清华大学：数据结构（冯毅）：yanjin crosoft Word 文档

第六章 树和二叉树
第一节 树的类型定义
A 为“根”
T1、T2和T3都是一棵树，称为A的子树。
称根和子树根之间的连线为“分支”
结点分支的个数定义为“结点的度”，如结点B的度为2，D 的度为3。
树中所有结点度的最大值定义为“树的度”。
称度为零的结点为“叶子”
或“终端结点”
所有度不为零的结点
被称作"分支结点"
基本定义森林为 m(m≥0) 棵互不相交的树的集合。
树的深度定义为树中叶子结点所在最大层次数。
称根结点为子树根的"双亲"。
称子树根为根结点的"孩子“
根的所有子树根互为“兄弟”。
有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
树的抽象数据类型,
ADT Tree {
　数据对象：D是具有相同特性的数据元素的集合。
　数据关系：
若 D 为空集，则称为空树；
若 D 中仅含一个数据元素，则关系R为空集；
否则 R={H}，
(1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；
(2) 当n>1时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限集 T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 <root,xi> H,i=1,2,…,m。
基本操作：
　{结构初始化}
InitTree(&T);
　操作结果：构造空树 T。
CreateTree(&T,definition);
　初始条件：definition 给出树T的定义。
　操作结果：按 definition 构造树 T。
　{销毁结构}
DestroyTree(&T);
　初始条件：树 T 存在。
　操作结果：销毁树 T。
{引用型操作}
TreeEmpty(T);
　初始条件：树 T 存在。
　操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。
　?
TreeDepth(T);
　初始条件：树T存在。
　操作结果：返回T的深度。
Root(T);
　初始条件：树 T 存在。
　操作结果：返回 T 的根。
Value(T,cur_e);
　初始条件：树 T 存在，cur_e 是 T 中某个结点。
　操作结果：返回 cur_e 的值。
Parent(T,cur_e);
初始条件：树 T 存在，cur_e 是 T 中某个结点。
操作结果：若 cur_e 是T的非根结点，则返回它的双亲，否则返回"空"。
LeftChild(T,cur_e);
初始条件：树 T 存在，cur_e 是 T 中某个结点。
操作结果：若 cur_e 是T的非叶子结点，则返回它的最左孩子，否则返回"空"。
　
RightSibling(T,cur_e);
初始条件：树 T 存在，cur_e 是 T 中某个结点。
操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回"空"。
TraverseTree(T,visit());
初始条件：树T存在，visit 是对结点操作的应用函数。
操作结果：按某种次序对 T 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失败，则操作失败。
{加工型操作}
Assign(T,cur_e,value);
　初始条件：树T存在，cur_e 是 T 中某个结点。
　操作结果：结点 cur_e 赋值为 value。
ClearTree(&T);
　初始条件：树 T 存在。
　操作结果：将树 T 清为空树。
　
InsertChild(&T,&p,i,c);
　初始条件：树 T 存在，p 指向T中某个结点，1≤i≤p 所指结点的度＋1，非空树 c 与 T 不相交。
　操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。
DeleteChild(&T,&p,i);
　初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 指结点的度。
　操作结果：删除 T 中 p 所指结点的第 i 棵子树。
} ADT Tree
树和线性结构对照,
第二节 二叉树类型定义：二叉树是另一种树形结构。它与树形结构的区别是：
（1）每个结点最多有两棵子树；
（2）子树有左右之分。
二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。
6.2.1 二叉树的类型定义
ADT BinaryTree {
数据对象：D 是具有相同特性的数据元素的集合。
数据关系：
　若 D 为空集，称 BinaryTree 为空二叉树；
　否则 关系 R={H}：
　 (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱；
　 (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点,它是 root 的"左后继"(<root,>∈H)，如果右子树 R 不空，则必存在一个根结点 为 root 的"右后继"(<root,>∈H)。
基本操作P：
{结构初始化}
InitBiTree(&T);
　操作结果：构造空二叉树 T。
　CreateBiTree(&T,definition);
　初始条件：definition 给出二叉树 T 的定义。
　操作结果：按 definition 构造二叉树 T。
　{销毁结构}
DestroyBiTree(&T);
　初始条件：二叉树 T 存在。
　操作结果：销毁二叉树 T。
{引用型操作}
BiTreeEmpty(T);
　初始条件：二叉树 T 存在。
　操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。
　?
BiTreeDepth(T);
　初始条件：二叉树 T 存在。
　操作结果：返回 T 的深度。
Root(T);
　初始条件：二叉树 T 存在。
　操作结果：返回 T 的根。
Value(T,e);
　初始条件：二叉树 T 存在，e 是 T 中某个结点。
　操作结果：返回 e 的值。
Parent(T,e);
初始条件：二叉树 T 存在，e 是 T 中某个结点。
操作结果：若e是T的非根结点，则返回它的双亲，否则返回"空"。
LeftChild(T,e);
初始条件：二叉树 T 存在，e 是 T 中某个结点。
操作结果：返回 e 的左孩子。若 e 无左孩子，则返回"空"。
RightChild(T,e);
初始条件：二叉树 T 存在，e 是 T 中某个结点。
操作结果：返回 e 的右孩子。若 e 无右孩子，则返回"空"。
LeftSibling(T,e);
初始条件：二叉树 T 存在，e 是 T 中某个结点。
操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回"空"。
RightSibling(T,e);
初始条件：二叉树 T 存在，e 是 T 的结点。
操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回"空"。
PreOrderTraverse(T,visit());
初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。
操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。
InOrderTraverse(T,vsit());
初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。
操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。
PostOrderTraverse(T,visit());
初始条件：二叉树T存在，visit 是对结点操作的应用函数。
操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。
LevelOrderTraverse(T,visit());
　初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。
　操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。
{加工型操作}
ClearBiTree(&T);
　初始条件：二叉树 T 存在。
　操作结果：将二叉树 T 清为空树。
Assign(&T,&e,value);
　初始条件：二叉树 T 存在，e 是 T 中某个结点。
　操作结果：结点 e 赋值为 value。
InsertChild(&T,p,LR,c);
　初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。
　操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。
DeleteChild(&T,p,LR);
　初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。
　操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。
} ADT BinaryTree
6.2.2 二叉树的几个特性
一、在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。
二、深度为k的二叉树中至多含有 2k-1 个结点，(k≥1)。
三、对任何一棵二叉树 T，如果其终端结点数为n0，度为2的结点数为n2，则n0 =n2+ 1
若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。
假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应，则称这类二叉树为完全二叉树。
第三节 二叉树的存储表示
6.3.1 顺序存储结构
二叉树的顺序存储结构的定义如下：
const MAXSIZE = 100; // 暂定二叉树中结点数的最大值为100
typedef struct {
　ElemType *data; 　// 存储空间基址(初始化时分配空间)
　int nodeNum; // 二叉树中结点数
} SqBiTree; 　 // 二叉树的顺序存储结构
6.3.2 链式存储结构
二叉树的二叉链表存储表示
typedef struct BiTNode {
　ElemType data;
　struct BiTNode *Lchild,*Rchild;// 左、右孩子指针
} *BiTree;
二叉树的三叉链表存储表示
typedef struct TriTNode {
　ElemType data;
　struct BiTNode *Lchild,*Rchild; //左、右孩子指针
　struct BiTNode *parent; // 双亲指针
} *TriTree;
二叉树的双亲链表存储表示
typedef struct BPTNode { // 结点结构
　ElemType data;
　int *parent; // 指向双亲的指针
　char LRTag; // 左、右孩子标志域
} BPTNode
第四节 二叉树的遍历
“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。
由于二叉树中每个结点都有两个后继，则可以有三条搜索路径：
1) 先左(子树)后右(子树)；
2) 先右(子树)后左(子树)；
3) 按层次从上到下。
6.4.1 先左后右的遍历 6-4-1遍历.swf
先序遍历递归算法
void PreOrder(BTree BT)
{
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild); }
}
6-4-2-1.swf
中序遍历递归算法
void InOrder(BTree BT)
{
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
} 6-4-2-2.swf
后序遍历递归算法
void PostOrder(BTree BT)
{
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 6-4-2-3.swf
按层次遍历二叉树
按层次遍历该二叉树的序列为,
ABCDEFGH
二叉树用链式存储结构表示时，按层遍历的算法实现
（1）访问根结点，并将根结点入队；
（2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
void LevelOrder(BTree *BT)
{
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p);
//访问根结点，并将根结点入队
while (!QueueEmpty(Q))
{//当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p->Lchild)
{ Visite(p->Lchild) ; EnQueue(&Q,p->Lchild); } //处理左孩子
if (!p->Rchild)
{ Visite(p->Rchild);EnQueue(&Q,p->Rchild); } //处理右孩子
}
}
¨á￠?t2?ê÷
void CreateBiTree(BiTree &T)
{
//?ú?èDò±éàú?t2?ê÷μ?1y3ì?Dê?èt2?ê÷μ?"?èDò×?·?′?"￡?
//?¨á￠?ùa Tμt2?á′±í′?′￠?á11?￡?ú?èDò×?·?′D￡?
// ×?·?'#'±íêê÷￡ü××?·a?áμ?μ?êy?Y?a
cin >> ch ￡?
if (ch=='#') T=NULL;//?¨ê÷
else {
T = new BiTNode ; // "·ê"2ù×÷?aéú3é?ù?áμ?
T->data = ch;
CreateBiTree(T->Lchild);// μY1é?¨(±éàú)×ó×óê÷
CreateBiTree(T->Rchild);// μY1é?¨(±éàú)óò×óê÷
}
}
6-4-6.swf
统计二叉树中叶子结点的个数
void CountLeaf (BiTree T,int& count)
　{
// 先序遍历二叉树，以 count 返回二叉树中叶子结点的数目
if ( T ) {
　if ((!T->Lchild)&& (!T->Rchild))
count++; 　// 对叶子结点计数
CountLeaf( T->Lchild,count);
CountLeaf( T->Rchild,count);
} // if
　}
求二叉树的深度
void BiTreeDepth(BiTree T,int level,int &depth)
　{// T指向二叉树的根，level 为 T 所指结点所在层次，其初值为1，depth 为当前求得的最大层次,其初值为0
if (T){
　if (level>depth) depth=level;
　BiTreeDepth(T->Lchild,level+1,depth);
　BiTreeDepth(T->Rchild,level+1,depth);
}
　} 6-4-3求二叉树的深度,swf
复制二叉树
生成一个二叉树的结点的算法,
BiTNode *GetTreeNode(TElemType item,BiTNode *lptr,BiTNode *rptr)
　{// 生成一个其元素值为 item，左指针为 lptr，右指针为 rptr 的结点
T = new BiTNode; T-> data = item;
T-> Lchild = lptr; T-> Rchild = rptr;
return T;
　}
后序遍历复制二叉树的操作为,
BiTNode *CopyTree(BiTNode *T)
　{
　// 已知二叉树的根指针为 T，本算法返回它的复制品的根指针
if (!T )
　return NULL; 　 　// 复制一棵空树
if (T->Lchild)
　newlptr = CopyTree(T->Lchild); 　 // 复制(遍历)左子树
else newlptr = NULL;
if (T->Rchild)
　newrptr = CopyTree(T->Rchild); // 复制(遍历)右子树
else newrptr = NULL;
newnode = GetTreeNode(T->data,newlptr,newrptr); // 生成根结点
return newnode;
　} 6-4-5后序遍历复制.swf
ú?t2?ê÷é?2é?ˉ?3áμ?
void locate(BiTree T,ElemType x,BiTree& p)
{
// èt2?ê÷ T?D′úoí x?àí?μa￡ò pòáμ?￡?·ò p μμ2?±?￡?p μ?3μ?a NULL
if (T)
{ if (T->data==x) p=T;
locate(T->lchild,x,p);
locate(T->rchild,x,p);
}
}
中序遍历（非递归）
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;
表达式的二叉树
二叉树的线索链表
将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。
typedef enum PointerType{ Link=0,Thread=1 };
// 定义指针类型，以 Link 表示指针，Thread 表示线索
typedef struct BiThrNode{
　ElemType data;
　struct BiThrNode *Lchild,*Rchild; //左右指针
　PointerType LTag,RTag; // 左右指针类型标志
} *BiThrTree;
在线索链表中添加了一个"头结点"，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点
以中序线索链表为存储结构的中序遍历
void InOrderTraverse_Thr(BiThrTree T,void (*Visit)(ElemType e))
　{// T 指向中序线索链表中的头结点，头结点的左指针 Lchild 指向二叉树的根结点，头结点的右线索 Rchild 指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对树中每个元素调用函数 Visit 进行访问操作
p = T->Lchild; // p 指向二叉树的根结点
while (p!= T)
{ // 空树或遍历结束时，p==Thead
　while (p->LTag==Link) p = p->Lchild;
　Visit(p->data); 　 　// 访问其左子树为空的结点
　while (p->RTag==Thread && p->Rchild!=T)
{
p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点
　 }
　p = p->Rchild; // p 进至其右子树根
}
　}
p = T->Lchild; // p 指向二叉树的根结点
while (p!= T)
{ // 空树或遍历结束时，p==Thead
　while (p->LTag==Link) p = p->Lchild;
　Visit(p->data); 　 　// 访问其左子树为空的结点
　while (p->RTag==Thread && p->Rchild!=T)
{
p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点
　 }
　p = p->Rchild; // p 进至其右子树根
} 6-5-1.swf
线索链表的生成
void InThreading(BiThrTree p，BiThrTree& pre)
{
// 对 p 指向根结点的二叉树进行中序遍历，遍历过程中进行“中序线索化”。若 p 所指结点的左指针为空，则将它改为“左线索”，若 pre所指结点的右指针为空，则将它改为“右线索”。指针 pre 在遍历过程中紧随其后，即始终指向 p 所指结点在中序序列中的前驱。
　if (p) {
InThreading(p->Lchild,pre); // 对左子树进行线索化
if (!p->Lchild)
　{ p->LTag = Thread; p->Lchild = pre; } // 建前驱线索
if (!pre->Rchild)
　{ pre->RTag = Thread; pre->Rchild = p; } // 建后继线索
pre = p; 　 // 保持 pre 指向 p 的前驱
InThreading(p->Rchild,pre); // 对右子树进行线索化
　}
}
void InOrderThreading(BiThrTree &Th,BiThrTree BT)
{ // BT为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链表，Thead 指向线索链表中的头结点。
　BiThrTree pre;
　if (!(Th = new BiThrNode)) exit (1); // 存储分配失败
　Th->LTag = Link; Th->RTag =Thread;　// 建头结点
　Th->Rchild = Th; // 右指针回指
　if (!BT) Th->Lchild = Th; 　// 若二叉树空，则左指针回指
　else {
Th->Lchild = BT; pre = Thead;
InThreading(BT,pre); 　// 中序遍历进行中序线索化
pre->Rchild = Th; pre->RTag = Thead; // 对中序序列中最后一个结点进行线索化
Th->Rchild = pre; 　// 建非空树的头结点的"右线索"
}
} 6-5-2.swf
树和森林的存储表示
1 树的双亲表示法
const MAX_TREE_SIZE = 100;
typedef struct { // 结点结构
　ElemType data;
　int parent; // 双亲位置域
} PTNode;
typedef struct { // 树结构
　PTNode nodes[MAX_TREE_SIZE];
　int r,n; // 根的位置和结点数
} PTree;
2 树的孩子表示法
树的孩子链表存储表示
typedef struct CTNode {　 // 孩子结点
　int child;
　struct CTNode *next;
} *ChildPtr;
typedef struct {
　ElemType data; // 结点的数据元素
　ChildPtr firstchild; // 孩子链表头指针
} CTBox;
typedef struct {
　CTBox nodes[MAX_TREE_SIZE];
　int n,r; 　 // 结点数和根结点的位置
} CTree;
3 树和森林的孩子兄弟表示法
存储表示
typedef struct CSNode{
　ElemType data;
　struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree;
firstchild 指向该结点的"第一个"子树根结点，nextsibling 指向它的"下一个"兄弟结点。
树的孩子-兄弟链表
森林的孩子-兄弟链表
森林和二叉树的转换
森林－>二叉树 6-6-1.swf
二叉树(森林 6-6-2.swf
树的遍历
一、先根(次序)遍历树
若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；
ABEHIJCDFGK 6-7-3.swf
二、后根(次序)遍历树
若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；
HIJEBCFKGDA 6-7-4.swf
森林的遍历
一、先序遍历森林
若森林不空，则可依下列次序进行遍历
(1) 访问森林中第一棵树的根结点；
(2) 先序遍历第一棵树中的子树森林；
(3) 先序遍历除去第一棵树之后剩余的树构成的森林。
二、中序遍历森林
若森林不空，则可依下列次序进行遍历：
(1) 中序遍历第一棵树中的子树森林；
(2) 访问森林中第一棵树的根结点；
(3) 中序遍历除去第一棵树之后剩余的树构成的森林。
求森林的深度
森林的深度 = Max{每一棵树的深度}
树的深度 = 其子树森林的深度+1
int Depth_Tree( CSTree T )
{
// T 是以孩子-兄弟链表存储的森林的头指针，返回该森林的深度
　if (!T) return 0;
　else {
dep = 0; // 初始化森林的深度为0
p = T; 　// 指针 p 指向第一棵树的根
while (p) {
　d = Depth_Tree(p->firstchild); // 返回 *p 的子树森林的深度
　if (d+1>dep) dep=d+1; // 求各棵树的深度的最大值
　p=p->nextsibling; // 指针 p 移向下一棵树的根
}
return dep;
　}
}