多叉树

· · 个人记录

二叉树的前序，中序，后序遍历；

二叉树结点的结论:

叶子节点=度为二的结点的数量+1

总结点等于度为0，1，2的结点的数量的和

树是由n个元素组成的有限集合，其中： （1）每个元素称为结点（node）。

（2）有一个特定的结点，称为根结点或树根（root）。

（3）除根结点外，其余结点能分成m个互不相交的有限 集合T0, T1, T2, …, Tm-1。其中每一个子集又都是一棵 树，这些集合称为这棵树的子树。

m叉树：结点的度最多为m的树，可以称为m叉树， 最经典的是二叉树，指度不超过2的树，我们把二叉树上 每个结点的左右两个结点分别称为左儿子、右儿子， 对应的子树分别称为左子树、右子树。

二叉树左儿子组成的树称为这个点的左子树

二叉树右儿子组成的树称为这个点的右子树

二叉树的性质：

【性质1】在二叉树的第i层上最多有2𝑖−1个结点（i≥1）。

【解释】我们按层推一下就可以发现，每层结点数量都是2的次 幂，第i层最大结点数量是第i-1层最大结点数量的两倍。

【性质2】深度为k的二叉树最多有2𝑘 − 1个结点。

【解释】利用性质1，将每一层的结点数量上限求和得出。

我们假设𝑛个结点的二叉树中，度为0/1/2的结点数量分 别为𝑛0、𝑛1、𝑛2，那么有：

【性质3】𝑛 = 𝑛0 + 𝑛1 + 𝑛2.

【性质4】𝑛 = 𝑛1 + 2 × 𝑛2 + 1.

【性质5】𝑛0 = 𝑛2 + 1

上述性质也可以推广到𝑚叉树。