免费企业邮箱账号密码_国外工作招聘网站_个人网页设计制作网站模板_广告推广一个月多少钱

定义：

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

1. 空树是二叉搜索树。

2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 N个结点的二叉搜索树中，这些操作的最优时间复杂度为O(logn) ，最坏为O(n) 。随机构造这样一棵二叉搜索树的期望高度为O(logn)  。

二叉搜索树节点的定义:

struct TreeNode{int key;TreeNode*left;TreeNode*right;//维护其他信息，如高度，节点数量。int size;//当前节点为根的子树大小int count;// 当前节点的重复数量TreeNode(int value): key(value), size(1), count(1), left(nullptr), right(nullptr) {} 
};

  

遍历二叉搜索树

由二叉搜索树的递归定义可得，二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为O(n)

void inOrderTraversal(TreeNode * root) 
{// 1. 如果当前节点为空，直接返回if (root == nullptr) {return;}// 2. 递归遍历左子树inOrderTraversal(root->left);// 3. 访问当前节点cout << root->key << ' ';// 4. 递归遍历右子树inOrderTraversal(root->right);    
}

查找最小/最大值

由二叉搜索树的性质可得，二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。时间复杂度为O(h)。

int findMin(TreeNode * root)
{if(root == nullptr) return -1;while(root ->left != nullptr) root = root ->left;return root ->key;
}
int findMax(TreeNode* root) {if (root == nullptr) {return -1;}while (root->right !&