二叉排序树的定义及查找头歌

二叉排序树的定义及查找方法

二叉排序树(Binary Search Tree)是一种树形数据结构，它的每个节点最多拥有两个子节点。同时，在二叉排序树中，所有左子树上的节点均小于它的父节点，所有右子树上的节点均大于它的父节点。这样的性质使得二叉排序树成为一种高效的数据存储结构，受到了广泛的应用。

一、二叉排序树的定义

在二叉排序树中，每个节点有三个字段，分别是节点的值val以及左子树的指针left和右子树的指针right。其定义如下：

```

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

```

二、二叉排序树的查找方法

我们可以使用递归或者迭代的方式来查找二叉排序树中的某个节点。

1. 递归查找方法

递归查找方法是二叉排序树最简单的查找方法。具体的过程是，从根节点开始，如果目标值等于当前节点的值，返回当前节点；如果目标值小于当前节点的值，则在左子树中查找；如果目标值大于当前节点的值，则在右子树中查找。如果找到了目标节点，则直接返回。如果没有找到，则返回NULL。

代码如下：

```

TreeNode* searchBST(TreeNode* root, int val) {

if (!root || root->val == val) return root;

if (val < root->val) {

return searchBST(root->left, val);

} else if (val > root->val) {

return searchBST(root->right, val);

}

return NULL;

}

```

2. 迭代查找方法

迭代查找方法可以使用栈的数据结构来实现。具体的过程是，从根节点开始，将当前节点压入栈中。如果目标值等于当前节点的值，返回当前节点；如果目标值小于当前节点的值，则将当前节点替换为左子节点；如果目标值大于当前节点的值，则将当前节点替换为右子节点。如果找到了目标节点，则直接返回。如果没有找到，则返回NULL。

代码如下：

```

TreeNode* searchBST(TreeNode* root, int val) {

stack st;

if (root) st.push(root);

while (!st.empty()) {

auto node = st.top(); st.pop();

if (node->val == val) {

return node;

} else if (val < node->val && node->left) {

st.push(node->left);

} else if (val > node->val && node->right) {

st.push(node->right);

}

}

return NULL;

}

```

三、总结

二叉排序树是一种高效的数据存储结构，它的查找操作可以使用递归或者迭代的方式实现。递归方式简单易实现，但可能会由于递归过深而导致出现栈溢出。迭代方式需要手动维护栈，稍微复杂一些，但可以避免栈溢出的问题。