5.4 二叉树的性质及存储结构

性质

性质1：在二叉树的第i层节点上，最多有 2^(i-1) 个节点

性质2：深度为k的二叉树，最多有2^k -1 个节点

性质3：对于二叉树，如果叶子节点数为n0，度为2的节点数为n2，则n0=n2+1

性质4：具有n个节点的完全二叉树的深度为 [logN]+1

性质5： 对于任何一个有n个节点深度为logN的完全二叉树，对任意一节点（1<=i<=n）,有

• 如果i=1.则节点i为根节点；如果i>1,则双亲为 i/2
• 如果2i>n,则节点i为叶子节点；否则，2i为i的左孩子；
• 如果2i+1>n，则节点i为无右孩子；否则，2i+1为i的右孩子；

满二叉树和完全二叉树

满二叉树 深度为k，节点数为2^k-1的二叉树

完全二叉树：深度为k具有n个节点，每一个节点的编号都和深度为k的满二叉树的1-n个节点编号一一对应

二叉树的存储结构

顺序存储

链表存储

二叉链表

三叉链表

typedef struct{
  TElementType data;
  TreeNode *left,*right,*parent;
} TreeNode;