第六章 树和二叉树第一节 树的类型定义
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时，有且仅有一个结点为二叉树的 根,其余结点被分成两个互不相交的子集，一个作为 左子集,
另一个作为 右子集,每个子集又是一个二叉树。
二叉树的 5种形态：
(a) (b) (c) (d) (e)
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
G H
D E F
B C
A 先序序列,ABDGCEFH
中序序列,DGBAECHF
后序序列,GDBEHFCA
先序遍历递归算法
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
G H
D E F
B C
A
二叉树用链式存储结构表示时，按层遍历的算法实现
（ 1）访问根结点，并将根结点入队；
（ 2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
G H
D E F
B C
A
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); } //处理右孩子
}
}
建立二叉树
void CreateBiTree(BiTree &T)
{
// 在先序遍历二叉树的过程中输入二叉树的 "先序字符串 "，
// 建立根指针为 T的二叉链表存储结构。在先序字符串中，
// 字符 '#'表示空树，其它字母字符为结点的数据元素
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->Lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->Rchild); // 递归建 (遍历 )右子树
}
}
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
在二叉树上查询某个结点
void locate(BiTree T,ElemType x,BiTree& p)
{
// 若二叉树 T 中存在和 x 相同的元素，则 p 指向该结点，否则 p 的值不变,p 的初值为 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;
}
}
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时，有且仅有一个结点为二叉树的 根,其余结点被分成两个互不相交的子集，一个作为 左子集,
另一个作为 右子集,每个子集又是一个二叉树。
二叉树的 5种形态：
(a) (b) (c) (d) (e)
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
G H
D E F
B C
A 先序序列,ABDGCEFH
中序序列,DGBAECHF
后序序列,GDBEHFCA
先序遍历递归算法
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
G H
D E F
B C
A
二叉树用链式存储结构表示时，按层遍历的算法实现
（ 1）访问根结点，并将根结点入队；
（ 2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
G H
D E F
B C
A
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); } //处理右孩子
}
}
建立二叉树
void CreateBiTree(BiTree &T)
{
// 在先序遍历二叉树的过程中输入二叉树的 "先序字符串 "，
// 建立根指针为 T的二叉链表存储结构。在先序字符串中，
// 字符 '#'表示空树，其它字母字符为结点的数据元素
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->Lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->Rchild); // 递归建 (遍历 )右子树
}
}
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
在二叉树上查询某个结点
void locate(BiTree T,ElemType x,BiTree& p)
{
// 若二叉树 T 中存在和 x 相同的元素，则 p 指向该结点，否则 p 的值不变,p 的初值为 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;
}
}
