二叉排序树

二叉排序树1．二叉排序树定义二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。

（2）左右子树也都是二叉排序树，如图6-2所示。

2．二叉排序树的查找过程由其定义可见，二叉排序树的查找过程为：（1）若查找树为空，查找失败。

（2）查找树非空，将给定值key与查找树的根结点关键码比较。

（3）若相等，查找成功，结束查找过程，否则：①当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。

②当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。

3．二叉排序树插入操作和构造一棵二叉排序树向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。

因此，新插入结点一定是作为叶子结点添加上去的。

构造一棵二叉排序树则是逐个插入结点的过程。

对于关键码序列为：｛63，90，70，55，67，42，98，83，10，45，58｝，则构造一棵二叉排序树的过程如图6-3所示。

4．二叉排序树删除操作从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。

设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。

（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。

（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。

（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。

设删除*p结点前，中序遍历序列为：① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。

一、平衡二叉树的概念平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。

定义：平衡二叉树或为空树,或为如下性质的二叉排序树:（1）左右子树深度之差的绝对值不超过1;（2）左右子树仍然为平衡二叉树.平衡因子BF=左子树深度－右子树深度.平衡二叉树每个结点的平衡因子只能是1，0，-1。

若其绝对值超过1，则该二叉排序树就是不平衡的。

如图所示为平衡树和非平衡树示意图：二、平衡二叉树算法思想若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。

首先要找出插入新结点后失去平衡的最小子树根结点的指针。

然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。

当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。

假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

1）LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。

故需进行一次顺时针旋转操作。

即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。

而原来B的右子树则变成A的左子树。

（2）RR型平衡旋转法由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。

故需进行一次逆时针旋转操作。

即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。

而原来C的左子树则变成A的右子树。

（3）LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。

故需进行两次旋转操作（先逆时针，后顺时针）。

即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。

数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。

⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。

定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。

（这⾥的左⼦树和右⼦树也是⼆叉树）。

值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。

具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。

⽆序树的⼦树⽆左右之分。

2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。

这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。

完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。

如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。

性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。

证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。

不能构成二叉排序树的一条查找路径在这个充满算法和代码的世界里，咱们聊聊二叉排序树吧，听起来是不是有点高深？二叉排序树就是一个神奇的家族，大家各自有各自的地方。

想象一下，咱们把一群人放在一个大房子里，每个人都有自己的房间，按大小来排列。

大一点的在右边，小一点的在左边。

这个家族的规矩就是，左边的小于自己，右边的大于自己，大家齐心协力让这个家变得有序，谁都不能打乱这个秩序。

不过，有时候啊，这个秩序就会被打破。

你想啊，假如有一天，一个家伙来了，他在外面嚷嚷着：“我可是最厉害的，我不想按照规矩来！”这可麻烦了，大家心里一紧，这条查找路径就会变得曲曲折折，甚至有点让人头疼。

二叉排序树可不是随便什么都能进来的，要有良好的家庭背景，懂规矩才能有位置。

想象一下，如果那个家伙的数字比家里最大的都要大，硬是往右边挤，那可真是让人哭笑不得。

再说说查找路径，简直就像寻宝一样。

想要找到宝藏，就得沿着正确的路线走。

可是，如果你走了一条“二叉排序树”的弯路，嘿，那可是个大问题。

比如说，有个数字在树的左边，结果你非要往右走，真是太离谱了。

你说这查找路径就像迷路，完全走偏了。

可是，偏偏这条错路就成了你的终点，简直让人感到无奈啊。

哎呀，咱们再想想，如果这个家族里出现了很多不合规矩的人，他们在这儿混乱得不可开交，二叉排序树就会失去意义。

你想啊，所有的数字都乱七八糟地挤在一起，左边也不再小于右边，树就变成了一堆杂乱无章的东西。

那种感觉就像大扫除时，家里突然变得乱七八糟，让人想要大喊：“我的天啊，快来帮忙！”二叉排序树是个追求秩序的地方，想要在里面生存，得遵循规矩。

如果你想插入一个新成员，得确保他是合适的。

否则，不仅你自己找不到路，连别人也会跟着懵圈。

那种情况下，别说“查找路径”了，连“家”都找不到了。

在这个二叉排序树的大家庭中，大家都有自己的位置，没位置的人可得想办法来适应。

像极了生活中的很多场景，有时候为了融入一个圈子，你可能得调整自己，找对路径，不然就会被排除在外。

二叉排序树的构造方法二叉排序树又称二叉查找树，是一种经典的数据结构，它具有快速的插入、删除和查找等操作。

在实际应用中，二叉排序树被广泛地使用，因此了解二叉排序树的构造方法至关重要。

本文将介绍二叉排序树的构造方法，帮助读者深入理解这一数据结构。

一、二叉排序树基本概念二叉排序树是一种二叉树，每个节点包含一个值，并且满足以下性质：1. 左子树上所有节点的值均小于其父节点的值；2. 右子树上所有节点的值均大于其父节点的值；3. 左右子树也分别为二叉排序树。

根据上述性质，可以得出二叉排序树的中序遍历结果为有序序列。

这一特点使得二叉排序树成为一种非常有效的数据结构，用于快速查找和排序。

二、二叉排序树的构造方法在构造二叉排序树时，一般采用递归或循环遍历的方法。

下面将分别介绍这两种构造方法。

1. 递归构造方法递归构造方法是一种常见且直观的构造二叉排序树的方式。

其基本原理为，将新节点插入到当前节点的左子树或右子树上，直至找到合适的位置。

具体流程如下所示：（1）若二叉排序树为空，直接将新节点作为根节点插入；（2）若新节点值小于当前节点值，则递归地将其插入到左子树上；（3）若新节点值大于当前节点值，则递归地将其插入到右子树上。

通过递归构造方法，可以很方便地构造出一棵满足二叉排序树性质的树。

2. 循环构造方法循环构造方法是另一种构造二叉排序树的方式，通过使用迭代的方式，逐步构建二叉排序树。

其基本思路为：（1）从根节点开始，若树为空，则直接将新节点插入为根节点；（2）若树不为空，则利用循环遍历的方式，找到新节点应插入的位置，直至找到合适的叶子节点；（3）将新节点插入到找到的叶子节点的左子树或右子树上。

循环构造方法相对于递归构造方法，更加迭代化，适合于对二叉排序树进行迭代构造和遍历。

三、二叉排序树构造方法的实现在实际编程中，可以通过使用递归或循环的方式，实现二叉排序树的构造。

下面将简要介绍二叉排序树构造方法的实现过程。

1. 递归实现递归实现二叉排序树的构造方法一般通过编写递归函数，不断地将新节点插入到当前节点的左子树或右子树上。

介绍二叉排序树的结构和特点二叉排序树，也称为二叉搜索树或二叉查找树，是一种特殊的二叉树结构，其主要特点是左子树上的节点都小于根节点，右子树上的节点都大于根节点。

在二叉排序树中，每个节点都存储着一个关键字，而且所有的关键字都不相同。

二叉排序树的结构如下：1.根节点：二叉排序树的根节点是整个树的起始点，其关键字是最大的。

2.左子树：根节点的左子树包含着小于根节点关键字的所有节点，且左子树本身也是一个二叉排序树。

3.右子树：根节点的右子树包含着大于根节点关键字的所有节点，且右子树本身也是一个二叉排序树。

二叉排序树的特点如下：1.有序性：二叉排序树的最重要特点是有序性。

由于左子树上的节点都小于根节点，右子树上的节点都大于根节点，所以通过中序遍历二叉排序树，可以得到一个有序的序列。

2.快速查找：由于二叉排序树是有序的，所以可以利用二叉排序树进行快速查找操作。

对于给定的关键字，可以通过比较关键字与当前节点的大小关系，逐步缩小查找范围，最终找到目标节点。

3.快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。

插入操作可以通过比较关键字的大小关系，找到合适的位置进行插入。

删除操作可以根据不同情况，分为三种情况处理：删除节点没有子节点、删除节点只有一个子节点和删除节点有两个子节点。

4.可以用于排序：由于二叉排序树的有序性，可以利用二叉排序树对一组数据进行排序。

将数据依次插入二叉排序树中，然后再通过中序遍历得到有序序列。

二叉排序树的优缺点如下：1.优点：(1)快速查找：通过二叉排序树可以提供快速的查找操作，时间复杂度为O(log n)。

(2)快速插入和删除：由于二叉排序树的有序性，插入和删除操作比较简单高效。

(3)可以用于排序：通过二叉排序树可以对一组数据进行排序，时间复杂度为O(nlog n)。

2.缺点：(1)受数据分布影响：如果数据分布不均匀，可能导致二叉排序树的高度增加，从而降低了查找效率。

(2)不适合大规模数据：对于大规模数据，二叉排序树可能会导致树的高度过高，从而影响了查找效率。

二叉排序树查找的递归算法介绍二叉排序树（Binary Search Tree），也称二叉查找树、有序二叉树或排序二叉树，是一种常用的数据结构。

它具有以下特点：•每个节点都包含一个键值和对应的数据。

•左子树中的所有节点的键值都小于根节点的键值。

•右子树中的所有节点的键值都大于根节点的键值。

•左右子树也分别是二叉排序树。

二叉排序树支持高效的查找、插入和删除操作，其中查找操作是利用递归实现的。

本文将详细介绍二叉排序树查找的递归算法。

二叉排序树的定义二叉排序树的定义如下：class TreeNode:def __init__(self, key, data):self.key = keyself.data = dataself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = None在二叉排序树中，每个节点都是一个TreeNode对象，包含键值key和对应的数据data。

left和right分别指向左子树和右子树的根节点。

树的根节点由BinarySearchTree对象的root属性表示。

二叉排序树查找的递归算法二叉排序树的查找操作是利用递归实现的，其具体算法如下：1.如果待查找的键值等于当前节点的键值，返回当前节点的数据。

2.如果待查找的键值小于当前节点的键值，递归在左子树中查找。

3.如果待查找的键值大于当前节点的键值，递归在右子树中查找。

4.如果在左子树或右子树中找不到对应的键值，则返回空。

下面是二叉排序树查找的递归算法的代码实现：def search_recursive(node, key):if node is None or node.key == key:return node.dataelif key < node.key:return search_recursive(node.left, key)else:return search_recursive(node.right, key)在上述代码中，node表示当前节点，key表示待查找的键值。

以二叉树或树作为表的组织形式，称为树表，它是一类动态查找表，不仅适合于数据查找，也适合于表插入和删除操作。

常见的树表：二叉排序树平衡二叉树B-树B+树9.3.1 二叉排序树二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：❶若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根节点值；❷若它的右子树非空，则右子树上所有节点值均大于根节点值；❸左、右子树本身又各是一棵二叉排序树。

注意：二叉排序树中没有相同关键字的节点。

二叉树结构满足BST性质：节点值约束二叉排序树503080209010854035252388例如:是二叉排序树。

66不试一试二叉排序树的中序遍历序列有什么特点？二叉排序树的节点类型如下：typedef struct node{KeyType key;//关键字项InfoType data;//其他数据域struct node*lchild,*rchild;//左右孩子指针}BSTNode;二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。

1、二叉排序树上的查找Nk< bt->keybtk> bt->key 每一层只和一个节点进行关键字比较！∧∧p查找到p所指节点若k<p->data，并且p->lchild=NULL，查找失败。

若k>p->data，并且p->rchild=NULL，查找失败。

查找失败的情况加上外部节点一个外部节点对应某内部节点的一个NULL指针递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该节点指针，否则返回NULL）：BSTNode*SearchBST(BSTNode*bt,KeyType k){if(bt==NULL||bt->key==k)//递归出口return bt;if(k<bt->key)return SearchBST(bt->lchild,k);//在左子树中递归查找elsereturn SearchBST(bt->rchild,k);//在右子树中递归查找}在二叉排序树中插入一个关键字为k的新节点，要保证插入后仍满足BST性质。

平衡树——特点：所有结点左右子树深度差≤1排序树——特点：所有结点―左小右大字典树——由字符串构成的二叉排序树判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）带权树——特点：路径带权值（例如长度）最优树——是带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。

1.1 二叉排序树：或是一棵空树；或者是具有如下性质的非空二叉树：（1）若左子树不为空，左子树的所有结点的值均小于根的值；（2）若右子树不为空，右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。

例：二叉排序树如图9.7：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。

中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.2.2 二叉排序树b中查找在二叉排序树b中查找x的过程为：1. 若b是空树，则搜索失败，否则：2. 若x等于b的根节点的数据域之值，则查找成功；否则：3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：4. 查找右子树。

[cpp]view plaincopyprint?1.Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){2. //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，3. //则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的4. //最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL5. if(!T){ p=f; return FALSE;} //查找不成功6. else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功7. else if LT(key,T->data.key)8. return SearchBST(T->lchild, key, T, p); //在左子树继续查找9. else return SearchBST(T->rchild, key, T, p); //在右子树继续查找10.}2.3 在二叉排序树插入结点的算法向一个二叉排序树b中插入一个结点s的算法，过程为：1. 若b是空树，则将s所指结点作为根结点插入，否则：2. 若s->data等于b的根结点的数据域之值，则返回，否则：3. 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：4. 把s所指结点插入到右子树中。

二叉排序树课程设计一、课程目标知识目标：1. 理解二叉排序树的概念和特点；2. 掌握二叉排序树的插入、删除和查找操作；3. 能够分析二叉排序树的时间复杂度；4. 了解二叉排序树在实际应用中的优势。

技能目标：1. 能够手动构建二叉排序树并进行基本操作；2. 能够运用编程语言实现二叉排序树的基本功能；3. 能够分析并解决二叉排序树相关的问题；4. 能够运用二叉排序树解决实际排序和查找问题。

情感态度价值观目标：1. 培养学生对数据结构和算法的兴趣，激发学习热情；2. 培养学生的逻辑思维能力和问题解决能力；3. 培养学生的团队协作意识，学会与他人共同分析、解决问题；4. 培养学生严谨的科学态度，注重算法的正确性和效率。

课程性质：本课程为计算机科学领域的数据结构与算法课程，旨在让学生掌握二叉排序树的基本概念和操作，提高学生的编程能力和逻辑思维能力。

学生特点：学生具备基本的计算机知识和编程基础，对数据结构有一定了解，但对二叉排序树的认识可能较浅。

教学要求：结合学生特点，采用讲解、实践和讨论相结合的教学方法，使学生在理解二叉排序树理论知识的基础上，能够动手实践并解决实际问题。

在教学过程中，注重培养学生的自主学习能力和团队合作精神，提高学生的综合素质。

通过本课程的学习，使学生能够达到上述课程目标，为后续相关课程打下坚实基础。

二、教学内容1. 引入二叉排序树的概念，阐述其定义、性质和应用场景；- 教材章节：第三章第一节“二叉排序树的定义和性质”2. 讲解二叉排序树的插入、删除、查找操作及其实现方法；- 教材章节：第三章第二节“二叉排序树的操作”3. 分析二叉排序树的性能特点，包括时间复杂度和空间复杂度；- 教材章节：第三章第三节“二叉排序树的性能分析”4. 介绍二叉排序树在实际应用中的优势，如排序、查找等；- 教材章节：第三章第四节“二叉排序树的应用”5. 结合实例，让学生动手实践二叉排序树的构建和操作；- 教材章节：第三章实例分析与编程练习6. 总结二叉排序树的特点和适用场景，与其他排序方法进行对比；- 教材章节：第三章总结与拓展教学进度安排：1. 第1课时：引入二叉排序树的概念、性质和应用场景；2. 第2课时：讲解二叉排序树的插入、删除、查找操作；3. 第3课时：分析二叉排序树的性能特点；4. 第4课时：介绍二叉排序树在实际应用中的优势；5. 第5课时：结合实例，学生动手实践二叉排序树的构建和操作；6. 第6课时：总结二叉排序树，与其他排序方法进行对比。

头歌二叉排序表的基本操作一、概述二叉排序树，也称为二叉搜索树（Binary Search Tree, BST），是一种特殊的二叉树，其中每个节点都满足以下性质：对于任意节点，其左子树中所有节点的值都小于该节点的值，而其右子树中所有节点的值都大于该节点的值。

这种特性使得二叉排序树成为一种非常有效的数据结构，用于在各种算法中实现快速查找、插入和删除操作。

二、基本操作1. 插入操作插入操作是二叉排序树中最常用的操作之一。

其基本步骤如下：（1）创建一个新节点，并将要插入的值赋给该节点。

（2）如果二叉排序树为空，则将新节点作为根节点。

（3）否则，从根节点开始比较新节点的值与当前节点的值。

如果新节点的值小于当前节点的值，则将新节点插入到当前节点的左子树中；否则，将新节点插入到当前节点的右子树中。

（4）重复步骤3，直到找到一个空位置来插入新节点。

2. 删除操作删除操作是二叉排序树中比较复杂的操作之一。

其基本步骤如下：（1）找到要删除的节点。

如果找不到要删除的节点，则无法进行删除操作。

（2）如果找到要删除的节点，则将其从树中删除。

如果该节点只有一个子节点，则直接删除该节点；如果该节点有两个子节点，则可以选择将其中的一个子节点“提升”到该节点的位置，然后删除该子节点。

在提升子节点时，需要考虑子节点的值与要删除的节点的值之间的关系，以确保二叉排序树的性质不变。

（3）如果被提升的子节点仍然包含要删除的节点，则需要重复步骤2，直到找到要删除的节点并将其删除。

3. 查找操作查找操作用于在二叉排序树中查找指定的值。

其基本步骤如下：（1）从根节点开始，比较当前节点的值与要查找的值。

如果它们相等，则查找成功，返回当前节点的位置。

（2）如果当前节点的值大于要查找的值，则进入当前节点的左子树中进行查找；否则进入当前节点的右子树中进行查找。

（3）重复步骤2，直到找到要查找的值或者搜索路径上的所有节点都已访问过。

如果最终没有找到要查找的值，则返回空指针。