编程之禅
0%

二叉树的性质和存储结构

发表于 更新于 分类于 阅读次数： Disqus：

二叉树的性质

性质1: 在二叉树的第i层上至多有2i-1个节点(i>=1)

性质2: 深度为k的二叉树至多有2k-1个节点(k>=1)

性质3: 对任何一棵二叉树T,如果其终端节点数为n0，度为2的节点数为n2,则n0=n2+1

满二叉树：深度为k且含有2k-1个节点的二叉树

满二叉树.png

完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应，称之为完全二叉树

完全二叉树的特点：

（1）叶子节点只可能出现在层次最大的两层出现

（2）对任一节点，若其右分支下的子孙的最大层数为l，则其左分支下的子孙的最大层数必为l或l+1

完全二叉树.png

性质4:具有n个节点的完全二叉树的深度为⎣⎦+1

性质5：如果对一棵有n个节点的完全二叉树的节点按层序编号，每层从左到右

(1) 如果i == 1，则节点i是二叉树的根；如果i > 1, 则其双亲parent(i)是节点⎣i/2⎦

(2) 如果2i>n，则节点i无左孩子(节点i为叶子节点)，否则其左孩子lchild(i)是节点2i

(3) 如果2i+1>n，则节点i无右孩子；否则其右孩子rchild(i)是节点2i+1

树节点.png

二叉树的存储结构

顺序存储结构

1
2
3
4
5
//------二叉树的顺序存储表示---------
#define MAXSIZE 100  //存储100个元素
typedef TElemType SqBiTree[MAXSIZE];  
//含有MAXSIZE个元素，类型为TElemType的数组，并用SqBiTree来作为定义数组的别名
SqBiTree bt;    //bt为含有MAXSIZE个元素，类型为TElemType的数组

用数组实现：若数组元素大于0，则节点存在，等于0则代表节点不存在

满二叉树可表示为： 1 2 3 4 5 6 7 8 9 10 11 12

一般二叉树可表示为：1 2 3 4 5 0 0 0 0 6 7

以上两树分别对应以下a和b

满二叉树和普通树.png

由此可见，顺序存储结构仅适用于完全二叉树。因为最坏情况下，一个深度为k且只有k个节点的单支树却需要长度为2k-1的一维数组。

链式存储结构

1
2
3
4
5
//-------二叉树的二叉链表存储表示----------
typedef struct BiTNode{
  TElemType data;                     //节点数据域
  struct BiTNode *lchild,*rchild;     //左右孩子指针
}BiTNode,*Bitree;

根据二叉树的定义，二叉树的节点由一个数据元素和分别指向其左，右子树的两个分支构成，则表示二叉树的链表中的节点至少包含三个域：数据域和左，右指针域。

有时为了方便找到双亲，会额外增加一个指向其双亲的指针域，此种链表称为三叉链表。

链表的头指针指向二叉树的根节点。根据数学计算，含有n个节点的二叉链表中有n+1个空链域，可以利用这些空链域存储一些有用信息，比如前驱和后继。