我理解的数据结构（五）——二叉搜索树（BinarySearchTree）首先，二叉树和链表一样，并且动态数据结构有一个唯一的根节点每个节点最多有两个子节点每个节点最多有一个父节点具有自然递归结构每个节点的左子树也是二叉树每个节点的右子树也是二叉树一个节点或为空也是一棵二叉树二、二叉搜索树是一棵二叉树，其中每个节点的值大于其左子树中所有节点的值且小于其左子树中所有节点的值右子树。每个子树也是一个二叉搜索树。存储的元素必须是可比较的。三、二叉查找树基本代码实现1.基本代码因为二叉查找树的元素必须有可比较的行，所以E继承了Comparable，这是一个注意点publicclassBST>{//节点私有类节点{publicEe;公共节点离开；公共节点权；公共节点（Ee）{this.e=e;左=空；对=空；}}私有节点根；私有整数大小；公共BST(){root=null;大小=0；}publicintgetSize(){返回大小；}publicbooleanisEmpty(){返回大小==0;}}2.添加元素代码publicvoidadd(Ee){if(root==null){root=newNode(e);尺码++；}add(root,e);}//将元素e添加到以node为根节点的二叉搜索树中，递归调用privatevoidadd(Nodenode,Ee){if(node.e.compareTo(e)){//不考虑重复元素return;}elseif(node.e.compareTo(e)>0&&node.left==null){node.left=newNode(e);尺码++；返回;}elseif(node.e.compareTo(e)<0&&node.right==null){node.right=newNode(e);尺码++；返回;}if(node.e.compareTo(e)>0){add(node.left,e);}else{添加（node.right，e）;}}3。添加元素代码（优化）publicvoidadd(Ee){root=add(root,e);}//返回二叉搜索树的根privateNodeadd(Nodenode,Ee){if(node==null){大小++;返回新节点（e）；}if(node.e.compareTo(e)>0){node.left=add(node.left,e);}elseif(node.e.compareTo(e)<0){node.right=add(node.right,e);}返回节点；}4。查询元素代码//是否包含元素publicbooleancontains(Ee){returncontains(root,e);}privatebooleancontains(Nodenode,Ee){if(node==null){返回假；}if(node.e.compareTo(e)>0){returncontains(node.left,e);}elseif(node.e.compareTo(e)<0){returncontains(node.right,e);}else{返回真；}}四、二叉查找树的前中后序遍历下面以二叉树为例：///////////////////5/////\////36/////\\////248/////////////////////1。前序遍历（深度优先遍历）最常用的遍历方式//前序遍历publicvoidpreOrder(){preOrder(root);}privatevoidpreOrder(Nodenode){if(node==null）{返回;}//遍历前访问元素：前序遍历System.out.println(node.e);预购（节点。左）；preOrder(node.right);}前序遍历结果：5324682.前序遍历（非递归写法）publicvoidpreOrderNR(){//importjava.util.Stack;堆栈<节点>堆栈=新堆栈<>();堆栈。推（根）；while(!stack.isEmpty()){节点cur=stack.pop();System.out.println(cur.e);if(cur.right!=null){stack.push(cur.right);}if(cur.left!=null){stack.push(cur.left);}}}3。Inorder遍历二叉搜索树的中序遍历结果是顺序的//中序遍历publicvoidinOrder(){inOrder(root);}privatevoidinOrder(Nodenode){if(node==null){return;}为了（节点。左）；//遍历的中间访问元素：中序遍历System.out.println(node.e);inOrder(node.right);}中序遍历结果：2345684.中序遍历后应用场景：释放内存//后序遍历publicvoidpostOrder(){postOrder(root);}privatevoidpostOrder(Nodenode){if(node==null){return;}postOrder(node.left);postOrder(node.right);//遍历后访问元素：后序遍历System.out.println(node.e);}中序遍历结果：243865五、二叉搜索树遍历的顺序（广度优先遍历)不同于二叉搜索树的前序遍历，层序遍历是广度优先遍历还是这个例子：先遍历根节点5，再遍历3、6，最后遍历2、4、8///////////////////////////////////////////////////////////////////////////////////////\////36/////\\////248/////////////////////优点：找到解决方案问题更快在语言设计算法——最短路径代码实现中：//层序遍历publicvoidlevelOrder(){levelOrder(root);}privatevoidlevelOrder(Nodenode){//importjava.util.Queue;//导入java。实用程序链表；队列<节点>q=newLinkedList<>();((LinkedList)q).add(node);while(!q.isEmpty()){节点cur=q.remove();System.out.println(cur.e);如果(cur.left!=null){((LinkedList)q).add(cur.left);}if(cur.right!=null){((LinkedList)q).add(cur.right);}}}六、删除二叉搜索树的最大值和最小值1、从根节点向左节点寻找最小值的节点，直到找到该节点。left==null，此时的节点为最小值的节点//二叉搜索树的最小值publicEminimum(){if(size==0){thrownewIllegalArgumentException("BST为空！");}returnminimum(root).e;}//返回节点作为根二叉搜索树的最小值的节点privateNodeminimum(Nodenode){if(node.left==null){returnnode;}returnminimum(node.left);}2.从根节点开始寻找最大值的节点，一路找右节点，直到找到node.right==null，此时的节点就是具有最大值的节点maximumvalue//二叉搜索树的最大值publicEmaximum(){if(size==0){thrownewIllegalArgumentException("BSTisempty!");}returnmaximum(root).e;}//返回以节点为根的二叉搜索树最大值的节点privateNodemaximum(Nodenode){if(node.right==null){returnnode;}返回最大值（node.right）；}3。删除具有最小值的节点。如果要删除的节点是没有右子树的叶子节点，则直接删除。如果要删除的节点不是叶子节点，那么需要用当前节点替换右边的节点//删除最小值的节点publicEremoveMin(){Emin=minimum();root=removeMin(root);returnmin;}//删除以节点为最小值的节点的二叉查找树//删除节点后返回新的二叉查找树的根privateNoderemoveMin(Nodenode){//找到要查找的节点删除if(node.left==null){NoderightNode=node.right;节点.right=null;尺寸-;返回右节点；}node.left=removeMin(node.left);returnnode;}4.删除最大值的节点//删除最大值的节点publicEremoveMax(){Emax=最大值();root=removeMax(root);returnmax;}//删除二叉搜索树中最大值为node的节点//删除节点后返回新二叉搜索树的根privateNoderemoveMax(Nodenode){//找到要删除的节点if(node.right==null){节点leftNode=node.left;节点.left=null;尺寸-;返回左节点；}node.right=removeMax(node.right);returnnode;}7.删除二叉查找树任意值删除任意节点可以使用前驱（predecessor）和后继（successor）两种方法，下面使用后继方法删除任意节点有三种情况：只删除左子树的节点和删除最大值的节点在逻辑上是一样的删除只右子树的节点和删除最小值的节点在逻辑上是一样的删除左子树和右子树的节点1962年，希伯德提出希伯德删除原理图如下：//删除元素为e的节点publicvoidremove(Ee){root=remove(root,e);}privateNoderemove(Nodenode,Ee){if(node==null){returnnull;}if(node.e.compareTo(e)>0){node.left=remove(node.left,e);返回节点；elseif(node.e.compareTo(e)<0){node.right=remove(node.right,e);返回节点；}else{//e==node.eif(node.left==null){//左子树为空NoderightNode=node.right;节点.right=null;尺寸-;返回右节点；}if(node.right==null){//右子树为空NodeleftNode=node.left;节点.left=null;尺寸-;返回左节点；}//节点的后继节点Nodesuccessor=minimum(node.right);//将删除node.right的后继者后的二叉树赋值给后继权的后继者。right=removeMin(node.right);//将node.left赋值给左后继successor.left=node.left;节点.left=节点.right=null;返回继任者；}}
