二叉树的性质
性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。
性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。
性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树和完全二叉树
一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。
完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。
完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。
完全二叉树的特点：
若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。
性质4：n个结点的完全二叉树深度为：ë㏒2nû +1。
其中符号： ëxû表示不大于x的最大整数。
éxù 表示不小于x的最小整数。
性质5：若对一棵有n个结点的完全二叉树(深度为ë㏒2nû +1)的结点按层（从第1层到第ë㏒2nû +1
层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结点：
⑴ 若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是 ëi/2û 。
⑵ 如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
⑶ 如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)