二叉排序树的概念_二叉排序树是完全二叉树

二叉排序树详解　　二叉排序树详解　　摘要：本篇笔记专门介绍二叉排序树，重点讲解了二叉排序树的特性，以及二叉排序树各方面的基本实现。　　目录二叉排序树详解1.二叉排序树简介2.二叉排序树的实现2.1.二叉排序树的节点实现2.2.二叉排序树的管理类实现2.2.1.二叉排序树的结构定义2.2.2.二叉排序树的插入方法定义3.二叉排序树的中序遍历4.二叉排序树的节点查找5.二叉排序树的节点删除　　1.二叉排序树简介　　二叉排序树又称为二叉搜索树，是一种重要的数据结构，需要注意的是，在使用二分搜索中，搜索数组中每一个数字的函数调用栈重叠起来，就是一个平衡的或者说是接近平衡的二叉排序树，也就是说使用有序数组进行二分搜索实际上和在一个二叉排序树搜索一个节点干的事情是一样的。并且，对于一棵二叉排序树的深度优先中序遍历结果，就是一个有序的数组。二叉排序树首先要求该树是一棵二叉树，之后要求在这棵树中，所有子树的根节点的左子树上的节点值或者说是权重要均小于(或大于)根节点，而右子树上的所有节点值或者说是权重均大于(或小于)根节点。如图所示：　　
　　二者均为二叉排序树，其中的左右的大小关系根据具体情况而定。 2.二叉排序树的实现 2.1.二叉排序树的节点实现　　二叉排序树的节点和普通树的节点没有差异，只是整棵树在生成的时候有所限制，因此不再画图介绍，我们在IDE中直接创建文件，代表树的节点类，如图所示：　　
　　之后我们开始书写代码，在树的节点类中，我们需要创建的字段分别为，以及，我们将他们声明为私有类型，如图所示：　　
　　我们为其编写一个构造器，以便于节点对象初始化的时候就将这些数据进行赋值，如图所示：　　
　　之后我们为其所有字符生成访问器和修改器，方法简单，不再赘述，生成后如图所示：　　
　　在此附上源码：　　2.2.二叉排序树的管理类实现　　二叉排序树的管理类实际上就是二叉排序树类，在这个类中定义了二叉排序树的存储结构，以及对于二叉排序树的各种方法，因此关于二叉排序树的生成，节点添加，节点修改，节点删除，节点搜索等各种方法都会在此定义。为此，我们特意新建一个来存储这个管理类，如图所示：　　
2.2.1.二叉排序树的结构定义　　在管理类中，我们通常会定义一个指针字段，用于指向实体结构的首索引节点，如在链表中我们会定义一个节点，而在二叉排序树中我们也会定义一个节点，在之后的各种生成操作中，我们都会以这个节点为首索引节点，在这个节点上进行扩充，简而言之，我们使用这个节点来表示整棵树结构，实际上它并不是一棵树，但是它是我们访问这棵树的入口，因此我们在逻辑上认为它就是这棵树逻辑上的实体，它的定义并不难，一个字段即可，如图所示：　　
　　然而，真正困难的方法才刚要到来，接下来，我们研究二叉排序树的插入方法。 2.2.2.二叉排序树的插入方法定义　　首先我们使用画图的方式来描绘一下二叉排序树的插入过程，如图，我们要在一棵空的二叉排序树中插入一个数组，如图所示：　　
　　首先我们插入第一个素6，此时二叉排序树中还没有任何一个节点，因此我们应该新建一个节点，并将6存储进去，并将6认定为根节点，如图所示：　　
　　之后我们插入第二个素2，此时二叉排序树已经不是一个空树了，因此我们需要首先找到适合它的位置，我们将2和6进行对比，判断谁大谁小，我们发现2更小，因此2应该被插入在6的左子树中，之后我们将2和根节点6的左子树进行对比，发现6的左子树是空的，因此这时我们将2存放在6的左子树根节点位置，如图所示：　　
　　之后是素7,7显然大于6，因此我们要将7放在6的右子树中，经过探寻我们发现6的右子树根节点也是空的，因此我们需要将7放在右子树的根节点上，如图所示：　　
　　之后是素4，我们首先将4和6对比，发现4是小于6的，因此4应该位于6的左子树上，之后我们将4和6的左子树根节点进行对比，发现4是大于2的，因此4应该被放在2的右子树上，而2的右子树为空，因此4直接被放置在2的右子树根节点上，如图所示：　　
　　之后是素0，首先我们将0和素6进行对比，发现0是小于素6的，因此应该被放置在6的左子树上，之后我们将0和6的左子树根节点进行对比，发现其小于2，因此0应该被放置在2的左子树上，这时我们发现0是小于2的，因此0应该被放置在2的左子树上，同时我们发现2的左子树为空，因此我们将0放置在2的左子树根节点上，如图所示：　　
　　之后是素3，我们发现素3是小于6的，因此3应该被放置在6的左子树上，而这时我们就开始研究6的左子树，3大于2，因此3应该被放置在2的右子树上，这时我们开始研究2的右子树，而3是小于2的右子树根节点4的，因此3应该放置在4的左子树上，我们发现4的左子树为空，因此我们将3放置在4的左子树根节点上，如图所示：　　
　　之后是素1，首先我们将1和6进行对比，发现1是小于6的，因此1应该被放置在6的左子树上，而1又小于2，因此应该被放置在2的左子树上，而1又大于0，因此应该被放置在0的右子树上，0的右子树为空，因此1应该被放置在0的右子树根节点上，如图所示：　　
　　之后我们研究最后一个素5,5小于根节点6，因此我们应该将5放置在6的左子树上，而5大于2，因此我们应该将5放置在2的右子树上，5大于4，因此5应该被放置在4的右子树上，4的右子树为空，因此我们将5放置在4的右子树根节点上，如图所示：　　
　　至此这个二叉排序树宣布构造完毕，经过这个步骤，我们可以分析出二叉排序树的插入规则：。因此我们总结出来了插入的规律：　　现在我们来书写代码，首先我们书写一个普通的实现方式，代码如图所示：　　
　　我们在TreeNode类中重写一个toString方法，用来测试一下这个插入方法：　　
　　书写测试代码如下：　　
　　输出结果如下：　　
　　经验证发现这个输出结果是正确的，接下来我们分析代码：　　对于这个方法我又一个小小的优化方案，可以去掉父节点指针的使用：　　
　　现在让我们修改测试代码如下：　　
　　我们运行查看输出如下：　　我们可以发现其结果是和之前的方法输出一致的。除去普通的插入方法外，我们还可以使用一种递归的方法，首先因为这个插入过程就是一个递归插入的过程，实际上我们做的事情是：拿到新节点之后，先将其放在最大的树中进行比较，我们让它和根节点进行比较，如果其小于根节点，这时我们查看根节点是否拥有左子树，并将新节点放在根节点的左子树上进行比较，此时我们是与左子树的根节点进行了比较，我们将眼界缩小到了一棵子树，然后我们重复这个过程，因此这也是一个递归的过程，我们可以书写这样的递归方法来解决这个问题：　　
　　验证输出为：　　验证正确。　　代码如下：　　3.二叉排序树的中序遍历　　二叉树的深度优先中序遍历，对于一棵子树的遍历，是先检索左孩子节点，然后在检索根节点，之后再检索右孩子节点的，对于一棵比较大的树，它会递归的检索左子树，左子树检索完毕之后检索根节点，之后再递归的检索右子树，这个检索过程使得二叉排序树的深度优先中序遍历结果，是一个有序的排列，接下来我们写一下二叉排序树的中序遍历：　　
　　使用递归的方法并不难写，接下来让我们调用看看我们构建的二叉排序树使用中序遍历输出出来是否是一个有序的排列：　　
　　结果如下图所示，很显然我们输出了一个有序排列：　　
4.二叉排序树的节点查找　　在二叉排序树中进行指定值的节点查找非常简便，这个查找过程实际上就是一个二分搜索的过程，我们首先创建一个遍历指针，让这个指针指向排序树的根节点，如果根节点值等于我们想要查找的值，那么我们就直接进行返回操作即可，如果不等于，那么根节点必定大于或者小于我们要查找的值，此时我们根据具体情况在根节点的左子树或者右子树中继续查询，这里是一个递归过程，算法比较简单，因此不再深入研究，直接附上代码。　　5.二叉排序树的节点删除　　关于这个问题，实际上比较复杂，为了避免增大篇幅，我另起一篇笔记来记录这个知识点，链接查看。

二叉排序树的概念_二叉排序树是完全二叉树

相关推荐