(a)
空二叉树
A
A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树图 6.8 二叉树的 5种形式二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图 6.8列出二叉树的 5种基本形态，图
6.8(C) 和图 6.8（ d）是不同的两棵二叉树。
6.3 二叉树完全二叉树
D
C
GFE
B
A
三、二叉树的存储结构
⒈ 顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素,结点的相对位置蕴含着结点之间的关系。
bt[3]的双亲为 └ 3/2┘ =1，
即在 b t[1]中；
其左孩子在 bt[2i]=bt[6]中；
其右孩子在 bt[2i+1]=bt[7]中。
1 2 3 4 5 6 7 8 9 10 11
A B C D E F G 0 0 0 0
6.3 二叉树这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，
可能造成存储空间的浪费。
D
二叉树
C
GF
E
B
A
1 2 3 4 5 6 7 8 9 10 11
A B C D E 0 0 0 0 F G 0 0 0 0
一般二叉树也按完全二叉树形式存储,没结点处用 0表示。
6.3 二叉树例如，深度为 k，且只有 k个结点的右单枝树 ( 每个非叶结点只有右孩子 )，需 2k-1个单元，即有 2k-1-k
个单元被浪费。
1
k
6.3 二叉树
⒉ 链式存储结构设计不同的结点结构，可以构成不同的链式存储结构。常用的有：
二叉链表
三叉链表
线索链表 用空链域存放指向前驱或后继的线索二叉树的二叉链表存储表示
Typedef struct BiTNode {
TelemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
6.3 二叉树二叉链表的结点结构
lchild data rchild
D
二叉树
C
E
B
A A
CB
D E ∧∧∧∧
∧ ∧
二叉链表
6.3 二叉树三叉链表的结点结构
lchild data parent rchild
D
二叉树
C
E
B
A A
CB
D E ∧∧∧∧
∧ ∧
∧三叉链表
6.3 二叉树性质 6,含有 N个结点的二叉链表中，有 N+1个空链域。
证明,设二叉树中度为 i的结点数为 ni，二叉树中总结点数为 N，因为二叉树中所有结点均小于或等于 2，所以有：
N＝ n0＋ n1＋ n2 ①
又由二叉树的链式存储结构定义可知，度为 1的结点的空链域个数为 1，度为 2的结点的空链域个数为 0，度为 0的结点的空链域个数为 2，设含有 N个结点的二叉树的二叉链表中空链域的个数为 M，则有：
M＝ 2* n0＋ 1*n1＋ 0*n2= 2* n0＋ n1 ②
又因为,n0＝ n2＋ 1 ③
由①、②、③ 可得：
M＝ 2* n0＋ n1
＝ n0+n1+n0
＝ n0+n1+n2+1
＝ N+1 命题得证。
6.4 遍历二叉树和线索二叉树一、遍历二叉树遍历二叉树是指 按一定的规律 对二叉树的每个结点,访问 且仅访问一次的处理过程。
访问 是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。
遍历的次序,若设二叉树根为 D，左子树为 L，右子树为 R，并限定先左后右，则有以下三种遍历次序：
LDR 中序遍历 ； LRD 后序遍历 ； DLR 先序遍历
空二叉树
A
A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树图 6.8 二叉树的 5种形式二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图 6.8列出二叉树的 5种基本形态，图
6.8(C) 和图 6.8（ d）是不同的两棵二叉树。
6.3 二叉树完全二叉树
D
C
GFE
B
A
三、二叉树的存储结构
⒈ 顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素,结点的相对位置蕴含着结点之间的关系。
bt[3]的双亲为 └ 3/2┘ =1，
即在 b t[1]中；
其左孩子在 bt[2i]=bt[6]中；
其右孩子在 bt[2i+1]=bt[7]中。
1 2 3 4 5 6 7 8 9 10 11
A B C D E F G 0 0 0 0
6.3 二叉树这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，
可能造成存储空间的浪费。
D
二叉树
C
GF
E
B
A
1 2 3 4 5 6 7 8 9 10 11
A B C D E 0 0 0 0 F G 0 0 0 0
一般二叉树也按完全二叉树形式存储,没结点处用 0表示。
6.3 二叉树例如，深度为 k，且只有 k个结点的右单枝树 ( 每个非叶结点只有右孩子 )，需 2k-1个单元，即有 2k-1-k
个单元被浪费。
1
k
6.3 二叉树
⒉ 链式存储结构设计不同的结点结构，可以构成不同的链式存储结构。常用的有：
二叉链表
三叉链表
线索链表 用空链域存放指向前驱或后继的线索二叉树的二叉链表存储表示
Typedef struct BiTNode {
TelemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
6.3 二叉树二叉链表的结点结构
lchild data rchild
D
二叉树
C
E
B
A A
CB
D E ∧∧∧∧
∧ ∧
二叉链表
6.3 二叉树三叉链表的结点结构
lchild data parent rchild
D
二叉树
C
E
B
A A
CB
D E ∧∧∧∧
∧ ∧
∧三叉链表
6.3 二叉树性质 6,含有 N个结点的二叉链表中，有 N+1个空链域。
证明,设二叉树中度为 i的结点数为 ni，二叉树中总结点数为 N，因为二叉树中所有结点均小于或等于 2，所以有：
N＝ n0＋ n1＋ n2 ①
又由二叉树的链式存储结构定义可知，度为 1的结点的空链域个数为 1，度为 2的结点的空链域个数为 0，度为 0的结点的空链域个数为 2，设含有 N个结点的二叉树的二叉链表中空链域的个数为 M，则有：
M＝ 2* n0＋ 1*n1＋ 0*n2= 2* n0＋ n1 ②
又因为,n0＝ n2＋ 1 ③
由①、②、③ 可得：
M＝ 2* n0＋ n1
＝ n0+n1+n0
＝ n0+n1+n2+1
＝ N+1 命题得证。
6.4 遍历二叉树和线索二叉树一、遍历二叉树遍历二叉树是指 按一定的规律 对二叉树的每个结点,访问 且仅访问一次的处理过程。
访问 是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。
遍历的次序,若设二叉树根为 D，左子树为 L，右子树为 R，并限定先左后右，则有以下三种遍历次序：
LDR 中序遍历 ； LRD 后序遍历 ； DLR 先序遍历
