基本算法|图解各种树（一）

01

—

二叉树

节点的度数不超过2的树，称为二叉树，如下图所示：

02

—

单链和满二叉树

含n个节点，高度为h的二叉树中，满足如下关系：

h < n < 2^(h+1)

当 n = h+1 时，退化为一条单链，

当 n = 2^(h+1) -1 时，是一棵满二叉树，如下图所示：

03

—

真二叉树

节点的出度为0或2，不能为1的二叉树，称为真二叉树。

为了构造真二叉树，需要虚拟一些节点，是画蛇添足吗？当然不是，为了代码实现更为简洁明了。

04

—

二叉树实现多叉树

二叉树明明是多叉树的特例，怎么可能用二叉树描述多叉树呢？这出乎意料，但是的确是可能的，就像是0~0.1的实数和整个轴上的实数一样多相似。

条件：在有根且有序的前提下。

方法：长子-兄弟法

多叉树如下：

长子-兄弟表示后：

整理上图：

结论，因为多叉树可以转化为二叉树，所以只需研究二叉树即可。