Horace Chan

树与二叉树

树（Tree） 是 n(n>=0) 个结点的有限集。n=0 时称为空树。 在任意一颗非空树中： 1. 有且仅有一个特定的称为根(Root)的结点。 2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树

定义

树（Tree） 是 n(n>=0) 个结点的有限集。n=0 时称为空树。 在任意一颗非空树中：

  1. 有且仅有一个特定的称为根(Root)的结点。
  2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

CAUTION: 树的定义

  1. n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
  2. m>0时，子树的个数没有限制，但它们一定是互不相交的。

树是一种递归的数据结构，即树在定义中又用到了自身

基本术语

树的基本术语图示 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。 树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。 度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。 结点的深度、高度和层次。 结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。 结点的深度是从根结点开始自顶向下逐层累加的。 结点的高度是从叶结点开始自底向上逐层累加的。 树的高度(或深度)是树中结点的最大层数。图中树的高度为4。 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。 注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。 森林。森林是m (m ≥ 0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

结点的度：树中每个节点的子节点数目的最大值 叶子节点是树结构中没有子节点的终端节点，也称终端结点或Leaf Node 对于二叉树来说，度为0的结点（即叶子结点）总是比 度为2的结点多一个

树的性质

树具有如下最基本的性质：

  1. 树中的结点数等于所有结点的度数加1.
  2. 度为 m 的树中第 i 层上至多有 m^i-1 个结点（ i ≥ 1 ）
  3. 高度为 h 的 m 叉树至多有 (m^h - 1)/(m - 1) 个结点。
  4. 具有 n 个结点的 m 叉树的最小高度为 ⌈ log_m(n(m - 1) + 1) ⌉ 。

二叉树

定义

每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒 二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。二叉树的5种基本形态

特殊二叉树

1. 斜树

  • 只有左子树的二叉树叫左斜树。
  • 只有右子树的二叉树叫右斜树。 这两者统称为斜树。

2. 满二叉树

  • 所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上

一棵高度为 h，且含有 2^h-1 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2 。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为1)起，自上而下，自左向右。这样，每个结点对应一个编号,对于编号为i的结点，若有双亲，则其双亲为i/2,若有左孩子，则左孩子为2i;若有右孩子，则右孩子为2i+1。满二叉树图示

3. 完全二叉树

高度为h、有 n 个结点的二叉树，当且仅当其每个结点都与高度为 h 的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

HELP: 编号顺序 从左到右，从上到下

一颗具有n个结点的二叉树按层编号，如果编号为i(1≤ i ≤ n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

如图所示。其特点如下:完全二叉树图示

NOTE 完全二叉树是 从上到下 一层一层 逐层排满的

二叉树遍历

定义

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

访问次序

二叉树的访问次序可以分为四种：

  1. 前序遍历 根结点 > 左子树 > 右子树
  2. 中序遍历 左子树> 根结点 > 右子树
  3. 后序遍历 左子树 > 右子树 > 根结点
  4. 层序遍历 仅仅需按层次遍历就可以

图解

二叉树遍历图示

前序遍历

定义

前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

TIP 根 → 左 → 右

遍历流程
  1. 从根结点出发，则第一次到达结点A，故输出A；
  2. 继续向左访问，第一次访问结点B，故输出B；
  3. 按照同样规则，输出D，输出H；
  4. 当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
  5. I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
  6. 向E左子树，故输出J；
  7. 按照同样的访问规则，继续输出C、F、G；
遍历结果

前序遍历输出为：ABDHIEJCFG

中序遍历

定义

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

TIP 左 → 根 → 右

ATTENTION: Skill 无敌“绕树描边法”（轮廓法）

如果你觉得补空法每次都要在脑子里写字太慢，这里有一个纯视觉的“神技”。

把这棵树想象成海里的一个岛屿。你开着一艘小船，从根节点的最左边出发，紧贴着树的轮廓，逆时针绕一圈。

针对每个节点，我们在它的左侧、正下方、右侧各画一个打卡点：

  • 前序遍历： 小船第一次路过节点（经过它的左侧）时，拍照打卡。
  • 中序遍历： 小船第二次路过节点（经过它的正下方，也就是从左子树回来时）时，拍照打卡。
  • 后序遍历： 小船第三次路过节点（经过它的右侧，马上要离开它往上走时）时，拍照打卡。
遍历流程
  1. 从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
  2. 到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
  3. H右子树为空，则返回至D，此时第二次到达D，故输出D；
  4. 由D返回至B，第二次到达B，故输出B；
  5. 按照同样规则继续访问，输出J、E、A、F、C、G；
遍历结果

中序遍历输出为：HDIBJEAFCG

后序遍历

定义

后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

TIP 左 → 右 → 根

ATTENTION: Skill “剪葡萄法”（强推 🌟）

把这棵二叉树想象成一串倒挂的葡萄。规则只有一个：你只能剪下底端悬空的葡萄。如果一颗葡萄下面还挂着别的葡萄，你就不能剪它。 而且我们要养成习惯：先看左边，再看右边。

拿一把剪刀，我们开始从下往上“咔嚓”：

  1. 看最左边： D 下面什么都没有，剪下 D。

  2. 往上看 B： 不能剪，因为右边还挂着一大串 E。

  3. 往下看 E： 不能剪，挂着 G 和 H。先看左边的 G，剪下 G。再看右边的 H，剪下 H。

  4. 再看 E： 它的左右 G 和 H 都被剪掉了，E 悬空了！剪下 E。

  5. 再看 B： 它的左右 D 和 E 都没了，B 悬空了！剪下 B。 (此时左半边全部剪完，顺序是：D, G, H, E, B)

  6. 看右半边 C： 不能剪，挂着 F。

  7. 看 F： 不能剪，挂着 I 和 J。先剪左边的 I，再剪右边的 J。

  8. 再看 F： I 和 J 没了，剪下 F。

  9. 再看 C： F 没了，C 悬空了，剪下 C。

  10. 最后看 A： 光杆司令，剪下 A。

连起来，后序遍历结果一秒得出：D, G, H, E, B, I, J, F, C, A。

INFO: Skill 反向先序法”（降维打击 🚀）

这是一个利用规律的“黑客解法”，特别适合在考试或做题时快速得出答案，保证 100% 正确。

你还记得前序遍历的口诀是“根 -> 左 -> 右”吗？ 如果我们稍微改一下，弄一个“伪前序遍历”，口诀变成“根 -> 右 -> 左”。 神奇的事情发生了：把你得到的“伪前序遍历”完全倒写过来，就是完美的后序遍历！

遍历流程
  1. 从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
  2. 到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
  3. H右子树为空，则返回至H，此时第三次到达H，故输出H；
  4. 由H返回至D，第二次到达D，不输出D；
  5. 继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
  6. 返回至D，此时第三次到达D，故输出D；
  7. 按照同样规则继续访问，输出J、E、B、F、G、C，A；`
遍历结果

后序遍历输出为：HIDJEBFGCA

层次遍历

遍历流程

层次遍历就是按照树的层次自上而下的遍历二叉树。

遍历结果

层次遍历输出为：ABCDEFGHIJ