第六章 树和二叉树
6.1树的类型定义
数据对象 D：D是具有相同特性的数据元素的集合。
数据关系 R：若D为空集，则称为空树 。否则:
(1) 在D中存在唯一的称为根的数据元素root；
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm，其中每一棵
子集本身又是一棵符合本定义的树，称为根root的子树。
基本操作：
·查 找 类
·插 入 类
·删 除 类
查找类：
Root(T) // 求树的根结点
Value(T, cur_e) // 求当前结点的元素值
Parent(T, cur_e) // 求当前结点的双亲结点
LeftChild(T, cur_e) // 求当前结点的最左孩子
RightSibling(T, cur_e) // 求当前结点的右兄弟
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
TraverseTree( T, Visit() ) // 遍历
插入类：
InitTree(&T) // 初始化置空树
CreateTree(&T, definition) // 按定义构造树
CreateTree(&T, definition) // 按定义构造树
InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树
删除类：
ClearTree(&T) // 将树清空
DestroyTree(&T) // 销毁树的结构
DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
树形图表示的例子
对比树型结构和线性结构的结构特点
线性结构 树型结构
第一个数据元素 根结点
(无前驱) (无前驱)
最后一个数据元素 多个叶子结点
(无后继) (无后继)
其它数据元素 其它数据元素
(一个前驱、一个后继) (一个前驱、多个后继)
基 本 术 语
结点: 数据元素+若干指向子树的分支
结点的度: 分支的个数
树的度: 树中所有结点的度的最大值
叶子结点: 度为零的结点
分支结点: 度大于零的结点
(从根到结点的)路径：由从根到该结点所经分支和结点构成
孩子结点、双亲结点
兄弟结点、堂兄弟
祖先结点、子孙结点
结点的层次:假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1
树的深度：树中叶子结点所在的最大层次
有向树：(１) 有确定的根；
(２) 树根和子树根之间为有向关系。
有序树：子树之间存在确定的次序关系。
无序树：子树之间不存在确定的次序关系。
森林：是m（m≥0）棵互不相交的树的集合
任何一棵非空树是一个二元组Tree = （root，F）
其中：root 被称为根结点F 被称为子树森林
6.2 二叉树的类型定义
二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
二叉树的五种基本形态：
二叉树的主要基本操作：
·查 找 类
·插 入 类
·删 除 类
Root(T); Value(T, e); Parent(T, e);
LeftChild(T, e); RightChild(T, e);
LeftSibling(T, e); RightSibling(T, e);
BiTreeEmpty(T); BiTreeDepth(T);
PreOrderTraverse(T, Visit());
InOrderTraverse(T, Visit());
PostOrderTraverse(T, Visit());
LevelOrderTraverse(T, Visit());
InitBiTree(&T);
Assign(T, &e, value);
CreateBiTree(&T, definition);
InsertChild(T, p, LR, c);
ClearBiTree(&T);
DestroyBiTree(&T);
DeleteChild(T, p, LR);
性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
用归纳法证明：
归纳基：i = 1 层时，只有一个根结点：2i-1 = 20 = 1；
归纳假设：假设对所有的 j，1≤ j < i，命题成立；
归纳证明：二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2´ 2 = 2i-1 。
性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。
性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。
证明：设 二叉树上结点总数 n = n0 + n1 + n2又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此， n0 = n2 + 1 。
性质 4：
两类特殊的二叉树：
满二叉树：指的是深度为k且含有2k-1个结点的二叉树。
完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。
性质 5 ：
若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲，
否则，编号为 ëi/2û 的结点为其双亲结点；
(2) 若 2i>n，则该结点无左孩子，
否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，
否则，编号为2i+1 的结点为其右孩子结点。
6.3 二叉树的存储结构
一、 二叉树的顺序存储表示
#define MAX_TREE_SIZE 100
// 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_
TREE_SIZE];
// 0号单元存储根结点
SqBiTree bt;
二、二叉树的链式存储表示
1. 二叉链表
C 语言的类型描述如下:
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;
2．三叉链表
C 语言的类型描述如下:
typedef struct TriTNode { // 结点结构
TElemType data;
struct TriTNode *lchild, *rchild;
// 左右孩子指针
struct TriTNode *parent; //双亲指针
} TriTNode, *TriTree;
6.4二叉树的遍历
一、问题的提出
顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。
“访问”的含义可以很广，如：输出结点的信息等。
“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。
对“二叉树”而言，可以有三条搜索路径：
1．先上后下的按层次遍历；
2．先左（子树）后右（子树）的遍历；
3．先右（子树）后左（子树）的遍历。
二、按层次遍历二叉树
实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
按层次遍历该二叉树的序列为：
A B E C F D G H K
三、先左后右的遍历算法
先（根）序的遍历算法
中（根）序的遍历算法
后（根）序的遍历算法
先（根）序的遍历算法：
若二叉树为空树，则空操作；否则，
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍历二叉树
if (T) {
visit(T->data); // 访问结点
Preorder(T->lchild, visit); // 遍历左子树
Preorder(T->rchild, visit);// 遍历右子树
}
}
中（根）序的遍历算法：
若二叉树为空树，则空操作；否则，
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
void Inorder (BiTree T,
void( *visit)(TElemType& e))
{ // 中序遍历二叉树
if (T) {
Inreorder(T->lchild, visit); // 遍历左子树
visit(T->data); // 访问结点
Inreorder(T->rchild, visit);// 遍历右子树
}
}
后（根）序的遍历算法：
若二叉树为空树，则空操作；否则，
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
void Postorder (BiTree T,
void( *visit)(TElemType& e))
{ // 后序遍历二叉树
if (T) {
Postreorder(T->lchild, visit); // 遍历左子树
Postreorder(T->rchild, visit);// 遍历右子树
visit(T->data); // 访问结点
}
}
四、中序遍历算法的非递归描述中序遍历示意图
算法一：
Status InorderTraverse(Bitree T,
Status(*Visit)(TElemType e)) {
InitStack(S); Push(S,T);
while(!StackEmpty(S)) {
while(GetTop(S,p) && p) Push(S,p->lchild);
Pop(S,p);
if (!StackEmpty(S)) {
Pop(S,p);
if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);} }
return OK;
}
算法二：
Status InorderTraverse(Bitree T,
Status(*Visit)(TElemType e)) {
InitStack(S); p=T;
while(p||!StackEmpty(S)){
if(p) {Push(S,p); p=p->lchild;}
else {
Pop(S,p); if(!Visit(p->data)) return ERROR;
p=p->rchild;
}
}
return OK;
}
五、遍历算法的应用举例
1、输入结点值，构造二叉树
算法基本思想:
先序(或中序或后序)遍历二叉树，读入一个字符，若读入字符为空，则二叉树为空,若读入字符非空，则生成一个结点。将算法中“访问结点”的操作改为：生成一个结点，输入结点的值。
Status CreateBiTree (BiTree &T){
scanf( &ch ) ;
if (ch＝＝’’) T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))
exit(OVERFLOW);
T->data=ch; //生成根结点
CreateBiTree( T->lchild); //构造左子树
CreateBiTree( T->rchild); //构造右子树
}
return(OK);
} // CreateBiTree
2、统计二叉树中叶子结点的个数
算法基本思想:
先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。
由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。
void CountLeaf (BiTree T, int& count){
if ( T ) {
if ((!T->lchild)&& (!T->rchild))
count++; // 对叶子结点计数
CountLeaf( T->lchild, count);
CountLeaf( T->rchild, count);
} // if
} // CountLeaf
3、求二叉树的深度(后序遍历)
算法基本思想:
首先分析二叉树的深度和它的左、右子树深度之间的关系。
从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1 。
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}