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;
本文标题：5.4 二叉树的性质及存储结构
本文链接：https://www.haomeiwen.com/subject/walcnrtx.html
网友评论