二叉树的性质
1：在二叉树的第i层上至多有2e(n-1)个结点（i>=1）
2：深度为k的二叉树至多有2e(k)-1个结点（k>=1）
3：二叉树中，终端结点数n0与度为2的结点数n2有如下关系：n0=n2+1（叶结点个数比度为2的结点个数多1个）
完全二叉树中
每个结点的左子数深度-右子数深度=0或1
结点个数n满足2e(k-1)-1结点数为n的完全二叉树，其深度为(log2(n))(下取整)+1
结点编号为i：
i=1：此结点为树根。
i>1：其双亲为i/2(下取整)
2i>n：此结点为叶结点，否则结点的左孩子为2i
2i+1>n：结点i无右孩子。否则其右孩子为2i+1
以上性质在二叉树顺序存储结构中很有用。
链式存储
含有n个结点的二叉链表中，有n+1个空链域
在线索二叉树中可以用到这n+1个空链域，存放结点的前驱和后继信息。（当然，每个节点还要加上两个tag域，还要另加一个头指针）
阅读(1909) | 评论(0) | 转发(0) |
