Java源码集合类TreeMap学习1——数据结构2

喜欢ヅ旅行 2022-07-03 15:27 147阅读 0赞

**二叉树的定义**

二叉树（Binary Tree）是另一种树型结构，它的特点是每个节点至多只有两颗子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次数不能任意颠倒。如下图。

![Center][]

**二叉树的性质**

**性质1** 在二叉树的第i层上至多有2i-1个节点(i>=1)。

证明（归纳法）：

1. i = 1时，显然节点数等于1。

2. 假定所有的j，1<=j<i，命题成立，即第j层上至多有2^j-1个节点。那么，可以证明j = i时命题也是成立。

3.有归纳法假设：第i-1层上至多有2^i-2个节点。由于二叉树的每个节点的度至多为2，故在第i层上的最大节点数为第i-2层上的最大节点数的2倍，即2\*2^i-2=2^i-1。

**性质2** 深度为K的二叉树至多有2k\-1个节点(k>=1)。

**性质3 **对任何一颗二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0 = n2 + 1。

证明：

1. 设n1为二叉树T中度为1的节点数，则二叉树T总节点数为：n = n0 + n1 + n2。

2. 设二叉树T中所有分支个数为B，则n = B + 1。由于度为1的节点是有一个分支，度为的2的节点是有2个分支，所以有：B = n1 + 2n2。于是可得出：

n = n1 + 2n2 + 1。

3. 由：n = n0 + n1 + n2和n = n1 + 2n2 + 1得：n0 = n2 + 1。

**满二叉树**

一棵深度为k且有2k \- 1个节点的二叉树称为满二叉树。

**完全二叉树**

满二叉树共有n个节点，按照有顺序的二叉树从根节点开始编号为1到n进行编号，假如有一棵二叉树节点总数为N（N>=1 && N <= n）的按顺序从1开始编号到N，且1到N这个顺序号在1到n中是依次对应的，那么这棵树就是完全二叉树。如下图。

![Center 1][]

**性质4** 具有n个节点的完全二叉树的深度为：|log2^n| + 1。

证明：

假设深度为k，则根据性质2和完全二叉树的性质有：

2^(k-1) - 1 < n <= 2^(k) - 1 或 2^(k - 1) <= n < 2^k。

于是k - 1 <= log2^n < k，因为k是整数，所以 k = |log2^n| + 1。

**性质5** 如果对一棵有n个结点的完全二叉树（其深度为|log2^n| + 1）的结点按层次编号（从第1层到|log2^n| + 1层，每层从左到右），则对任意结点 i（1 <= i <= n），有

（1）如果 i = 1， 则结点i是二叉树的根，无双亲；如果 i > 1，则其双亲PARENT(i)是结点 | i / 2 |。

（2）如果 2i >= n，则结点i 无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。

（3）如果 2i + 1 > n，则结点 i 无右孩子；否则其右孩子RCHILD(i)是结点 2i + 1。

**二叉树的存储结构**

1.顺序存储结构，就是存储在一组数组中。

2.链式存储结构，分为：二叉链表和三叉链表。三叉链表中的结点至少包含3个域：数据域和左、右指针域。

二叉链表的结点结构包含：数据域和左、右指针域。

三叉链表的结点结构包含：数据域、双亲节点指针域和左、右指针域。如下图。

![Center 2][]

[Center]: /images/20220618/e72c949f9ee84476b3bc938565bd0f7e.png
[Center 1]: /images/20220618/e3d806f13aff4dee93d322f6524df589.png
[Center 2]: /images/20220618/3c16b06fdf474e77afcdb67ee82e63ad.png

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java源码集合类TreeMap学习1——数据结构1

写在前面的话 TreeMap类的底层实现用到了数据结构——树(红黑树)，红黑树一直没有彻底搞清楚到底是怎么实现的，因为看到了它就想放弃，觉得不去理解清楚好像也没有多大影响。但

Myth丶恋晨/ 2022年10月01日 04:55/ 0 赞/ 169 阅读

相关 Java源码集合类LinkedHashMap学习1

LinkedHashMap类简介(jdk 1.7.0\_67) LinkedHashMap类继承了HashMap类，也就是LinkedHashMap类的功能几乎和Has

小咪咪/ 2022年09月28日 13:28/ 0 赞/ 165 阅读

相关 Java源码集合类HashMap学习1

Java中集合类HashMap是存储键值(key,value)对为元素的集合，键和值都是以类类型来存储，通过键(key)来获得对应的值(value)。使用Has

柔光的暖阳◎/ 2022年07月12日 08:53/ 0 赞/ 166 阅读

相关 Java源码集合类TreeMap学习1——数据结构2

二叉树的定义二叉树（Binary Tree）是另一种树型结构，它的特点是每个节点至多只有两颗子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次数不能

喜欢ヅ旅行/ 2022年07月03日 15:27/ 0 赞/ 148 阅读

相关 Java源码集合类TreeMap学习1——数据结构4平衡二叉树的旋转

平衡二叉树的旋转理解清楚平衡二叉树的概念。具体如何旋转是平衡二叉树保持继续平衡的，可以参考如下的两个博客和一本书。 https://www.tutorialspoint.

分手后的思念是犯贱/ 2022年06月17日 09:49/ 0 赞/ 113 阅读

相关 Java源码集合类TreeMap学习1——数据结构3二叉树创建代码

二叉树的二叉链表存储结构二叉树的二叉链表存储结构，一个结点结构包含三个域：数据域、左、右指针域。如下图所示。 ![Center][] 二叉树的遍历知识参考：

野性酷女/ 2022年06月17日 09:13/ 0 赞/ 122 阅读

相关 Java源码集合类TreeMap学习1——数据结构4平衡二叉树创建代码

平衡二叉排序树上插入一个新的元素递归[算法][Link 1]，还是比较复杂的，特别是代码的实现上想要理解还是要动手去一步步去手动执行代码。个人理解这个算法和看示例代码也是费了很

﹏ヽ暗。殇╰゛Y/ 2022年06月16日 11:29/ 0 赞/ 124 阅读

相关 Java源码集合类TreeMap学习1——数据结构5红黑树

红黑树本质上一棵平衡二叉树。参考：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/mas

忘是亡心i/ 2022年06月14日 05:10/ 0 赞/ 144 阅读

相关 Java源码集合类TreeMap学习2

通过分析 JDK 源代码研究 TreeMap 红黑树算法实现参考：https://www.ibm.com/developerworks/cn/java/j-lo-tree/

古城微笑少年丶/ 2022年06月13日 21:13/ 0 赞/ 216 阅读

相关 Java集合-TreeMap源码

数据结构红黑树实现了NavigableMap，是一个key有序的Map 源码成员变量 private final Comparat

桃扇骨/ 2022年04月18日 06:18/ 0 赞/ 250 阅读