前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

6.5 二叉树的性质

6.5.1二叉树性质

性质1:在二叉树的第i层上至多有2^（i-1）个结点(i≥1)。(带入即可理解)

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

如果有一层，至多有1 = 2 的 0次方 - 1 个结点

如果有二层，至多有1 + 2 = 3 = 2 的平方 - 1 个结点

...

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

性质4:具有n个结点的完全二叉树的深度为[log2n]+1 (Lx]表示不大于x的最大整数)。

这个其实就是性质二的倒数，反过来求k的值的

性质5:如果对一棵有n个结点的完全二叉树(其深度为log2n]+1) 的结点按层序编号(从第1层到第log2n]+1层，每层从左到右)，对任一结点i (1≤i≤n)有:

1.如果i=1，则结点i是二叉树的根，无双亲;如果i>1,则其双亲是结点li/2」。

2.如果2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。

3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。

如下图

对于第一条来说是很显然的，i=1 时就是根结点。i>1 时，比如结点7,它的双亲就是l7/2]=3,结点9,它的双亲就是[9/2]=4

第二条，比如结点6,因为2X6=12超过了结点总数10,所以结点6无左孩子，它是叶子结点。同样，而结点5,因为2X5=10正好是结点总数10,所以它的左孩子是结点10

第三条，比如结点5,因为2X5+1=11,大于结点总数10,所以它无右孩子。而结点3，因为2X3+1=7小于10,所以它的右孩子是结点7

6.6 二叉树的存储结构

6.6.1二叉树的顺序存储

如果有一颗深度为k的右斜树，它有k个结点，却要分配2的k次方减1个存储单元，他会很浪费如下图，所以顺序存储结构一般用于完全二叉树

6.6.2 二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表

结构如图所示：

代码实现如下：

/*二叉树的二叉链表结点结构定义*/
 typedef struct BiTNode /* 结点结构*/
 {
     TElemType data;     /*结点数据*/
     struct BiTNode *1child, *rchild; /*左右孩子指针*/
 } BiTNode, *BiTree;

结构下图：

如果有需要，还可以增加一个指向其双亲的指针域，那样就称之为三叉链表，很灵活要学会自己变通~~~~