数据结构树之易忘知识点

一、
二叉树性质

性质1&＃xff1a;在二叉树的第i层上至多有2^(i-1)结点(i >&＃61;1)。

性质2&＃xff1a;深度为k的二叉树至多2^k-1个结点(k>&＃61;1)。

性质3&＃xff1a;对任何一棵二叉树T&＃xff0c;如果其终端结点数为n0&＃xff0c;度为2的结点数为n2&＃xff0c;则n0&＃61;n2&＃43;1。
三叉树&＃xff1a; n0&＃61;1&＃43;n2&＃43;2n3
四叉树&＃xff1a; n0&＃61;1&＃43;n2&＃43;2n3&＃43;3n4
K叉树&＃xff1a; n0&＃61;1&＃43;n2&＃43;2n3&＃43;…&＃43;(k-1)nk

性质4 : 具有n个结点的完全二叉树的深度k为[log2n]&＃43;1。

二、
满二叉树&＃xff1a;一棵深度为k且有2k-1个结点的二叉树。
特点&＃xff1a;每一层上的结点数都是最大结点数

完全二叉树&＃xff1a;深度为k&＃xff0c;有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时&＃xff0c;称为完全二叉树。

三、
由遍历序列恢复二叉树&＃xff1a;由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。

四、
树和二叉树之间的转换
森林和二叉树之间的转换