二、二叉树的性质 1.性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1). 分析：计算二叉树某一层的结点数。这里的"至多"指的是，当该二叉树为满二叉树时，由数学归纳法论证可知，第i层有最多可以有2^(i-1)个结点。 2.性质2：深度为k的二叉树至多有2^k-1个结点(k>=1) 分析：计算二叉树结点总数。这里"深度为k"指有k层的二叉树，当该二叉树为满二叉树时，由数学归纳法论证可知，该二叉树至多有2^k-1个结点。 3.性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则no=n2+1. 分析：一颗二叉树主要有n0个度为0的叶子结点、n1个度为1的结点、n2个度为2的结点组成。因此，该二叉树的结点总数n=n0+n1+n2(方程1).从二叉树中连接线数可知，由于根结点只有分支出去，没有分支进入，所有分支线总数减去1，即二叉树分支线总数=n-1=n1+2n2(方程2)(其中n1为度为1的结点数、n2为度为2的结点数)。联立方程得：n0=n2+1. 4.性质4：具有n个结点的完全二叉树的深度为「log2^n」+1 (「x」表示不大于x的最大整数)。 分析：由性质2我们可以知道，深度为k的满二叉树的结点数n=2^k-1。由其倒推得到满二叉树的度数为k=log2^(n+1)。由于完全二叉树是满二叉树的一个子集，它的结点数一定少于等于同样度数的满二叉树的结点数2^k-1，但一定多于2^(k-1)-1。即满足2^(k-1)-1
(1)如果i=1,则结点是i的二叉树的根，无双亲；如果i<1，则其双亲是结点[i/2]; (2)如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i; (3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1. 三、二叉树的存储结构 1.二叉树顺序存储结构 由于二叉树是一种特殊的树，使得顺序存储结构得以实现。二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。(k个结点，需要分配2^k-1个存储单元空间) 注意：顺序存储结构一般只用于完全二叉树。
2.二叉链表
(1)核心思想 二叉树每个结点最多有两个孩子，所有为它设计一个数据域和两个指针域，用来指向该结点的左右孩子，我们称为这样的链表为二叉链表。
(2)结点结构
其中，data为数据域，lchild和rchild都是指针域，分别存放指向左右孩子的指针 (3)二叉链表的结点结构定义代码 /*二叉树的二叉链表结点结构定义*/ typedef struct BiTNode /*结点结构*/ { TElemtype data; //结点数据 struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; (4)结构实例 >>二叉链表
>>三叉链表：parent指针域存放指向结点双亲的指针
