前面我们已经学习了二叉树的基础知识。今天我们来看一种特殊的二叉树：二叉查找树，也称二叉搜索树、排序二叉树，它具有下列特点。
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；从它的名字我们就可以看得出来，二叉查找树是为了快速查找而生的。不过，它不仅在查找，而且在插入和删除的时间复杂度上都有很大的优势。
二叉查找树通常采用链式存储法进行存储。中序遍历二叉查找树即可获得一个有序序列。一个无序序列可以通过构建一个二叉查找树变成一个有序序列，构建树的过程就是对无序序列进行排序的过程。每次插入新的节点都是二叉查找树上新的叶子节点，不必移动其他节点，只需要改动某个节点的指针即可。
查找算法首先我们先看一下如何在二叉查找树中查找一个节点。
如果树为空树，则查找失败，否则：如果要查找的数据等于根节点，则查找成功，否则：如果要查找的数据小于根节点，则查找左子树；否则：就查找右子树；然后循环2、3、4步骤，直到查找成功下面我们结合代码更直观的来看一下：
publicclassSearchBST{publicTreeNodefind(intdata,TreeNodetree){TreeNodenode=tree;while(node!=null){if(datanode.value)//如果值小于节点的值，继续在左子树查找{node=node.left;}elseif(datanode.value)//如果值大于节点的值，继续在右子树查找{node=node.right;}else//如果值等于节点的值，返回该节点{returnnode;}}returnnull;}}publicclassTreeNode{intvalue;TreeNodeleft;TreeNoderight;TreeNode(intvalue){this.value=value;}}插入算法
二叉查找树的插入过程和查找过程类似。新插入的数据都是在叶子节点上，所以我们只要从根节点开始，依次比较节点和要插入数据的大小，然后确定插入位置。
如果树是空树，那么将插入数据作为根节点，否则：如果插入数据小于节点的数据，那么把数据插入到左子树中：否则：把数据插入到右子树中；循环上边步骤，直到某个节点的左子树为空，或者右子树为空我们也通过代码更直观的看一下插入的过程：
publicvoidinsert(intdata,TreeNodetree){if(tree==null){tree=newTreeNode(data);return;}TreeNodenode=tree;while(node!=null){if(datanode.value){if(node.left==null){node.left=newTreeNode(data);return;}node=node.left;}else{if(node.right==null){node.right=newTreeNode(data);return;}node=node.right;}}}删除算法
二叉查找树的查找和插入操作都相对比较简单，删除操作就比较复杂了。删除节点分为三种情况：
如果要删除的节点为叶子节点，也就是它没有子节点，那么我们直接删除该节点，然后把父节点的指针置为null即可。如果要删除的节点只有一个子节点（左子节点或右子节点），那么我们只需要更新父节点的指针，使其指向要删除节点的子节点即可。最复杂的情况是，要删除的节点有两个子节点。我们需要找到这个节点右子树的最小节点，把它替换到要删除的节点上，然后删除这个最小节点。下面我们来看一下删除的代码：
publicvoiddelete(intdata,TreeNodetree){TreeNodenode=tree;//node指向要删除的节点，初始化指向根节点TreeNodenodeParent=null;//nodeParent记录的是node的父节点while(node!=nullnode.value!=data){nodeParent=node;if(datanode.value)node=node.left;elsenode=node.right;}if(node==null)return;//没有找到//要删除的节点有两个子节点if(node.left!=nullnode.right!=null){//查找右子树中最小节点TreeNodeminNode=node.right;TreeNodeminNodeParent=node;//minNodeParent表示minNode的父节点while(minNode.left!=null){minNodeParent=minNode;minNode=minNode.left;}node.value=minNode.value;//将minNode的数据替换到node中node=minNode;//下面就变成了删除minNode了nodeParent=minNodeParent;}//删除节点是叶子节点或者仅有一个子节点TreeNodechild;//node的子节点if(node.left!=null)child=node.left;elseif(node.right!=null)child=node.right;elsechild=null;if(nodeParent==null)tree=child;//删除的是根节点elseif(nodeParent.left==node)nodeParent.left=child;elsenodeParent.right=child;}含有重复数据的二叉查找树
前边我们讲查找、插入和删除，都是默认二叉树中没有重复的数据。但是，实际开发中肯定会遇到需要重复数据的情况。那我们该怎么存储呢？
我们每个节点不仅仅存储一个数据，可以存储一个链表或者数组等数据结构，把相同的数据存储在一个节点上，这个比较简单直接，我们就不展开讨论了。
另一种方法就是每个节点还是只存储一个数据，可以允许树中两个或多个节点有相同的数据。那我们来看看这种情况下的查找、插入和删除操作。
我们先来看一下插入一个数据（因为我们需要知道相同的数据在树中是怎样存储的），当我们遇到一个节点的数据与要插入的数据相等时，我们把这个插入的数据当做大于这个节点的值来处理，继续在右子树中寻找插入的位置。
当我们要查找一个数据的时候，不能像原来一样，遇到相同的节点就停止了，需要继续在右子树中查找（因为可能会有相同的数据存在右子树中），直到叶子节点才停止。
当我们需要删除一个数据的时候，需要找出所有与删除数据相等的节点，然后按照上边的删除操作依次进行删除。
总结二叉查找树，支持快速的查找、插入和删除操作。中序遍历二叉查找树，可以输出有序的数据序列，非常高效。二叉查找树每个节点的值都大于左子树节点的值，小于或等于右子树节点的值。对于重复数据的存储，一种是每个节点存储多个相同的数据，另外一种是每个节点存储一个数据，遇到相同的保存到其右子树中。
如果觉得对你有帮助，可以点击在看，也可以分享给你的朋友
预览时标签不可点收录于话题#个上一篇下一篇