第12章 二叉查找树

# 一、概念 ### 1.定义与性质 （1）设x为二叉查找树中的一个结点，若y是x左子树中的一个结点，则key[y] <= key[x]；若y是x右子树中的一个结点，则key[x]<=key[y] （2）二叉查找树上执行的基本操作的时间与树的高度成正比。 ### 2.结构 （1）结点结构： 关键字key 卫星数据data 分别指向父、左右孩子的指针p, left, right ### 3.在二叉查找树上的操作 查找一个关键字：SEARCH(x, k) 求最小关键字：MINIMUM(x) 求最大关键字：MAXIMUM(x) 求前驱：PREDECESSOR(x) 求后继：SUCCESSOR(x) 插入一个结点：INSERT(T, z) 删除一个结点：DELETE(z) ### 4.二叉查找树的应用 1.遍历：中序遍历、先序遍历、后序遍历 2.查找：查找包含某个关键字的结点，查找关键字最大或最小的结点、查找某个结点的前驱或后继 # 二、代码 [头文件](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/include/binarySearchTree.h) [产品代码](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/src/binarySearchTree.cpp) 测试代码 # 三、练习 ### 12.1 二叉查找树 12.1-2 二叉查找树：左子树关键字<根结点关键字<右子树关键字 堆：左子树关键字<根结点关键字 && 右子树关键字<根结点关键字 不能，因为一个结点的的左子树与右子树的关键字大小没有关系 12.1-3 用栈实现：见[算法导论-10.4-有根树的表示](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707756)中的10.4-3 不用栈实现：见[算法导论-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490) 12.1-4 ~~~ //递归的先序遍历 void BST_Tree::Preorder_Tree_Walk(BST_Node *x) { //x不是叶子结点 if(x != NULL) { //访问当前结点 cout<<x->key<<' '; //先序遍历当前结点的左子树 Preorder_Tree_Walk(x->left); //先序遍历当前结点的右子树 Preorder_Tree_Walk(x->right); } } //递归的后序遍历 void BST_Tree::Postorder_Tree_Walk(BST_Node *x) { //x不是叶子结点 if(x != NULL) { //后序遍历当前结点的左子树 Postorder_Tree_Walk(x->left); //后序遍历当前结点的右子树 Postorder_Tree_Walk(x->right); //访问当前结点 cout<<x->data<<' '; } } ~~~ ### 12.2 查询二叉查找树 ~~~ 12.2-1 c，e 12.2-2 //递归地查找最小值 BST_Node *BST_Tree::Tree_Minimum(BST_Node *x) { if(x->left != NULL) return Tree_Minimum(x->left); else return x; } //递归的查找最大值 BST_Node *BST_Tree::Tree_Maximum(BST_Node *x) { if(x->right != NULL) return Tree_Maximum(x->right); else return x; } 12.2-3 //查找中序遍历下x的前驱，即小于x的最大值 BST_Node *BST_Tree::Tree_Predecessor(BST_Node *x) { //如果x的左子树非空 if(x->left != NULL) //x的前驱是x的左子树的最大值 return Tree_Maximum(x->left); //如果x的左子树为空且x有前驱y，那么y是x的最低祖先结点，且y的右儿子也是 BST_Node *y = x->p; while(y != NULL && x == y->left) { x = y; y = y->p; } return y; } 12.2-4 （1） 4->left = 2 4->right =NIL 2->left = 1 2->right = 3 搜索路径4-2-1 （2） 1->right = 3 1->left = NUL 3->left = 2 3->right = 4 搜索路径1-3-4 ~~~ ### 12.3 插入和删除 12.3-1 ~~~ //递归的二叉查找树的插入操作，分三种情况 void BST_Tree::Tree_Insert(BST_Node *x, BST_Node *z) { //已经存在 if(z->key == x->key) { cout<<"error:exist"<<endl; return; } //插入到x的左子树中 else if(z->key < x->key) { //x没有左子树 if(x->left == NULL) { //修改指针，插入操作 x->left = z; z->p = x; return; } //x有左子树 else //对x的左子树执行插入操作 Tree_Insert(x->left, z); } //插入到x的右子树中，与上面类似 else if(z->key > x->key) { if(x->right == NULL) { x->right = z; z->p = x; } else Tree_Insert(x->right, z); } } ~~~ 12.3-3 最坏是n^2 最好是nlgn 12.3-4 求y的前驱z分为两种情况，以下分别讨论： （1）y有左孩子，则z是left[y]中最右边的结点，z没有右孩子，因此删除z时直接删除修改指针即可，没有问题 （2）y没有左孩子，则z是y的祖先，y是z右子树是最左边的点，又分为两种情况： （2.1）若z没有左孩子，则直接删除z并修改指针，没有问题。 （2.2）若z有左孩子，则不直接删除z，而是用z代替y存在并删除y。这里会有问题，另一个数据结构中的保存了指向y的指针，但是y的内容转移到另一个结点上了，指向y的指针指向了一个被释放的空间。 解决方法：使TREE-DELETE返回删除后的y的指针，这个值可能会变，可能不变。让另一个数据结构的y指针指向TREE-DELETE的返回值。 12.3-5 不或交换，反例如图   12.3-6 当待删除结点有两个子树时，不删除待删除结点，而是删除它的前驱或后继，用随机数rand()%2来确定删除的前驱还是后继 代码见文：二 # 四、思考题 ### 12-1 具有相同关键字元素的二叉树 见[算法导论-12-1-具有相同关键字元素的二叉查找树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719138) ### 12-2 基数树 见[算法导论-12-2-基数树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719324) 12-3 随机构造的二叉查找树中的平均结点深度 f）待解决