2001 -- 12 --15/27
华中科技大学计算机学院 (6)数据结构第六章 树和二叉树线性结构：线性表,栈,队列串,数组,广义表非线性结构：树和二叉树图，网
6.1树的定义
6.1.1 定义和术语
1.树 （ tree)----
树是 n(n≥ 0)个结点的有限集 T,当 n=0时,T为空树；
当 n>0时,(1)有且仅有一个称为 T的根的结点,(2)当 n>1时,
余下的结点分为 m(m>0)个互不相交的有限集 T1,T2,...,Tm,
每个 Ti(1≤i≤m) 也是一棵树,且称为根的子树。
例 1,一个结点的树
T＝ {A} AT
T1={B,C,D,E,F}
T11={C,D,E}
T111={D}
T112={E}
T12={F}
T2={G,H}
T21={H}
T3={I,J,K,L,M,N,O,P}
T31={J,K,L,M,N}
T32={O}
T33={P}
T311={K}
T312={L},..
JC F H
IGB
A
E MK
P
L
O
D N
树 T
C F
B
ED
T1
H
G
T2
例 2 有 16个结点的树
T={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}
J
I
MK
P
L
O
N
T3
2.结点的度 (degree)---结点的子树数目
3.树的度 ----树中各结点的度的最大值
4.n度树 ----度为 n的树
5.叶子 (终端结点 )----度为 0的结点
6.分枝结点 (非终端结点,非叶子 )----
度不为 0的结点
7.双亲 (父母,parent)和 孩子 (儿子,child)
B
A
FD
H
E
C
G
4度树
1层
2层
3层
----若结点 C是结点 P的子树的根,称 P是 C的双亲,C是 P的孩子。
8.结点的层 (level)----规定树 T的根的层为 1，其余任一结点的层等于其双亲的层加 1。
9.树的深度 (depth,高度 )----树中各结点的层的最大值。
10.兄弟 (sibling)----同一双亲的结点之间互为兄弟。
11.堂兄弟 ----同一层号的结点互为堂兄弟。
12.祖先 ----从树的根到某结点所经分枝上的所有结点为该结点的祖先。
13.子孙 ----一个结点的所有子树的结点为该结点的子孙。
14.有序树 ----若任一结点的各棵子树，规定从左至右是 有次序的,即 不能互换位置,则称该树为有序树。
15.无序树 ----若任一结点的各棵子树，规定从左至右是 无次序的,即 能互换位置,则称该树为无序树。
B
A
D
F
E
C
G
无序树 T1
B
A
D
FC
无序树 T1 有序树 T1 有序树 T2
E G
B
A
D
F
E
C
G
B
A
D
FC
E G
16.森林 -----m(m≥ 0)棵互不相交的树的集合。
D
A
F H
C
E
B
G
T1
I
MJ L
K
N
T2 T3
森林 F={T1,T2,T3}
6.1.2.树的其它表示形式
1.广义表一般形式：
树 T的广义表 =(T的根 (T1,T2,...,Tm))
其中 Ti是 T的子树，也是广义表。 (1≤ i≤m)
树 T
F
A
G
EB
C D
树 T的广义表形式 =(A(B(C,D),E,F(G,))
广义表 A=(B,E,F)=((C,D),( ),(G))=((( ),( )）,( ),(( )))
2.嵌套集合,
广义表 A的树形表示
A
B
C D
E F
G
ED CB GF
A
3.凹入表 /书目表树 T
F
A
G
EB
C D
6.1.3 树的基本操作
1.置 T为空树,T={ }
2.销毁树 T
3.生成树 T
4.遍历树 T,按某种规则 (次序 )访问树 T的每一个结点一次且一次的过程。
5.求树 T的深度
6.求树 T的度
A -----------
B ---------
C -------
D -------
E ---------
F ---------
G -------
凹入表
7.插入一个结点
8.删除一个结点
9.求结点的层号
10.求结点的度
11.求树 T的叶子 /非叶子
12...................
6.2 二叉树 (binary tree)
6.2.1 定义和术语
1.二叉树 的递归定义二叉树是有限个结点的集合,它或者为空集；或者是由一个根结点和两棵互不相交的,且分别称为根的 左子树和 右子树 的二叉树所组成 。
若二叉树为空集,则为 空二叉树 。
例,
二叉树 T4
C
A
G
B
E F
H
A
A
B
二叉树 T2
二叉树 T1
2.二叉树的 5种基本形态,
T1 T2 T3 T4 T5
A
B
C
二叉树 T3
3.二叉树 与 2度树 的区别
(1)二叉树
T4
C
A
D
B
D
A
B
C
A
B
T3T2
C
(2)树
A
B
C
T2
2度树
A
B C
D
T5
T3
1度树
T4
2度树
A
T1
A
T1
0度树
C
A
B
C
A
B
4.三个结点不同形态的 二叉树 (5种 )
T1
A
B C
T2 T3 T4 T5
A
B
C
A
B
C
A
B
C
A
B
C
5.三个结点不同形态的 树 (2种 )
A
B
C
T1
A
B C
T2
6.二叉树的基本操作
1.置 T为空二叉树,T={ }
2.销毁二叉树 T
3.生成二叉树 T：
例：生成 哈夫曼树、二叉排序树、平衡二叉树、堆
4.遍历二叉树 T：
按某种规则访问 T的每一个结点一次且仅一次的过程。
5.二叉树 ←→ 树
6.二叉树 → 平衡二叉树
7.求结点的层号
8.求结点的度
9.求二叉树 T的深度
10.插入一个结点
11.删除一个结点
12.求二叉树 T的叶子 /非叶子
13...................
6.2.2 二叉树的性质和特殊二叉树
1.二叉树的 第 i(i≥1) 层最多有 2i-1个结点二叉树
C
A
G
B
E F
H
≤2 0 =1个
≤2 3 =8个
≤2 2 =4个
≤2 1 =2个
20(1- 2k)
1- 2
2.深度为 k的二叉树最多有 2k-1个结点
20+21+,..+ 2k-1= = 2k-1
3.叶子的数目 =度为 2的结点数目 +1
n0 = n2 + 1
A
B C
A
B
C
C
A
G
B
E F
H
T1 T2 T3
T1,n0=2,n2=1,2=1+1
T2,n0=1,n2=0 1=0+1
T3,n0=3,n2=2 3=2+1
4.满二叉树 （ full binary tree)----
深度为 k且有 2k-1个结点的二叉树。
T1 T2 T3
T4
(1) n个结点的满二叉树的深度 =log2(n+1)
设深度为 k
∵ 2k - 1＝ n
2k＝ n + 1
∴ k =log2(n+1)
(2)顺序编号的满二叉树
1
2 3
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
1
2 3
4 5 6 7
1
设满二叉树有 n个结点,编号为 1,2,...,n
● 左小孩为偶数,右小孩为奇数；
● 结点 i的 左小孩是 2i,2i≤n
结点 i的右 小孩是 2i+1,2i+1≤n
结点 i的双亲是?i/2?； 2≤i≤n
● 结点 i的层号 =?log2 i? + 1 =?log2(i+1)? 1≤i≤n
T1
T2 T3 T4
●? X? = 不大于 X的最大整数，取 X的 下限 /地板
●? X? = 不小于 X的最小整数，取 X的 上限 /天花板例?3.1? = 3,?3.9? = 3,? 3? = 3
3.1? = 4,?3.9? = 4? 3? = 3
5.完全二叉树 （ full binary tree)----
深度为 k的有 n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从 1至 n的结点一一对应,称之为 完全二叉树 （其它教材称为,顺序二叉树,） 。
例,完全二叉树,
1
2
1 1
2 3
4 5
T1
T2
T3 T4 T5
A
B E
D C F
1
2 3
4 5 6 7
例 非完全二叉树,
1
2
1
2 3
4 5
1
2 3
5 64
1
2 3
4 5 6 7
例 满二叉树,
T2
T1
T3
1
2 3
54
T4
1
2 3
T1
T2
n(n>0)个结点的完全二叉树的深度 =?log2 n?+1 =?log2(n+1)?
6.2.3 二叉树的存储结构
1.顺序结构
(1) n个结点的完全二叉树，使用一维数组,
例,ElemType tree[n+1]；
char t[7]；
A
C D
B E F
T1
// A C D B E F
1
2 3
4 65
t[1..6]
0 1 2 3 4 5 6
父子关系
● 元素 (结点 )t[i]的双亲是 t[i/2],2≤i≤n
● 元素 (结点 )t[i]的 左小孩是 t[2*i],2i≤n
● 元素 (结点 )t[i]的右 小孩是 t[2*i+1],2i+1≤n
T1的顺序结构
(2) 一般二叉树
A
B E
C
H
G
T2
A B E C G D E H
1
2 3
4 6
13
t[1..13]
1 2 3 4 5 6 7 8 9 10 11 12 13
父子关系
● 若 t[i]存在,t[i]的双亲是 t[i/2]； 2≤i≤n
● 若 t[2*i]存在,t[i]的 左小孩是 t[2*i]； 2i≤n
● 若 t[2*i+1]存在,t[i]的右 小孩是 t[2*i+1]。 2i+1≤n
E
9
D
8
T2的顺序结构
(3)右单枝树
A
B
T3
A B C D
1
3 t[1..15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
深度为 k的二叉树，最多需长度为 2k-1的一维数组。
若是 右单枝树,空间利用率为,
k? = ———
2k - 1
k=4,?=4/15 ；
k=10,?=10/1023
0.0098
C
D
7
15
T3的顺序结构
2.链式存储结构
(1)二叉链表
struct BiTNode //结点类型
{ struct BiTNode * lchild； //左孩子指针
ElemType data； //抽象数据元素类型
struct BiTNode * rchild； //右孩子指针
} *root,*p；
lchild data rchildp
A
B ∧ C
∧ D ∧ ∧ E ∧ F ∧
∧ G ∧
root
二叉树 T1 T1的二叉链表
C
A
F
B
D E
G
(2)三叉链表
struct BiTNode
{ struct BiTNode *parent,*lchild,*rchild ；
ElemType data；
} *root,*p；
lchild data parent rchildp
C
A
F
B
D E
G
∧ A
B ∧ C
∧ D ∧ ∧ E ∧ F ∧
∧ G ∧
root
二叉树 T2 T2的三叉链表
(3)静态链表
struct bnode2
{ ElemType data；
int lchild,rchild；
}t[n+1]；
二叉树
/// /// ///
2 A 3
4 B 5
0 C 6
0 D 0
0 E 0
7 F 0
0 G 0
0
1
2
3
4
5
6
7
lchild data rchild
一维数组 t[0..7]
root
C
A
F
B
D E
G
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树 ----
按某种规则访问二叉树的每一个结点一次且仅一次的过程。
设,D----访问根结点,输出根结点；
L----递归遍历左二叉树；
R----递归遍历右二叉树。
遍历规则 (方案 ):
● DLR----前序遍历 (先根,preorder)
● LDR----中序遍历 (中根,inorder)
● LRD----后序遍历 (后根,postorder)
● DRL----逆前序遍历
● RDL----逆中序遍历
● RLD----逆后序遍历
1.前序遍历 二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 访问根结点；
(2) 遍历根的左子树；
(3) 遍历根的右子树 。
例 1,前序遍历
T1
E
T11
● 遍历 T：
● 访问 A；
● 遍历 T1：
● 访问 B；
● 遍历 T11：
● 访问 E；
● 左子树为空,遍历结束；
● 右子树为空,遍历结束。
● T11遍历结束。
● 遍历 T12：
C
A
D
G
T
B
E F
B
E F
T1
F
T12
● 遍历 T12：
● 访问 F；
● 左子树为空,遍历结束；
● 右子树为空,遍历结束。
● T12遍历结束。
● T1遍历结束。
C
D
G
T2
● 遍历 T2：
● 访问 C；
● 左子树为空,遍历结束；
● 遍历 C的右子树 T22：
遍历 T12:
T
B
E F
C
A
D
G
B
E F
C
D
G
T2
D
G
T22
G
T221
● 遍历 C的右子树 T22：
● 访问 D；
● 遍历 T221：
● 访问 G；
● G的左子树为空,遍历结束；
● G的右子树为空,遍历结束；
● T221遍历结束。
● D的右子树为空,遍历结束。
● T22遍历结束。
● T2遍历结束。
● T遍历结束。
● 得前序序列：
A,B,E,F,C,D,G
遍历 T22:
C
A
D
G
T
B
E F
2.中序遍历二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 遍历根的左子树；
(2) 访问根结点；
(3) 遍历根的右子树 。
例 1,中序遍历
T1
E
T11
● 遍历 T：
● 遍历 T1：
● 遍历 T11：
● 左子树为空,遍历结束
● 访问 E；
● 右子树为空,遍历结束。
● T11遍历结束。
● 访问 B；
● 遍历 T12：T
B
E F
C
A
D
G
B
E F
遍历 T12：
F
● 遍历 T12：
● 左子树为空,遍历结束；
● 访问 F；
● 右子树为空,遍历结束。
● T12遍历结束。
● T1遍历结束。T1
● 访问 A；
● 遍历 T2：
● C的左子树为空,遍历结束；
● 访问 C；
● 遍历 C的右子树 T22：
C
D
G
T12
T2T
C
A
D
G
B
E F
B
E F
遍历 T22：
C
D
G
T2
D
G
T22
● 遍历 C的右子树 T22：
● 遍历 T221：
● G的左子树为空,遍历结束；
● 访问 G；
● G的右子树为空,遍历结束
● T221遍历结束。
● 访问 D；
● D的右子树为空,遍历结束
● 遍历 T22结束。
● 遍历 T2结束。
G
T221
● 遍历 T结束。
● 得中序序列：
E,B,F,A,C,G,D
T
C
A
D
G
B
E F
3.后序遍历二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 遍历根的左子树；
(2) 遍历根的右子树；
(2) 访问根结点 。
例 1,后序遍历
T1
E
T11
● 遍历 T：
● 遍历 T1：
● 遍历 T11：
● 左子树为空,遍历结束
● 右子树为空,遍历结束。
● 访问 E；
● T11遍历结束。
● 遍历 T12：T
C
A
D
G
B
E F
B
E F
遍历 T12
T1
F
T12
● 遍历 T12：
● F的左子树为空,遍历结束
● F的右子树为空,遍历结束。
● 访问 F；
● T12遍历结束。
● 访问 B；
● T1遍历结束。
● 遍历 T2：
● C的左子树为空,遍历结束；
● 遍历 T22：
● 遍历 T221：
C
D
G
T2
D
G
T22
B
E F
T
C
A
D
G
B
E F
遍历 T221,● 遍历 T221：
● G的左子树为空,遍历结束；
● G的右子树为空,遍历结束；
● 访问 G；
● T1221遍历结束；
● D的右子树为空,遍历结束；
● 访问 D；
● T22遍历结束。
D
G
T22
G
T221
C
D
G
T2
● 访问 C；
● T2遍历结束
● 访问 A；
● T遍历结束。
● 得后序序列,E,F,B,G,D,C,A
T
C
A
D
G
B
E F
先序 遍历 递归算法
typedef struct BiTNode *BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (!T) return;
else
{
printf(“%c”,T->data); //访问根指针
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
先序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
printf(“%c”,T->data); //访问根指针
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
例 1,前序遍历递归算法过程
T1
C
A
D
G
T
B
E F
B
E F
E
F
C
D
G
D
G
G
T
T
T
T
T
T
T
左左左左右右右右访问 A
访问 B
访问 C
访问 E
访问 F
访问 D 访问 C
中序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void MidOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
MidOrderTraverse(T->lchild)； //递归访问左子树
printf(“%c”,T->data); //访问根指针
MidOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
后序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
printf(“%c”,T->data); //访问根指针
}
return；
}
B
A
C
D
F
E
G
T1
B
A
C
D
F
E
G
6.3.2 建立 (生成 )二叉树
● 二叉树 T1的先序序列：
"ADEFGBC"
带空二叉树的先序序列：
"AD?EFGB?C"
其中,'?'表示空二叉树
● 二叉树 T2的先序序列：
"ADEFGBC"
带空二叉树的先序序列：
"ADEFGBC"
B
A
C
D
F
E
G
T2
B
A
C
D
F
E
G
● 输入带空二叉树的先序序列，按先序序列方式建立对应二叉树的二叉链表。
C算法
#define leng sizeof(BiTNode) /*结点所占空间大小 */
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
用根结点的指针表示一棵 二叉树：
例,BiTree root1,root2;
root1=NULL;
root2=NULL;
算法 1:
void CreatBiTree1(struct BiTNode **root)
//root是指向二叉链表根指针的指针
{ char ch；
scanf(“%c”,&ch)； /输入一个结点，假定为字符型
if (ch =='?') (*root)=NULL；
else
{
(*root)=(struct BiTNode *)malloc(leng)；
(*root)->data=ch； //生成根结点
CreatBiTree1(&(*root)->lchild)； //递归构造左子树
CreatBiTree1(&(*root)->rchild)； //递归构造右子树
}
}
算法 2:
BiTree CreatBiTree2()
{ char ch; BiTree root; //二叉链表根结点指针
scanf(“%c”,&ch); //输入一个结点
if (ch =='? ') root=NULL;
else
{ root=(BiTree) malloc(leng); //生成根结点
root->data=ch;
root->lchild=CreatBiTree2(); //递归构造左子树
root->rchild=CreatBiTree2(); //递归构造右子树
}
return root;
}
算法 3:
void CreatBiTree3(BiTree &root)
{ char ch;; //二叉链表根结点指针
scanf("%c",&ch); //输入一个结点
if (ch =='? ') root=NULL;
else
{
root=(BiTree) malloc(leng); //生成根结点
root->data=ch;
CreatBiTree3(root->lchild); //递归构造左子树
CreatBiTree3(root->rchild); //递归构造右子树
}
}
主函数 (调用方法）：
main( )
{ struct BiTNode *root1,*root2,*root3；
CreatBiTree1(&root1)； /*算法 1*/
root2=CreatBiTree2(); /*算法 2*/
CreatBiTree3(root3)； /*算法 3*/
}
假设输入先序序列,AD?EFGB?C,对应的二叉链表为
A
∧ D ∧ B
∧ F ∧
E ∧ C ∧
∧ G ∧
root
二叉链表
B
A
C
D
F
E
G
二叉树左右先序序列,AD?EFGB?C
A
root
左?
右
^ D
root
左右
E
root
左?
右?
^ F ^
root
左?
右?
^ G ^
root
左?
右
^ B
root
左?
右?
^ G ^
root
返回 root
返回 root
返回 root
返回 root
返回 root
返回 root
返回 root
6.3.3 线索二叉树 ---- 在空二叉树的位置增加指向 前趋 /后继线索 (即指针 )的二叉树。
1.前序线索二叉树 ----线索指向前序遍历中前趋、后继的线索二叉树。
例,T的前序序列,A,B,C.D,E,F,G
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的前序线索二叉树
NULL
2.中序线索二叉树 ----线索指向中序遍历中前趋、后继的线索二叉树。
例,T的中序序列,B,D,C,E,A,F,G
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的中序线索二叉树
NULL
NULL
3.后序线索二叉树 ----线索指向后序遍历中前趋、后继的线索二叉树。
例,T的后序序列,D,E,C,B,G,F,A
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的后序线索二叉树
NULL
4.后序后继线索二叉树 ----只设指向后序遍历中后继线索的线索二叉树。
例,T的后序序列,H,D,E,C,B,G,F,A
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的后序后继线索二叉树
H H
5.线索二叉树的存储结构
(1).结点结构：
F
A
G
B
D
C
二叉树
0/1 0/1
lchild ltag data rtag rchild
左小孩 左标志 结点值 右标志 右小孩或前趋 或后继
0 A 0
root
中序线索二叉树链表
E
1 F 01 B 0
1 G 10 C 0
1 D 1 1 E 1
NULL
NULL
华中科技大学计算机学院 (6)数据结构第六章 树和二叉树线性结构：线性表,栈,队列串,数组,广义表非线性结构：树和二叉树图，网
6.1树的定义
6.1.1 定义和术语
1.树 （ tree)----
树是 n(n≥ 0)个结点的有限集 T,当 n=0时,T为空树；
当 n>0时,(1)有且仅有一个称为 T的根的结点,(2)当 n>1时,
余下的结点分为 m(m>0)个互不相交的有限集 T1,T2,...,Tm,
每个 Ti(1≤i≤m) 也是一棵树,且称为根的子树。
例 1,一个结点的树
T＝ {A} AT
T1={B,C,D,E,F}
T11={C,D,E}
T111={D}
T112={E}
T12={F}
T2={G,H}
T21={H}
T3={I,J,K,L,M,N,O,P}
T31={J,K,L,M,N}
T32={O}
T33={P}
T311={K}
T312={L},..
JC F H
IGB
A
E MK
P
L
O
D N
树 T
C F
B
ED
T1
H
G
T2
例 2 有 16个结点的树
T={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}
J
I
MK
P
L
O
N
T3
2.结点的度 (degree)---结点的子树数目
3.树的度 ----树中各结点的度的最大值
4.n度树 ----度为 n的树
5.叶子 (终端结点 )----度为 0的结点
6.分枝结点 (非终端结点,非叶子 )----
度不为 0的结点
7.双亲 (父母,parent)和 孩子 (儿子,child)
B
A
FD
H
E
C
G
4度树
1层
2层
3层
----若结点 C是结点 P的子树的根,称 P是 C的双亲,C是 P的孩子。
8.结点的层 (level)----规定树 T的根的层为 1，其余任一结点的层等于其双亲的层加 1。
9.树的深度 (depth,高度 )----树中各结点的层的最大值。
10.兄弟 (sibling)----同一双亲的结点之间互为兄弟。
11.堂兄弟 ----同一层号的结点互为堂兄弟。
12.祖先 ----从树的根到某结点所经分枝上的所有结点为该结点的祖先。
13.子孙 ----一个结点的所有子树的结点为该结点的子孙。
14.有序树 ----若任一结点的各棵子树，规定从左至右是 有次序的,即 不能互换位置,则称该树为有序树。
15.无序树 ----若任一结点的各棵子树，规定从左至右是 无次序的,即 能互换位置,则称该树为无序树。
B
A
D
F
E
C
G
无序树 T1
B
A
D
FC
无序树 T1 有序树 T1 有序树 T2
E G
B
A
D
F
E
C
G
B
A
D
FC
E G
16.森林 -----m(m≥ 0)棵互不相交的树的集合。
D
A
F H
C
E
B
G
T1
I
MJ L
K
N
T2 T3
森林 F={T1,T2,T3}
6.1.2.树的其它表示形式
1.广义表一般形式：
树 T的广义表 =(T的根 (T1,T2,...,Tm))
其中 Ti是 T的子树，也是广义表。 (1≤ i≤m)
树 T
F
A
G
EB
C D
树 T的广义表形式 =(A(B(C,D),E,F(G,))
广义表 A=(B,E,F)=((C,D),( ),(G))=((( ),( )）,( ),(( )))
2.嵌套集合,
广义表 A的树形表示
A
B
C D
E F
G
ED CB GF
A
3.凹入表 /书目表树 T
F
A
G
EB
C D
6.1.3 树的基本操作
1.置 T为空树,T={ }
2.销毁树 T
3.生成树 T
4.遍历树 T,按某种规则 (次序 )访问树 T的每一个结点一次且一次的过程。
5.求树 T的深度
6.求树 T的度
A -----------
B ---------
C -------
D -------
E ---------
F ---------
G -------
凹入表
7.插入一个结点
8.删除一个结点
9.求结点的层号
10.求结点的度
11.求树 T的叶子 /非叶子
12...................
6.2 二叉树 (binary tree)
6.2.1 定义和术语
1.二叉树 的递归定义二叉树是有限个结点的集合,它或者为空集；或者是由一个根结点和两棵互不相交的,且分别称为根的 左子树和 右子树 的二叉树所组成 。
若二叉树为空集,则为 空二叉树 。
例,
二叉树 T4
C
A
G
B
E F
H
A
A
B
二叉树 T2
二叉树 T1
2.二叉树的 5种基本形态,
T1 T2 T3 T4 T5
A
B
C
二叉树 T3
3.二叉树 与 2度树 的区别
(1)二叉树
T4
C
A
D
B
D
A
B
C
A
B
T3T2
C
(2)树
A
B
C
T2
2度树
A
B C
D
T5
T3
1度树
T4
2度树
A
T1
A
T1
0度树
C
A
B
C
A
B
4.三个结点不同形态的 二叉树 (5种 )
T1
A
B C
T2 T3 T4 T5
A
B
C
A
B
C
A
B
C
A
B
C
5.三个结点不同形态的 树 (2种 )
A
B
C
T1
A
B C
T2
6.二叉树的基本操作
1.置 T为空二叉树,T={ }
2.销毁二叉树 T
3.生成二叉树 T：
例：生成 哈夫曼树、二叉排序树、平衡二叉树、堆
4.遍历二叉树 T：
按某种规则访问 T的每一个结点一次且仅一次的过程。
5.二叉树 ←→ 树
6.二叉树 → 平衡二叉树
7.求结点的层号
8.求结点的度
9.求二叉树 T的深度
10.插入一个结点
11.删除一个结点
12.求二叉树 T的叶子 /非叶子
13...................
6.2.2 二叉树的性质和特殊二叉树
1.二叉树的 第 i(i≥1) 层最多有 2i-1个结点二叉树
C
A
G
B
E F
H
≤2 0 =1个
≤2 3 =8个
≤2 2 =4个
≤2 1 =2个
20(1- 2k)
1- 2
2.深度为 k的二叉树最多有 2k-1个结点
20+21+,..+ 2k-1= = 2k-1
3.叶子的数目 =度为 2的结点数目 +1
n0 = n2 + 1
A
B C
A
B
C
C
A
G
B
E F
H
T1 T2 T3
T1,n0=2,n2=1,2=1+1
T2,n0=1,n2=0 1=0+1
T3,n0=3,n2=2 3=2+1
4.满二叉树 （ full binary tree)----
深度为 k且有 2k-1个结点的二叉树。
T1 T2 T3
T4
(1) n个结点的满二叉树的深度 =log2(n+1)
设深度为 k
∵ 2k - 1＝ n
2k＝ n + 1
∴ k =log2(n+1)
(2)顺序编号的满二叉树
1
2 3
1
2
4 5
8 9 10 11
3
6 7
12 13 14 15
1
2 3
4 5 6 7
1
设满二叉树有 n个结点,编号为 1,2,...,n
● 左小孩为偶数,右小孩为奇数；
● 结点 i的 左小孩是 2i,2i≤n
结点 i的右 小孩是 2i+1,2i+1≤n
结点 i的双亲是?i/2?； 2≤i≤n
● 结点 i的层号 =?log2 i? + 1 =?log2(i+1)? 1≤i≤n
T1
T2 T3 T4
●? X? = 不大于 X的最大整数，取 X的 下限 /地板
●? X? = 不小于 X的最小整数，取 X的 上限 /天花板例?3.1? = 3,?3.9? = 3,? 3? = 3
3.1? = 4,?3.9? = 4? 3? = 3
5.完全二叉树 （ full binary tree)----
深度为 k的有 n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从 1至 n的结点一一对应,称之为 完全二叉树 （其它教材称为,顺序二叉树,） 。
例,完全二叉树,
1
2
1 1
2 3
4 5
T1
T2
T3 T4 T5
A
B E
D C F
1
2 3
4 5 6 7
例 非完全二叉树,
1
2
1
2 3
4 5
1
2 3
5 64
1
2 3
4 5 6 7
例 满二叉树,
T2
T1
T3
1
2 3
54
T4
1
2 3
T1
T2
n(n>0)个结点的完全二叉树的深度 =?log2 n?+1 =?log2(n+1)?
6.2.3 二叉树的存储结构
1.顺序结构
(1) n个结点的完全二叉树，使用一维数组,
例,ElemType tree[n+1]；
char t[7]；
A
C D
B E F
T1
// A C D B E F
1
2 3
4 65
t[1..6]
0 1 2 3 4 5 6
父子关系
● 元素 (结点 )t[i]的双亲是 t[i/2],2≤i≤n
● 元素 (结点 )t[i]的 左小孩是 t[2*i],2i≤n
● 元素 (结点 )t[i]的右 小孩是 t[2*i+1],2i+1≤n
T1的顺序结构
(2) 一般二叉树
A
B E
C
H
G
T2
A B E C G D E H
1
2 3
4 6
13
t[1..13]
1 2 3 4 5 6 7 8 9 10 11 12 13
父子关系
● 若 t[i]存在,t[i]的双亲是 t[i/2]； 2≤i≤n
● 若 t[2*i]存在,t[i]的 左小孩是 t[2*i]； 2i≤n
● 若 t[2*i+1]存在,t[i]的右 小孩是 t[2*i+1]。 2i+1≤n
E
9
D
8
T2的顺序结构
(3)右单枝树
A
B
T3
A B C D
1
3 t[1..15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
深度为 k的二叉树，最多需长度为 2k-1的一维数组。
若是 右单枝树,空间利用率为,
k? = ———
2k - 1
k=4,?=4/15 ；
k=10,?=10/1023
0.0098
C
D
7
15
T3的顺序结构
2.链式存储结构
(1)二叉链表
struct BiTNode //结点类型
{ struct BiTNode * lchild； //左孩子指针
ElemType data； //抽象数据元素类型
struct BiTNode * rchild； //右孩子指针
} *root,*p；
lchild data rchildp
A
B ∧ C
∧ D ∧ ∧ E ∧ F ∧
∧ G ∧
root
二叉树 T1 T1的二叉链表
C
A
F
B
D E
G
(2)三叉链表
struct BiTNode
{ struct BiTNode *parent,*lchild,*rchild ；
ElemType data；
} *root,*p；
lchild data parent rchildp
C
A
F
B
D E
G
∧ A
B ∧ C
∧ D ∧ ∧ E ∧ F ∧
∧ G ∧
root
二叉树 T2 T2的三叉链表
(3)静态链表
struct bnode2
{ ElemType data；
int lchild,rchild；
}t[n+1]；
二叉树
/// /// ///
2 A 3
4 B 5
0 C 6
0 D 0
0 E 0
7 F 0
0 G 0
0
1
2
3
4
5
6
7
lchild data rchild
一维数组 t[0..7]
root
C
A
F
B
D E
G
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树 ----
按某种规则访问二叉树的每一个结点一次且仅一次的过程。
设,D----访问根结点,输出根结点；
L----递归遍历左二叉树；
R----递归遍历右二叉树。
遍历规则 (方案 ):
● DLR----前序遍历 (先根,preorder)
● LDR----中序遍历 (中根,inorder)
● LRD----后序遍历 (后根,postorder)
● DRL----逆前序遍历
● RDL----逆中序遍历
● RLD----逆后序遍历
1.前序遍历 二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 访问根结点；
(2) 遍历根的左子树；
(3) 遍历根的右子树 。
例 1,前序遍历
T1
E
T11
● 遍历 T：
● 访问 A；
● 遍历 T1：
● 访问 B；
● 遍历 T11：
● 访问 E；
● 左子树为空,遍历结束；
● 右子树为空,遍历结束。
● T11遍历结束。
● 遍历 T12：
C
A
D
G
T
B
E F
B
E F
T1
F
T12
● 遍历 T12：
● 访问 F；
● 左子树为空,遍历结束；
● 右子树为空,遍历结束。
● T12遍历结束。
● T1遍历结束。
C
D
G
T2
● 遍历 T2：
● 访问 C；
● 左子树为空,遍历结束；
● 遍历 C的右子树 T22：
遍历 T12:
T
B
E F
C
A
D
G
B
E F
C
D
G
T2
D
G
T22
G
T221
● 遍历 C的右子树 T22：
● 访问 D；
● 遍历 T221：
● 访问 G；
● G的左子树为空,遍历结束；
● G的右子树为空,遍历结束；
● T221遍历结束。
● D的右子树为空,遍历结束。
● T22遍历结束。
● T2遍历结束。
● T遍历结束。
● 得前序序列：
A,B,E,F,C,D,G
遍历 T22:
C
A
D
G
T
B
E F
2.中序遍历二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 遍历根的左子树；
(2) 访问根结点；
(3) 遍历根的右子树 。
例 1,中序遍历
T1
E
T11
● 遍历 T：
● 遍历 T1：
● 遍历 T11：
● 左子树为空,遍历结束
● 访问 E；
● 右子树为空,遍历结束。
● T11遍历结束。
● 访问 B；
● 遍历 T12：T
B
E F
C
A
D
G
B
E F
遍历 T12：
F
● 遍历 T12：
● 左子树为空,遍历结束；
● 访问 F；
● 右子树为空,遍历结束。
● T12遍历结束。
● T1遍历结束。T1
● 访问 A；
● 遍历 T2：
● C的左子树为空,遍历结束；
● 访问 C；
● 遍历 C的右子树 T22：
C
D
G
T12
T2T
C
A
D
G
B
E F
B
E F
遍历 T22：
C
D
G
T2
D
G
T22
● 遍历 C的右子树 T22：
● 遍历 T221：
● G的左子树为空,遍历结束；
● 访问 G；
● G的右子树为空,遍历结束
● T221遍历结束。
● 访问 D；
● D的右子树为空,遍历结束
● 遍历 T22结束。
● 遍历 T2结束。
G
T221
● 遍历 T结束。
● 得中序序列：
E,B,F,A,C,G,D
T
C
A
D
G
B
E F
3.后序遍历二叉树递归定义：
若二叉树为空,则遍历结束；
否则,执行下列步骤：
(1) 遍历根的左子树；
(2) 遍历根的右子树；
(2) 访问根结点 。
例 1,后序遍历
T1
E
T11
● 遍历 T：
● 遍历 T1：
● 遍历 T11：
● 左子树为空,遍历结束
● 右子树为空,遍历结束。
● 访问 E；
● T11遍历结束。
● 遍历 T12：T
C
A
D
G
B
E F
B
E F
遍历 T12
T1
F
T12
● 遍历 T12：
● F的左子树为空,遍历结束
● F的右子树为空,遍历结束。
● 访问 F；
● T12遍历结束。
● 访问 B；
● T1遍历结束。
● 遍历 T2：
● C的左子树为空,遍历结束；
● 遍历 T22：
● 遍历 T221：
C
D
G
T2
D
G
T22
B
E F
T
C
A
D
G
B
E F
遍历 T221,● 遍历 T221：
● G的左子树为空,遍历结束；
● G的右子树为空,遍历结束；
● 访问 G；
● T1221遍历结束；
● D的右子树为空,遍历结束；
● 访问 D；
● T22遍历结束。
D
G
T22
G
T221
C
D
G
T2
● 访问 C；
● T2遍历结束
● 访问 A；
● T遍历结束。
● 得后序序列,E,F,B,G,D,C,A
T
C
A
D
G
B
E F
先序 遍历 递归算法
typedef struct BiTNode *BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (!T) return;
else
{
printf(“%c”,T->data); //访问根指针
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
先序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
printf(“%c”,T->data); //访问根指针
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
例 1,前序遍历递归算法过程
T1
C
A
D
G
T
B
E F
B
E F
E
F
C
D
G
D
G
G
T
T
T
T
T
T
T
左左左左右右右右访问 A
访问 B
访问 C
访问 E
访问 F
访问 D 访问 C
中序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void MidOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
MidOrderTraverse(T->lchild)； //递归访问左子树
printf(“%c”,T->data); //访问根指针
MidOrderTraverse(T->rchild)； //递归访问右子树
}
return；
}
后序 遍历 递归算法
typedef struct BiTNode*BiTree; //结点指针类型
void PreOrderTraverse(BiTree T)
//T是指向二叉链表根 结点 的指针
{
if (T)
{
PreOrderTraverse(T->lchild)； //递归访问左子树
PreOrderTraverse(T->rchild)； //递归访问右子树
printf(“%c”,T->data); //访问根指针
}
return；
}
B
A
C
D
F
E
G
T1
B
A
C
D
F
E
G
6.3.2 建立 (生成 )二叉树
● 二叉树 T1的先序序列：
"ADEFGBC"
带空二叉树的先序序列：
"AD?EFGB?C"
其中,'?'表示空二叉树
● 二叉树 T2的先序序列：
"ADEFGBC"
带空二叉树的先序序列：
"ADEFGBC"
B
A
C
D
F
E
G
T2
B
A
C
D
F
E
G
● 输入带空二叉树的先序序列，按先序序列方式建立对应二叉树的二叉链表。
C算法
#define leng sizeof(BiTNode) /*结点所占空间大小 */
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
用根结点的指针表示一棵 二叉树：
例,BiTree root1,root2;
root1=NULL;
root2=NULL;
算法 1:
void CreatBiTree1(struct BiTNode **root)
//root是指向二叉链表根指针的指针
{ char ch；
scanf(“%c”,&ch)； /输入一个结点，假定为字符型
if (ch =='?') (*root)=NULL；
else
{
(*root)=(struct BiTNode *)malloc(leng)；
(*root)->data=ch； //生成根结点
CreatBiTree1(&(*root)->lchild)； //递归构造左子树
CreatBiTree1(&(*root)->rchild)； //递归构造右子树
}
}
算法 2:
BiTree CreatBiTree2()
{ char ch; BiTree root; //二叉链表根结点指针
scanf(“%c”,&ch); //输入一个结点
if (ch =='? ') root=NULL;
else
{ root=(BiTree) malloc(leng); //生成根结点
root->data=ch;
root->lchild=CreatBiTree2(); //递归构造左子树
root->rchild=CreatBiTree2(); //递归构造右子树
}
return root;
}
算法 3:
void CreatBiTree3(BiTree &root)
{ char ch;; //二叉链表根结点指针
scanf("%c",&ch); //输入一个结点
if (ch =='? ') root=NULL;
else
{
root=(BiTree) malloc(leng); //生成根结点
root->data=ch;
CreatBiTree3(root->lchild); //递归构造左子树
CreatBiTree3(root->rchild); //递归构造右子树
}
}
主函数 (调用方法）：
main( )
{ struct BiTNode *root1,*root2,*root3；
CreatBiTree1(&root1)； /*算法 1*/
root2=CreatBiTree2(); /*算法 2*/
CreatBiTree3(root3)； /*算法 3*/
}
假设输入先序序列,AD?EFGB?C,对应的二叉链表为
A
∧ D ∧ B
∧ F ∧
E ∧ C ∧
∧ G ∧
root
二叉链表
B
A
C
D
F
E
G
二叉树左右先序序列,AD?EFGB?C
A
root
左?
右
^ D
root
左右
E
root
左?
右?
^ F ^
root
左?
右?
^ G ^
root
左?
右
^ B
root
左?
右?
^ G ^
root
返回 root
返回 root
返回 root
返回 root
返回 root
返回 root
返回 root
6.3.3 线索二叉树 ---- 在空二叉树的位置增加指向 前趋 /后继线索 (即指针 )的二叉树。
1.前序线索二叉树 ----线索指向前序遍历中前趋、后继的线索二叉树。
例,T的前序序列,A,B,C.D,E,F,G
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的前序线索二叉树
NULL
2.中序线索二叉树 ----线索指向中序遍历中前趋、后继的线索二叉树。
例,T的中序序列,B,D,C,E,A,F,G
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的中序线索二叉树
NULL
NULL
3.后序线索二叉树 ----线索指向后序遍历中前趋、后继的线索二叉树。
例,T的后序序列,D,E,C,B,G,F,A
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的后序线索二叉树
NULL
4.后序后继线索二叉树 ----只设指向后序遍历中后继线索的线索二叉树。
例,T的后序序列,H,D,E,C,B,G,F,A
F
A
G
B
D
C
E
二叉树 T
F
A
G
B
D
C
E
T的后序后继线索二叉树
H H
5.线索二叉树的存储结构
(1).结点结构：
F
A
G
B
D
C
二叉树
0/1 0/1
lchild ltag data rtag rchild
左小孩 左标志 结点值 右标志 右小孩或前趋 或后继
0 A 0
root
中序线索二叉树链表
E
1 F 01 B 0
1 G 10 C 0
1 D 1 1 E 1
NULL
NULL
