2. 非空二叉树的第i 层最多有2i–1个结点(i1)。
证明(采用归纳法) (1).当i=1时,结论显然正确。非空二叉树的第1层 有且仅有一个结点,即树的根结点. (2).假设对于第j层(1ji–1)结论也正确,即第j层 最多有2j-1个结点. (3).由定义可知, 二叉树中每个结点最多只能有 两个孩子结点。若第i–1层的每个结点都有两 棵非空子树,则第i层的结点数目达到最大.而 第i–1层最多有2i–2个结点已由假设证明,于是, 应有
(2) 二叉链表存储结构 结点的结构如下:
typedef struct node
{ ElemType data;
struct node *lchild,*rchild;
} BTNode, * BiTree;
其中： data表示值域，用于存储对应的数据元素 , lchild和rchild分别表示左指针域和右指针域，用于分 别存储左孩子结点和右孩子结点 ( 即左、右子树的根 结点)的存储位置。
即： k= log2n +1
性质6: 如果对一棵有n 个结点的完全二叉树 (其深度 为log2n + 1) 的结点按层序编号 (从第一层到第log2n + 1 层，每层从左到右)，则对任一结点i (1 i n)，有： (1)若i＝1，则i为根，无双亲，若i>1，则双亲为i/2
#define MaxTree 100 typedef TElemType SqBiTree[MaxTree]; SqBiTree bt;
采用一维数组，按层序顺序依 次存储二叉树的每一个结点。 如下图所示：
4 D 8 H
1 2 B 5 E 9 10 I J
A C 6 F 11 K G 3 7
完全二叉树
练习3：
后序序列：g d b e i h f c a
层次遍历
从第一层开始，同一层从左到右。
一般借助队列进行层次遍历。
B
A
F
ABFCGDEH
D
C
G
E
H
6.3.2 二叉树遍历的递归算法
由二叉树的 先序、中序和后序 遍历过程直接得到如 下三种递归算法如下： void PreOrder(BiTree b) { //先序遍历的递归算法
(2)若2i>n，则i无左孩子，否则i的左孩子为2i。
(3)若2i+1>n，则i无右孩子，否则i的右孩子为2i+1。
1
i=1 只有根结点
2
3
4
5
6
7
8 9 10 11 12 13 14 15
编号i=4 双亲为i/2 =2 左子树为2i=8 右子树为2i+1=9 编号i=5 双亲为i/2 =2 左子树为2i=10 右子树为2i+1=11 i=8,2i>n 无左子树
A 2 B 4 D 8 H I 9 10 J E 11 12 K L 5 6 F 13 14 M N G 15 O C 3 7
满二叉树
若二叉树中最多只有最下面两层的结点的度数可以 小于2,并且最下面一层的叶结点都依次排列在该层最左 边的位置上 , 则这样的二叉树称为完全二叉树。如下图 所示为一棵完全二叉树。同样可以对完全二叉树中每个 结点进行连续编号 , 编号的方法同满二叉树相同。图中 每个结点外边的数字为对该结点的编号。
2 2 i –2 = 2 i – 1
3. 深度为h 的非空二叉树最多有2h –1个结点。 证明: 由性质1可知,若深度为h的二叉树的每一层
的结点数目都达到各自所在层的最大值,则二叉
树的结点总数一定达到最大。即有 20+21+22+…+2i-1+ …+2h-1 = 2h-1
4. 若非空二叉树有n0个叶结点,有n2个度为2的 结点,则 n0=n2+1
1 A C 5 D 8 H I 9 10 J E 11 K 6 F G 3 7 2 B 4
完全二叉树
满二叉树
完全二叉树
6.2.2 二叉树性质
1. 具有n个结点的非空二叉树共有n–1个分支。 证明:
除了根结点以外，每个结点有且仅有一个 双亲结点，即每个结点与其双亲结点之间仅有 一个分支存在， 因此，具有n个结点的非空二 叉树的分支总数为n–1。
练习3：
先序序列：a b d g c e f h i
中序遍历
若被遍历的二叉树非空, 则：
B C D E
A F G H
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。
中序序列：BDCEAGHF
练习1：
中序序列：a + b * c - d - e / f
练习2：
中序序列：d f e b a g c
A B C
A
B F
∧
∧
C
D G
E
D
∧
E
∧
∧
F
∧
∧
G
∧Hale Waihona Puke (a)(b)二叉树及其二叉链表存储结构
两种存储结构的转换
A B C A
B F
∧
∧
C
D G
E
D
∧
E
∧
∧
F
∧
∧
G
∧
(a)
(b)
ABCD
1 2 3 4 5
E F
6 7 8 (c)
G
9 10 11 12 13 14 15
下面根据二叉树的顺序存储结构画出其二叉链表存储结构
证明:
设该二叉树有n1个度为1的结点,结点总数 为 n, 有 n=n0+n1+n2 --------(1) 设二叉树的分支数目为B，根据性质1，有 B=n-1 -------- (2) 这些分支来自度于为1的结点与度为2结点,即： B=n1+2n2 ---------(3) 联列关系(1),(2)与(3),可得到 n0=n2+1
递归定义
二叉树有五种基本形态 , 如下图所示 , 任何复杂 的二叉树都是这五种基本形态的复合。
下面两种说法正确与否? 应该怎样说才合适?
1. 度为2 的树 是二叉树。
结论:子树有严格的左右 之分且度≤2的树是二叉树。
2. 具有三个结点的 树 可以有以下五种形态:
结论:具有三 个结点的树只有 两种形态。
通过性质6把非线性结构轻易转化成了线性结构。
6.2.3
二叉树存储结构
二叉树的顺序存储结构 二叉树的链式存储结构
(1) 二叉树的顺序存储结构
1. 完全二叉树的顺序存储结构
根据完全二叉树的性质6 ,对于深度为h 的完全二 叉树, 将树中所有结点的数据信息按照编号的顺序依 次存储到一维数组BT[1:2h-1]中,由于编号与数组下标 一一对应, 该数组就是该完全二叉树的顺序存储结构。
J
I
BT[1:15]
A B C D E F G H J I
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
结论
对于一般二叉树, 只须在二叉树中“添加”一 些实际上二叉树中并不存在的“虚结点” ( 可以认 为这些结点的数据信息为空), 使其在形式上成为一 棵“完全二叉树”, 然后按照完全二叉树的顺序存 储结构的构造方法将所有结点的数据信息依次存放 于数组BT[1: 2h -1]中。
（2）如何遍历二叉树？
二叉树是一种非线性结构，而遍历的结果是一个线性 的结点序列。 D 考虑二叉树的结构… 根据二叉树的结构，分为三部分： R L 左子树 L D 根结点 R 右子树
A B D
G E C F
（3）遍历二叉树的方法
先序遍历 DLR 中序遍历 LDR
后序遍历 LRD
由于左右子树也是二叉树，属于递归结构，所以常
结点数为3的二叉树有三种形态：
二叉树的主要术语
左 孩子 双亲
根
右 孩子
叶子
叶子 是没有孩 子的结点。
二叉树的表示
从定义看到，二叉树是一种特殊的树，其表
示法也与树的表示法一样，有树形表示法、文氏
图表示法、凹入表示法和括号表示法等。
两种特殊形态的二叉树
在一棵二叉树中 , 如果所有分支结点都有左孩子 结点和右孩子结点 , 并且叶子结点都集中在二叉树的 最下一层，这样的二叉树称为满二叉树。下图所示就 是一棵满二叉树。可以对满二叉树的结点进行连续编 号 , 约定编号从树根为 1 开始 , 按照层数从小到大、同 一层从左到右的次序进行。图中每个结点外边的数字 为对该结点的编号。 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F GHI J K
利用性质6实现线性结构和非线性结构的灵活转换。
2.一般二叉树的顺序存储结构
通过虚设部分结点，使其变成相应的完全二叉树。
1
A
2
3
B
5
C E
6 7
“完全二叉树”
G
4 8
D
9
10
F
13
H
11 12
visit(b->data); //访问根结点
InOrder(b->rchild);
}
}
void PostOrder(BiTree b) { if (b!=NULL) { PostOrder(b->lchild);
//后序遍历递归算法
PostOrder(b->rchild);
visit(b->data); //访问根结点
}
}
T
+ * ∧ a ∧ ∧ b ∧
-
/
/\ d /\
∧ e ∧
∧ c ∧
a*(b-c)+d/e