算法基础知识之树、二叉树

- 日理万妓 2021-09-30 16:44 338阅读 0赞

### 一、树 ###

![1068826-20170520200736369-1506254333.png][]

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。在计算机科学中，**树**（英语：tree）是一种[抽象数据类型][Link 1]（ADT）或是实作这种抽象数据类型的[数据结构][Link 2]，用来模拟具[有树状结构][Link 3]性质的数据集合。树一般分为两类：

*  无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为[自由树][Link 4]；
 *  有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

### 二、二叉树 ###

![1068826-20170520201219103-623969052.png][]

在[计算机科学][Link 5]中，**二叉树**（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的[树结构][Link 6]。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。

二叉树的第i层至多拥有2^\{i-1\}\}![2^\{i-1\}][2_i-1]个节点数:  2^0   2 ^1   2^2 ........

深度为k的二叉树至多总共有![\{\\displaystyle 2^\{\\begin\{aligned\}k+1\\end\{aligned\}\}-1\}][displaystyle 2_begin_aligned_k_1_end_aligned_-1]个节点数： 1 + 2 + 4 + .... + 2^k = ![\{\\displaystyle 2^\{\\begin\{aligned\}k+1\\end\{aligned\}\}-1\}][displaystyle 2_begin_aligned_k_1_end_aligned_-1]

### 三、满二叉树 ###

![1068826-20170520201554994-1446222156.png][]

二叉树满满当当的，称为满二叉树

###  四、完全二叉树 ###

![1068826-20170520201738166-633200281.png][]

完全二叉树　　　　　　　　　　　　　　　　　　满二叉树

除了最后一层，都长满了。而且是最后一层的右方存在空缺。叫做完全二叉树

转载于:https://www.cnblogs.com/skiler/p/6883072.html

[1068826-20170520200736369-1506254333.png]: /images/20210724/d0270e94b83a4db6abf3723304121dd2.png
[Link 1]: https://zh.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E8%B3%87%E6%96%99%E5%9E%8B%E5%88%A5
[Link 2]: https://zh.wikipedia.org/wiki/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B
[Link 3]: https://zh.wikipedia.org/wiki/%E6%A8%B9%E7%8B%80%E7%B5%90%E6%A7%8B
[Link 4]: https://zh.wikipedia.org/wiki/%E8%87%AA%E7%94%B1%E6%A0%91
[1068826-20170520201219103-623969052.png]: /images/20210724/7dde6fdad003426bb8518cf655159855.png
[Link 5]: https://zh.wikipedia.org/wiki/%E9%9B%BB%E8%85%A6%E7%A7%91%E5%AD%B8
[Link 6]: https://zh.wikipedia.org/wiki/%E6%A0%91%E7%BB%93%E6%9E%84
[2_i-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/de838b503259acc792dd682654445984ea6e4c6d
[displaystyle 2_begin_aligned_k_1_end_aligned_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/f24729d4eae59094b7ed114e09dcbf142f32cde8
[1068826-20170520201554994-1446222156.png]: https://images2015.cnblogs.com/blog/1068826/201705/1068826-20170520201554994-1446222156.png
[1068826-20170520201738166-633200281.png]: https://images2015.cnblogs.com/blog/1068826/201705/1068826-20170520201738166-633200281.png