掉一根头发，吃透二叉查找树

前言前面介绍的大部分学习都是和线性表相关的。理解了指针之后，就不难了。规则比较简单，后面会讲解一些比较通用的数据结构，以多图的方式让大家更容易吸收。在数据结构和算法中，树是一个比较大的家族。家族中有很多有权势的成员。这些成员包括二叉树和多叉树（如B+树等），而在二叉树这个大家族中，二叉搜索树（也称为二叉排序树）是最基本的，在此基础上可以继续拓展学习AVL（二叉平衡树）、红黑树等知识。对于二叉排序树，本章重点介绍它的实现和插入、删除的步骤。我们会手写一个二叉排序树，二叉树遍历部分的内容会单独详细讲解。什么是树？树是一种数据结构，它是由n（n>=1）个有限节点组成的一组层次关系。它被称为“树”，因为它看起来像一棵倒置的树，这意味着它的根朝上，叶子朝下。树是递归的，树的任意一个节点和该节点下的节点都可以组合成一棵新树，所以树的很多问题都是用递归解决的。根节点：最顶层节点（root），根节点没有父节点，只有子节点（0个或多个都可以）层数：一般认为根节点是第一层（也有的说是第0层），树的高度为层数最高的节点的层数（上层数从1开始）节点关系：父节点：与该节点相连的上层节点，子节点：对应到父节点，上下关系。祖先节点是父节点的父节点（或祖先）节点。兄弟节点：父节点相同的节点！节点度：该节点拥有的子节点数（直连子节点，不是后代）。树度：所有节点中最大的（节点的度）。同时，如果度数大于0的节点是分支节点，则度数等于0的节点是叶子节点（没有后代）。相关性质：二叉树二叉树是树的一种，但是应用较多，需要深入研究。二叉树的每个节点最多有两个子节点（但不一定是两个节点）。二叉树和度数为2的树的区别：1.度数为2的树必须有3个以上节点（否则不叫度数为2的，必须先存在），而二叉树树可以是空的。2、二叉树的度不一定是2，比如斜树。3、二叉树有左右节点之分，而度数为2的树没有左右节点之分。几种特殊的二叉树：满二叉树：一棵高度为n的满二叉树有(2^n)-1个节点fullbinarytree完全二叉树：上层全是满二叉树，底层依次从上到下排列从左到右完全二叉树二叉排序树：按照一定的规则插入树并排序（本文有详细介绍）。平衡二叉树：树上任意节点的左子树和右子树的深度差不超过1（后面详述）。二叉树的性质：1.二叉树的有用树的性质。2、非空二叉树的叶子节点个数=度数为2+1的节点个数。本来一个节点如果度数为1，它会继续做叶子，但是如果有度数为2的节点，除了继续原来的节点，还会多出一个节点需要维护.所以最后会有一片额外的叶子。3.非空第i层最多有2^(i-1)个节点。4.一棵高度为h的树，至多有(2^h)-1个节点（等比求和）。二叉树一般都是链式存储，这样内存利用率比较高，但是二叉树也可以用数组存储（经常遇到），计算每个节点对应的下标。如果从左到右取一棵完整的二叉树，从上到下编号如图：一棵二叉排序树的详细介绍，二叉查找树具有二叉树的性质，同时有其自身的一些规则：首先，你必须了解二叉排序树的规则：从任意一个节点开始，节点左侧的节点值总是小于节点右侧的值。例如，将15、6、23、7、4、71、5、50依次插入二叉排序树中，就会形成下图所示的序列。构建了一个二叉排序树。二叉排序树由多个节点组成。对于节点，这些属性是必需的：left、right和value。其中left和right是指向左右子树的左右指针，value是存储的数据，这里使用int类型。节点类构造为：classnode{//nodepublicintvalue;publicnodeleft;publicnoderight;publicnode(){}publicnode(intvalue){this.value=value;this.left=null;this.right=null;}publicnode(intvalue,nodel,noder){this.value=value;this.left=l;this.right=r;}}既然已经构造了节点，接下来就要用节点等其他信息构造一棵树。有了构造链表的经验，很容易知道一棵树最重要的是根节点。所以树的结构是：publicclassBinarySortTree{noderoot;//rootpublicBinarySortTree(){root=null;}publicvoidmakeEmpty()//清空{root=null;}publicbooleanisEmpty()//检查是否为空{returnroot==空；}//各种方法}可以用一个图来表示这个结构：既然main方法已经构造了一棵树，那么就需要实现main方法，因为二叉排序树中的每个节点都可以看作是一棵树。所以我们在创建方法的时候，是时候加入节点参数了（方便一些递归调用）findmax(),findmin()findmin()寻找最小的节点：因为所有节点中最小的插入到左边，所以只需要找到最左边的返回即可，具体实现可以使用递归或者非递归while循环。findmax()寻找最大节点：因为所有较大的节点都向右插入，所以只需要找到最右边的并返回，实现方法与findmin()方法一致。代码使用递归函数publicnodefindmin(nodet)//找到最小返回值为node，需要调用.value{if(t==null){returnnull;}elseif(t.left==null){returnt;}elsereturn(findmin(t.left));}publicnodefindmax(nodet)//求最大值{if(t==null){returnnull;}elseif(t.right==null){returnt;}elsereturn(findmax(t.right)));}求一个图中的最大值和最小值的过程如下：这里的查找过程isContains(intx)是指查找二叉搜索树中是否存在值为x的节点。具体实现上，根据二叉排序树左边小右边大的性质，向下查找。如果找到值为x的节点，则返回true，如果找不到，则返回false。当然实现可以使用Recursive或者非递归，我这里使用的是非递归的方式。publicbooleanisContains(intx)//有没有{nodecurrent=root;if(root==null){returnfalse;}while(current.value!=x&¤t!=null){if(xcurrent.value){current=current.right;}if(current==null){returnfalse;}//如果super直接返回就在里面判断}//这里判断是否为空positionif(current.value==x){returntrue;}returnfalse;}insert(intx)类似于前面的isContains(intx)，找到自己的位置（空位置）插入。但是在具体实现中也有一些需要注意的地方。我们需要去到下一层要插入的节点。你可能会疑惑为什么不直接找到最后一个空的地方，然后将current赋值给current=newnode(x)，这样current就相当于指向一个newnode(x)节点，与原来的树分离（原树相当于没有操作），所以需要判断父节点是否为空来提前找位置，通过left或者父节点找到合适的位置。右边的节点指向新创建的节点，完成插入操作。publicnodeinsert(intx)//insertt是对root的引用{nodecurrent=root;if(root==null){root=newnode(x);returnroot;}while(current!=null){if(xcurrent.value){if(current.right==null){returncurrent.right=newnode(x);}elsecurrent=current.right;}}returncurrent;//没用}比如上面的树插入一个值为51的节点插入一个值为51的节点delete(intx)删除操作是一个比较难理解的操作，因为要删除的点可能在不同的位置，所以具体的处理方式也不同。如果是叶子，可以直接删除。有一个子节点可以替换为子节点。如果有两个子节点，先找到值最接近待删除节点的点（左子树最大点或右子树最小点），替换值，然后递归操作子树删除被替换的节点，当然没有具体分析，可以看下：图中红点均满足此方法）。待删除的节点是一个叶子节点，一个子节点为空：这种情况也很容易，将删除点的子节点放在被删除的位置即可。待删除节点有一个子节点，且左右节点不为空。情况比较复杂，因为其中一个子节点不能直接用来替换当前节点（放不下，如果子节点也有两个子节点那么还有一个不能放的节点，比如replace它与下面的节点71）如果要删除的节点有两个孩子，如果它填充了19或71个节点。虽然可以保证部分边大于或小于节点，但是在合并时会造成混乱。例如，如果您使用71个节点而不是23个节点。那么就需要考虑如何处理这三个节点（19、50、75），是否满了，有没有孩子。这是一个复杂的过程，不适合考虑。因此，我们需要分析我们想要的点的属性：可以保证该点在这个位置仍然满足二叉搜索树的性质（找到最接近的值），那么子树中的哪个节点满足这样的关系？左子树右子树中的最右节点或者右子树中的最左节点都满足了，我们可以选择一个节点来代替要删除的节点的值（这里用左子树的最右节点代替）。这个点更换后怎么办？这很简单。二叉树用递归的思想来解题，再次调用delete函数删除左子树中被替换的节点。先替换值，然后递归删除子树中的18个节点。这里的演示是选择左子树中最大的节点（最右边）进行替换。当然，使用右子树中最小的节点也可以满足这里要删除的大小关系，原理是一样的。整个删除算法流程为：这部分删除流程的代码为：publicnoderemove(intx,nodet)//删除节点{if(t==null){returnnull;}if(xt.value){t.right=remove(x,t.right);}elseif(t.left!=null&&t.right!=null)//左右节点不为空{t.value=findmin(t.right).value;//找右边的最小值代替t.right=remove(t.value,t.right);}else//左右单空或左右全空{if(t.left==null&&t.right==null){t=null;}elseif(t.right!=null){t=t.right;}elseif(t.left!=null){t=t.left;}return;}returnt;}完整代码这段完整代码是作者大三的时候写的，可能有很多遗漏或者不规范的地方，仅供学习参考，如有遗漏和错误请指正。二叉排序树的完整代码是：结语到这里我们已经了解了树、二叉树和二叉搜索树。二叉查找树的插入和查找比较容易理解，但是在实现的时候要注意函数参数的引用等等。比较难的是二叉树的删除。用递归的思路，分类别讨论删除的情况。寻找特例和常见情况，递归在一定程度上也是对问题的一种改造（把它变成和自己一样的问题，缩小范围）。思考。下面还会介绍二叉树的三阶遍历（递归和非递归）和层序遍历。这些都是比较经典和流行的问题，需要深入了解。