• 欢迎来到我的博客
  • [email protected]

二叉树、二叉排序树

学习笔记 tianlan 1年前 (2020-04-09) 529次浏览 0个评论 扫描二维码
文章目录[隐藏]

 

几个概念:根节点、兄弟节点、叶子节点(没有子元素、末端节点)

度:节点的子节点数

 

二叉树

二叉树、二叉排序树

①普通二叉树

②满二叉树

③完全二叉树(和满二叉树相比,只少了点最后一层的右侧叶子节点)

二叉树的基本性质

性质1:

在第 i 层最多有 2i-1 个节点。

性质2:

深度为 k 的二叉树最多有 2k-1 个节点。

性质3:

对于任何一个二叉树,叶子节点数为 n0,度为 2 的节点数为 n2,则 n0 = n2+1。

性质4 具有n 个结点的完全二叉树的深度k 为[log2n]+1。

证明根据完全二叉树的定义和性质2 可知,当一棵完全二叉树的深度为k、结点个数为n 时,有

二叉树、二叉排序树

性质5 对于具有n 个结点的完全二叉树,如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1 开始顺序编号,则对于任意的序号为i 的结点,有:
(1)如果i>1,则序号为i 的结点的双亲结点的序号为i/2(“/”表示整除);如果i=1,则序号为i 的结点是根结点,无双亲结点。
(2)如果2i≤n,则序号为i 的结点的左孩子结点的序号为2i;如果2i>n,则序号为i 的结点无左孩子。
(3)如果2i+1≤n,则序号为i 的结点的右孩子结点的序号为2i+1;如果2i+1>n,则序号为i 的结点无右孩子。

二叉树的存储

用数组存储

1.先将二叉树补全成完全二叉树

2.将节点依次编号

3.第 i 层的左节点编号为 2i,右节点 2i+1

二叉树、二叉排序树

用链表存储

二叉树、二叉排序树

二叉树的遍历

前序遍历

先遍历本节点,后遍历左子节点,最后遍历右子节点

二叉树、二叉排序树

中序遍历

先遍历左子节点,再遍历本节点,最后遍历右子节点

二叉树、二叉排序树

后序遍历

先遍历左子节点,再遍历右子节点,最后遍历本节点

二叉树、二叉排序树

小结

X序遍历针对的对象是本节点,前序遍历=本节点先遍历,中序遍历=本节点第二遍历,后序遍历=本节点最后遍历。

二叉排序(查找)树

优势

插入、删除、查找性能都不错,构建起来也不是很复杂,性能还很稳定的数据结构

插入节点

如果是空树,则将其作为根节点,否则判断插入节点数据与当前节点数据的大小,如果小于当前节点,则递归遍历左子树,找到对应的位置插入,如果大于当前节点,则递归遍历右子树找到对应的位置插入。

查找节点

查找实现非常简单,和插入类似,依次递归比较就好了,直到直到对应节点,或者返回空,表示没有找到。

删除节点

  • 第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。
  • 第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
  • 第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。(同理,也可以通过待删除节点的左子树中的最大节点思路来实现)

二叉树、二叉排序树

时间复杂度

不论是插入、删除、还是查找,二叉排序树的时间复杂度都等于二叉树的高度,最好的情况当然是满二叉树或完全二叉树,此时根据完全二叉树的特性,时间复杂度是 O(logn),性能相当好,最差的情况是二叉排序树退化为线性表(斜树),此时的时间复杂度是 O(n),所以二叉排序树的形状也很重要,不同的形状会影响最终的操作性能,所以下一篇我们将讨论如何实现平衡的二叉排序树 —— 平衡二叉树。

参考网站

http://c.biancheng.net/cpp/html/974.html

https://xueyuanjun.com/post/20971

 


天蓝, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:二叉树、二叉排序树
喜欢 (0)
[[email protected]]
分享 (0)

您必须 登录 才能发表评论!