「学习笔记」树和二叉树

树是具有木质树干及树枝的植物，可存活多年。一般将乔木称为树，主干，植株一，分枝距离地面较高，可以形成树冠。树有很多种。

树，是我们日常生活中不可或缺的重要组成部分。

在程序的世界里，树是数据元素之间具有层次关系的非线性结构。

树 Tree

由n（n≧0）个结点组成的有限集合（树中元素通常称为结点）。

约定条件：

1. 有一个特殊的结点称为根（Root）结点，它只有后继结点，没有前驱结点。
2. 除根以外的其他结点分为m（0 ≦ m ≦ n）个互不相交的集合T0、T1、...、Tm-1，其中每个集合Ti（0 ≦ i ≦ m）也具有树结构，称为根的子树（Subtree）。

上图是 n=10，度为3，高度为3的树

树的术语

1. 父母、孩子与兄弟结点
   1. A 是 B、C、D 的父母（Parent）结点；
   2. B、C、D 是 A 的孩子（Child）结点；
   3. B、C、D 是兄弟（Sibling）结点；E、F 也是兄弟结点，但 E、G 不是；
2. 度
   1. 结点所拥有子树的棵数。例如：A 的度是3，E 的度是0；
   2. 度为0的结点称为叶子（Leaf）结点，叶子结点以外的称为分支结点；
   3. 树的度是指树中各结点度的最大值。
3. 结点层次、树的高度
   1. 结点的层次（Level）属性反应结点处于树中的层次位置。例如：A 的层次是1，B 的层次是2，F、G 不是兄弟，称为同一层上的结点。
   2. 树的高度（Height）是树中结点的最大层次数。
4. 边、路径、直径
   1. 假设树中 X 结点是 Y 结点的父母结点，有序对（X，Y）称为连接这两个结点的分支，也称为边（Edge）；
   2. 假设（X0，X1，...，Xk）（0 ≦ k < n）是由树中结点组成的一个序列，且（Xi，Xi+1）（0 ≦ i < k）都是树中的边，则称为该序列为 X0 到 Xi 的一条路径（Path）。路径长度（Path Length）为路径上的边数。例如：从 A 到 E 的路径是（A、B、E），路径长度为 2；
   3. 从根到叶子结点最长的路径，称为直径（Diameter）。直径的长度为该二叉树的高度-1；
5. 无序树、有序树
   1. 在树的定义中，结点的子树之间没有次序，可以交换位置。称为无序树；
   2. 如果结点的子树，从左至右是有次序的，不能交换位置。则被称为有序树（Ordered Tree）；
6. 森林
   1. m（m ≧ 0）棵互不相交的树的集合。称为森林（Forest）；

二叉树 Binary Tree

由 n（n ≧ 0）个结点组成的有序集合，n = 0 时称为空二叉树；n > 0 的二叉树是由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。

二叉树性质

1. 若根结点的层次是1，则二叉树第i层最多有 2i-1（i ≧ 1）个结点。
2. 在高度为 h 的二叉树中，最多有 2h-1 个结点（h≧0）。
3. 假设一棵二叉树的叶子结点数为n0，2 度结点数为n2，则 n0 = n2 + 1；
4. 满二叉树和完全二叉树
   1. 一棵高度为 h 的满二叉树（Full Binary Tree）是具有2h-1（h≧0）个结点的二叉树。
   2. 一棵具有 n 个结点高度为 h 的二叉树，如果它的每个结点都与高度为 h 的满二叉树中的序号为 0 ∼ n-1 的结点一一对应，则称为完全二叉树（Complete Binary Tree）；
   3. 满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。
   4. 完全二叉树的第 1 ∼ h-1 层是满二叉树，第 h 层不满，并且该层所有结点都必须集中在该层左边的相应位置上；
5. 一棵具有 n 个结点的完全二叉树，其高度 h = （log2n）+ 1；
6. 一棵具有 n 个结点的完全二叉树，对序号为 i （0 ≦ i < n）的结点
   1. 若 i = 0，则 i 为根结点，无父母结点；若 i > 0，则 i 的父母结点序号为（i-1）/ 2；
   2. 若 2i + 1 < n，则 i 的左孩子结点序号为 2i + 1；否则 i 无左孩子；
   3. 若 2i + 2 < n，则 i 的右孩子结点序号为 2i + 2；否则 i 无右孩子；

遍历规则

1. 先根次序（Preorder）：访问根结点，遍历左子树，遍历右子树。
2. 中根次序（Inorder）：遍历左子树，访问根结点，遍历右子树。
3. 后根次序（Postorder）：遍历左子树，遍历右子树，访问根结点。

先根次序：A BDGCEFH

中根次序：DGB A ECHF

后根次序：GDBEHFC A

小结

上周的二叉树问题，让我又一次触摸到了知识盲区。所以，本周的目标是捋一捋树与二叉树的相关知识点。

今天先分享一遍《树与二叉树》的基础学习笔记。

如果想要从初级程序员、中级程序员提升到高级程序员或者架构师的话，那么数据结构是绕不过去的坑。

各种的数字上标、下标、对数 log ...，让我有种回到高等数学的困觉之中。并习惯的挠了挠头（秃）。

这个周末，又一次成功“强迫”自己学习。

感谢各位小伙伴的阅读，这里是一个技术人的学习与分享。