第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历 6.4线索二叉树 6.5树和森林 6.6树的应用（霍夫曼树及其编码）

Presentation on theme: "第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历 6.4线索二叉树 6.5树和森林 6.6树的应用（霍夫曼树及其编码）"— Presentation transcript:

1 第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历 6.4线索二叉树 6.5树和森林 6.6树的应用（霍夫曼树及其编码）

2 6.1树的基本概念 树的定义 （无序树） 6.1.1树的定义 n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。否则：
当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，......，Tm，其中每个子集本身又是一颗树，并成为根的子树

3 树的ADT描述 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称为空树； 否则R是满足下列条件的二元关系：
(1)D中存在唯一的称为根的元素root，它在R下无直接前驱。 (2)若D-{root}=，则R=；否则存在D-{root}的一个划分D1，D2，...Dm(m>0)，对任意的j≠k(1≤j,k≤m)，有Dj∩Dk=，且对任意的i(1≤i≤m)，存在唯一的数据元素xi∈Di，有<root，xi>∈R； (3)对应于D-{root}的划分，R-{<root，x1>,...<root，xm>}有唯一的一个划分R1，...，Rm(m>0)，对任意的j≠k(1≤j,k≤m)有Rj∩Rk=，且对任意的i(1≤i≤m)，Ri是Di上的二元关系。(Di，Ri)是一棵符合本定义的树，称为根root的子树。

4 基本操作： InitTree（&T） DestroyTree（&T） CreateTree(&T,definition)
TreeEmpty(T) TreeDepth(T) Root(T) Parent(T, x) FirstChild（T，x） Nextsibling(T,x) InsertChild（&T,x,i,p） DeleteChild（&T,x,i） Traverse(T,visit())

5 树的术语 结点：树的数据元素及指向子树的分支。 结点的度：子树的个数。 树的度：树中结点度的最大值。
分支结点、叶子结点：度不为0、为0的结点。 孩子：结点子树的根（后继）称为该结点孩子。 双亲：结点前驱称该结点双亲。 兄弟、祖先、子孙： 结点层次：根结点层次是1，其他结点层次是双亲层次+1。 树深度：结点层次的最大值。 无序树：交互子树不是不同的树。 森林：m(m>=0)个不相交的树构成森林。

6 树的性质 性质1:n个结点，每个结点度di,则： 性质2:度为k的树第i层的结点个数最多 k (i-1)
性质3:深度为h 的k叉树，最多结点数为 性质4:具有n个结点的k叉树深度最小为

7 6.2二叉树 6.2.1二叉树的定义和基本术语 二叉树（binary Tree）
结点的度：非空子树的个数 左孩子，右孩子 叶子结点：左右子树均空的结点；度为零 二叉树的深度：二叉树中叶子结点的最大层次数

8 满二叉树（full binary tree）：所有结点度为2，叶子结点在同一层次
完全二叉树（complete binary tree）：深度h，h-1为满二叉树，h层的结点都集中在左侧

9 二叉树ADT描述 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称BinaryTree为空二叉树；
(1)在D中存在唯一的称为根的元素root，它在R下无直接前驱； (2)若D-{root}=，则R=；否则存在D-{root}={Dl，Dr}， 且Dl∩Dr=； (3)若Dl≠，则Dl中存在唯一的元素xl，<root,xl>∈R，且存在Dl上的关系RlR；若Dr≠，则Dr中存在唯一的元素xr，<root,xr>∈R，且存在Dr上的关系RrR；R={<root,xl>，<root,xr>，Rl，Rr}； (4)(Dl，Rl)是一棵符合本定义的二叉树，称为根的左子树；(Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树。

10 二叉树的操作： InitBiTree(&T) RightChild(T,e) DestroyBiTree(&T)
CreateBiTree(&T,definition) BiTreeEmpty(T) BiTreeDepth(T) Parent(T,e) LeftChild(T,e) RightChild(T,e) LeftSibling(T,e) RightSibling(T,e) InsertChild(&T,p,LR,C) DeleteChild(&T,p,LR) Traverse(T)

11 6.2.2二叉树的几个基本性质 性质1 在二叉树的第i层的结点个数最多 2 (i-1) 性质2 深度为k 的二叉树的最大结点数为2k-1
性质3 任一二叉树T，如果其叶子结点数为n0， 度为2的结点数为n2，则n0=n n0+n1+n2=n=2n2+n1+1 性质4 具有n个结点的完全二叉树深度为 或

12 性质5 如果对一个有n个结点的完全二叉树T的结点按层序（从第一层到第[logn]+1层，层内从左到右）从1开始编号，则对任意一个编号为i(1<=i<=n)的结点有：
如果i＝1，则该结点是二叉树的根，无双亲；如果i>1，，则其双亲结点Parent(i)的编号为[i/2] 如果2i>n，则编号为i 的结点没有左孩子，为叶子结点；否则其左孩子LChild(i)的编号为2i 如果2i+1>n，则编号为i 的结点没有右孩子；否则其右孩子RChild(i)的编号为2i+1

13 6.2.3二叉树的存储结构 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data;
int nodenum; }SqBiTree

14 链式存储结构 二叉链表 包涵data，lchild，rchild三个域，找父亲必须从根开始
三叉链表 包涵data，lchild，rchild，parent四个域，找父亲容易       typedef BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;

15 6.3二叉树遍历 6.3.1问题的提出 二叉树遍历 对所有结点进行访问，且仅被访问一次
LDR、LRD、DLR、DRL、RLD、RDL六种次序 先序（根）DLR、中序（根）LDR、后序（根）LRD 例：右图得三种遍历序列 先序遍历：ABDEC 中序遍历：DBEAC 后序遍历：DEBCA A B C D E

16 遍历的递归实现 先序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 访问根结点； (2) 先序遍历左子树；
(3) 先序遍历右子树。 void PreOrder(BiTree T){ if(!T) return; visite(T->data); //访问根结点 PreOrder(T->lchild); //先序遍历左子树 PreOrder(T->rchild); //先序遍历右子树 }//PreOrder

17 中序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。
void InOrder (BiTree T){ if(!T) return; InOrder (T->lchild); //中序遍历左子树 visite(T->data); //访问根结点 InOrder (T->rchild); //中序遍历右子树 }//InOrder

18 后序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。
void PostOrder (BiTree T){ if(!T) return; PostOrder (T->lchild); //后序遍历左子树 PostOrder (T->rchild); //后序遍历右子树 visite(T->data); //访问根结点 }//InOrder

19 扩展二叉树 先序扩展序列： ABD##E##C## 中序扩展序列： #D#B#E#A#C# 后续序扩展序列： ##D##EB##CA
包络线经过每个内部结点3次 A B C D E # 内部结点 外部结点

20 序列确定二叉树 一个先/中/后序序列能否确定一个二叉树？ 一个先序扩展序列能否确定一个二叉树？ 一个后序扩展序列能否确定一个二叉树？
一个中序扩展序列能否确定一个二叉树？ 一个先序和中序序列能否唯一确定一个二叉树？ 一个中序和后序序列能否确定一个二叉树？ 一个先序和后序能序列能否确定一个二叉树？ 例： 已知先序扩展序列：AB#DF###C#E## 已知后序扩展序列：##D##G#EB###H#FCA 已知先序:ABCDEFGHIJ 中序:BCDAFEHJIG 已知中序:BFDAEGC 后序:FDBGECA

21 遍历的非递归实现 typedef enum {Travel=1,Visit=0} TaskType; typedef struct {
BiTree ptr; TaskType task; }SElemType; void InOrder_iter (BiTree BT,void (* visit)(BiTree)) 用栈实现遍历

22 非递归实现 e.ptr=p->rchild;e.task=Travel;Push(s,e);
Void InOrder(BiTree BT,void (*visit)(BiTree T)){ InitStack(S); e.ptr=BT;e.task=travel; if(BT)push(S,e); while(!StackEmpty(S)){ Pop(S,e); if(e.task=Visit) visit(e.ptr); else if(e.ptr){ p=e.ptr; e.ptr=p->rchild;e.task=Travel;Push(s,e); e.ptr=p;e.task=Visit;Push(s,e); e.ptr=p->lchild;e.task=Travel;Push(s,e); }//if }//while }//InOrder

23 非递归的另一种实现 if(T)-- 中序 else-- 后序？ 算法6.4 先序 Void postorder(BiTree T){
InitStack(S); while(T||!StackEmpty(S)){ while(T){ //左子树 visit(T->data); Push(S,T); T=T->lchild; } if(!StackEmpty(S)){ pop(S,T); //回溯 T=T->rchild; if(T)-- 中序 else-- 也可以改为 if else 后序？

24 算法6.4可以实现后序遍历吗？ typedef strunct {BiTree T; int flag;} SElemType ;
Void postorder(BiTree T){ InitStack(S); while(T||!StackEmpty(S)){ while(T){ //左子树 e=(T,0);Push(S,e);T=T->lchild; } if(!StackEmpty(S)){pop(S,e); //回溯 if(e.flag==0){Push(S,(e.T,1)); T=e.T->rchild;} if(e.flag==1){visit(T->data);T=NULL;}

25 层次遍历 void LayerTraversal（BiTree T）{//按层序遍历二叉树T
InitQueue(Q); //初始化一个空队列 if(T) EnQueue(Q,T); //非空根指针入队 while(!QueueEmpty(Q)){ DeQueue(Q,p); //队头出队 visite(p->data); //访问出队的结点*p if(p->lchild) EnQueue(Q, p->lchild); //*p左孩子入队 if(p->rchild) EnQueue(Q, p->rchild); //*p右孩子入队 } }LayerTraversal

26 6.3.3二叉树应用举例 例 求二叉树的结点数和叶子结点数 （先序）
void Count1(BiTree T,int &C1, int &C2) { if(!T)return; C1++; if(T->lchild==NULL && T->rchild==NULL)C2++; count(T->lchild,C1,C2); count(T->rchild,C1,C2); }

27 nl=Count2(T->lchild); nr=Count2(T->rchild); return(1+nl+nr);
求二叉树的结点数 后序 int Count2(BiTree T) { if(!T) return 0; nl=Count2(T->lchild); nr=Count2(T->rchild); return(1+nl+nr); }//Count2

28 输出二叉树每个结点的层次数 void level(BiTree T,int lev) { //lev=1调用 if(!T) return;
printf(T->data, lev); level(T->lchild,lev+1); level(T->rchild,lev+1); }

29 对比 层次吗？ 输出的还是 void numb(BiTree,int &lev){ if(!T) return;
void Level(BiTree T, int lev){ if(!T)return; printf(T->data, lev); lev++; Level(T->lchild,lev); Level(T->rchild,lev); }//Level void numb(BiTree,int &lev){ if(!T) return; numb (T->lchild,lev); numb (T->rchild,lev); } 输出的还是 层次吗？

30 例6.3求二叉树的深度 int Depth(BiTree T) { //后序 if(!T)return 0;
hl=Depth(T->lchild); //计算左子树深度 hr=Depth(T->rchild); //计算右子树深度 return (hl>hr? hl+1 : hr+1); } void Depth2(BiTree T,int h,int &depth){ //先序 if(!T) return; if(h>depth)depth=h; Depth2(T->lchild,h+1,depth); Depth2(T->rchild,h+1,depth);

31 例 建立二叉树的存储结构(先序扩展二叉树序列)
void CreateBiTree(BiTree &T) 递归 先序 { cin>>ch; if（ch==‘#’)T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }

32 例 复制二叉树 递归算法 后序 Bitree CopyTree(BiTree T){ if(!T)return NTLL;
例 复制二叉树 递归算法 后序 Bitree CopyTree(BiTree T){ if(!T)return NTLL; newlp=CopyTree(T->lchild); newrp=CopyTree(T->rchild); newnode=new BiTNode; newnode->data=T->data; newnode->lchild=newlp; newnode->rchild=newrp; return newnode; }

33 输出二叉树根结点到所有叶子结点的路径 void OutPath(BiTree T，Stack &S){//先序遍历 if(!T)return; Push(S,T); //将当前先序遍历到的结点记入路径 if(!T->lchild && !T->rchild) //该结点是树叶 StackTraverse(S); //输出自栈底至栈顶的结点序列 OutPath(T->lchild, S); //先序遍历左子树 OutPath(T->rchild, S); //先序遍历右子树 Pop(S,e); //当结点的左、右子树遍历结束，该结点出栈 }// OutPath

34 表达式求值(波兰式/逆波兰式) typedef struct BiNode{ double val; //存放操作数
与之前后序序列不能唯一决定二叉树是否矛盾？ typedef struct BiNode{ double val; //存放操作数 char op; //存放运算符 unsigned char tag; //标志 0:操作数 1：运算符 struct BiNode *lchild,*rchild; }BiTNode, *BiTree; double Calculate(BiTree ){ if(T->tag)==0)return T->val; a=Calculate(T->lchild); b=Calculate(T->rchild); return operate(a, T->op, b); } 后缀表达式和二叉树是否唯一对应？ 单目运算符有问题吗？ -a+b*(c-d)*(-f) - + * b / e d c f a 表达式的二叉树表示

35 6.4线索二叉树 typedef struct BiThrNode{ TElemType data; //数据域
struct BiThrNode *lchild,rchild;//左、右指针域 unsigned char ltag,rtag; //左、右标志域 }BiThrNode, *BiThrTree; 0 lchild域为左指针，指向结点的左孩子 1 lchild域为左线索，指示结点的某序前驱 0 rchild域为右指针，指向结点的右孩子 1 lchild域为右线索，指示结点的某序后继 ltag= rtag=

36 A B E G D C F H (a) (b) A B C 1 F D E G H ∧ (c) A B C 1 F ∧ D E G H
B C 1 F D E G H ∧ A B E G D C F H (a) (c) A B C 1 F ∧ D E G H (d) A B C 1 F D E G ∧ H

37 中序线索化二叉树 Visit函数 BiThrTree pre=NULL; //pre是全局变量
void InThreading(BiThrTree T){//T中结点的ltag和rtag的初值是0 if(!T)return; InThreading(T->lchild); //中序线索化T的左子树 if(!T->lchild){ T->ltag=1;T->lchild=pre; //填T的左标志和左线索 } if(pre && !pre->rchild){ pre->rtag=1; pre->rchild=T;//填pre的右标志和右线索 pre=T; //保持pre指向T的中序前驱 InThreading(T->rchild); //中序线索化T的右子树 }//InThreading Visit函数

38 中序线索链表遍历(非递归 O(n)) BiThrTree GetNext(BiThrTree p){//中序线索链表上结点*p的后继
if(p->rtag==1)return p->rchild; q=p->rchild; //指针q指向p的右子树树根 while(q->ltag==0) q=q->lchild; //搜索“最左下”结点 return q; //返回p右子树上最左下结点指针 }//GetNext void InOrder(BiThrTree T){ //利用中序线索来中序遍历二叉树 if(!T) return; p=T; while(p->ltag==0) p=p->lchild; //找中序序列的第一个结点 do{ visit(p->data); //访问p p=GetNext(p); //p移至中序后继 }while(p!=NULL); }InOrder

39 线索二叉树另一种方法 在二叉链表的结点中增加两个指针域，分别指向“前驱”和“后继”，该指针称线索。加上线索的二叉树成为线索二叉树
typedef BiTHrNode{ ElemType data; struct BiTHrNode *lchild,*rchild; struct BiTHrNode *pred,*succ; }BiTHrNode,*BiThrTree;

40 二叉树中序线索化 H ∧ T A B C ∧ D ∧ E ∧ F ∧ G ∧ H ∧

41 线索二叉树的遍历 Void InOrder(BiThrTree H,void (* visit)(BiTree))
p=H->succ; while(p!=H) { visit(p); p=p->next; }

42 线索二叉树的中序建立 Void InOrderThreading(BiThrTree &H, BiThrTree T){
H=new BiThrNode; H->lchild=T;H->rchild=NULL; if(!T){H->pred=H->succ=H;} else{ pre=H; InThreading(T,pre); pre->succ=H;H->pred=pre; } }//InOrderThreading

43 Void InThreading(BiThrTree p, BiThrTree &pre)
{ //p是当前指针，pre是跟随指针，比p慢一个结点 if(!p) return; Inthreading(p->lchild,pre); pre->succ=p; p->pred=pre; pre=p; Inthreading(p->rchild,pre); } //InThreading

44 6.5树和森林 6.5.1树和森林的定义 树的定义 （无序树） 森林的定义
n(n>=0)个数据元素（结点）的有限集D，若D为空集，则为空树。否则： 在D中存在唯一的称为根的数据元素 当n>1时，其余结点可分为m（m>0）个互不相交的有限子集T1，T2，......，Tm，其中每个子集本身又是一颗树，并成为根的子树 森林的定义 是m(m>=0)颗互不相交的树的集合

45 6.5.2 树和森林的存储结构 1、双亲表示法 Const MAX_TREE_SIZE=100 typedef struct PTNode{
Elem data; int parent; }PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r,n; }PTree; 例：前图的双亲存储示意图 r=0 n=11

46 data parent A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F
A -1 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K A B C D E F G H I J K

47 2、孩子表示法 1)孩子链表示法 例：前图孩子链表示，r=0,n=11 typedef struct CTNode{ int child;
struct CTNode *next; }CTNode,*Childptr; typedef struct { Elem data; Childptr firstchild; }CTBox; CTBox nodes[MAX_TREE_SIZE]; int n,r; }CTree; 例：前图孩子链表示，r=0,n=11

48 data fchild A 1 B 2 C ^ 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 1 2 3 ^ 4 5 6 ^ A B C D E F G H I J K 7 8 ^ 9 10 ^

49 2）树的多重链表表示法 typedef struct TNode{ Elem data; struct TNode *child[MAX_NODE]; }TNode,*Tree; 3、孩子双亲表示法 结合了双亲表示法和孩子链表示法 4、树的二叉链表（孩子－兄弟）表示法 typedef struct CSNode{ struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

50 A A B C D E F G H I J K B E C D F J G H I K

51 树与二叉树的变换 以树的结点为二叉树结点 树根与最左子树的父－子关系改为父－左子关系，去除根与其他子树的父－子关系
将其他各子树根（除最右子树）到其右兄弟之间的隐含关系以父－右子关系表示。 对于无右子树的二叉树可以实施逆变换

52 森林到二叉树的变换：F(T1,T2.....Tn)-> B
若森林F空，则二叉树B空。 由森林中的第一颗树的根结点ROOT（T1）作为二叉树的根，其子树转换为二叉树的左子树。 由森林中其余树构成的森林{T2，T Tn}转化得到的二叉树B的右子树 二叉树到森林的变换：B -> F（T1，T Tn） 若二叉树B空，则森林F空。 二叉树的根为森林中的第一颗树的根结点ROOT（T1），二叉树的左子树转化为T1的子树 二叉树的右子树转化为森林{T2，T Tn}

53 6.5.3 树和森林的遍历 树遍历的三种搜索路径（右图） 先根遍历 ABCEHDFG 后根遍历 BHECFGDA 层次遍历 ABCDEFGH
若树为空，则空操作；否则 1）访问根结点； 2）按照从左至右次序先根遍历根结点的每一棵子树。 后根遍历 BHECFGDA 1）按照从左至右次序后根遍历根结点的每一棵子树； 2）访问根结点。 层次遍历 ABCDEFGH 从树的第1层开始，自上而下逐层遍历，在同一层中，按从左至右的次序逐个访问结点。 A B C D E F G H

54 先根遍历树（孩子链表存储） void PreOrderTree(CTNode T[], int root){
//T[]是表头结点数组，root是树根在T中的位置下标 if(root==-1) return; //空树，空操作 visite(T[root].data); //访问根 for(p=T[root].firstchild; p; p=p->next) PreOrderTree(T, p->child); //依次先根遍历根的各个子树 }//PreOrderTree

55 后根遍历树（孩子链表存储） void void PostOrderTree(CTNode T[], int root){
//T[]是表头结点数组，root是树根在T中的位置下标 if(root==-1) return; //空树，空操作for(p=T[root].firstchild; p; p=p->next) PostOrderTree(T, p->child); visited(T[root].data); //访问根 } //PostOrderTree

56 对森林遍历的两种方法：（右图） 先序遍历：(ABCDEFGHIJ) 若森林非空 中序遍历：(BCDAFEHJIG) 若森林非空
访问森林中的第一颗树根结点 先序遍历第一颗树中根结点的子树森林 先序遍历除去第一颗树之后剩余树构成的森林 中序遍历：(BCDAFEHJIG) 若森林非空 中序遍历第一颗树中根结点的子树森林 中序遍历除去第一颗树之后剩余树构成的森林 A B C D E F G H I J

57 树的先根遍历和后根遍历可利用对应二叉树的先序和中序遍历算法实现
森林的先序遍历和中序遍历即是对应二叉树的先序和中序遍历

58 树和森林遍历的应用 求树的深度 int TreeDepth1(CSTree T){ //T用孩子兄弟链表存储
int maxh=0; //maxh用来记录T所有子树深度的最大值 if(!T) return 0; //空树的深度为0 for(p=T->firstchild; p; p=p->nextsibling){ h=TreeDepth(p); //计算一棵子树的深度 if(h>maxh) maxh=h; //求子树深度的最大值 } return maxh+1； } //TreeDepth1

59 int TreeDepth2(CTNode T[], int root){
//计算树的深度，树用孩子链表存储 //T是表头结点数组, root是根结点在数组T中的位置下标 int maxh=0; //maxh用来记录各个子树深度的最大值 if(root==-1) return 0; //空树的深度为0 for(p=T[root].firstchild; p!=NULL; p=p->next){ h=TreeDepth2(T, p->child); //计算子树的深度 if(h>maxh) maxh=h; //求子树深度的最大值 } return 1+maxh; }// TreeDepth2

60 求森林或树的深度 int TreeDepth(CsTree T) //后序 {//孩子兄弟链表存储 if(!T)return 0;
h1=TreeDepth(T->firstchild); h2=TreeDepth(T->nextsibling); return (h1+1>h2)?h1+1:h2; }

61 求树的度 void TreeDegree(CSTree T, int °ree)
if(!T)return; for(k=0,p=T->firstchild; p; p=p->nextsibling){ k++; TreeDegree(p,degree); } if(k>degree) degree=k; } //TreeDegree

62 递归用来遍历左分支，即真正的孩子 while循环用来遍历右分支几兄弟 栈底到栈顶为一条路径 例 输出树中从根结点到所有叶子结点的路径
void OutPath(CSTree T,Stack &S) { while(T){ Push(S,T->data); if(!T->firstchild)StackTraverse(S); else OutPath(T->firstchild,S); Pop(S,e); T=T->nextsibling; } 递归用来遍历左分支，即真正的孩子 while循环用来遍历右分支几兄弟 栈底到栈顶为一条路径

63 树的层次遍历 void TreeLayerOrder (CSTree T){ //层序遍历树T，T用孩子兄弟链表存储
if(!T)return; InitQueue(Q); //初始化一个空队列Q EnQueue(Q,T); //树根入队 while(!EmptyQueue(Q)){ DeQueue(Q, s); //队头元素s出队 visite（s->data）; //访问s for(p=s->firstchild; p!=NULL; p=p->nextsibling) EnQueue(Q,p); //s的所有孩子依次入队 } }// TreeLayerOrder

64 例 建立树的存储结构――孩子－兄弟链表 void CreateTree(CSTree T) { T=NULL; for(cin>>fa>>ch;ch!=‘#’;cin>>fa>>ch){ p=new CSNode; p->data=ch;p->firstchild=p->nextsibling=NULL; EnQueue(Q,p); if(fa==‘#’)T=p; else{ while(GetHead(Q,s) && s->data!=fa){DeQueue(Q,s);} if(!s->firstchild){s->firstchild=p;r=p;}; else{r->nextsibling=p;r=p;} }//else }//for } //CreateTree

65 二叉排序树 二叉排序树定义： 或空树，或满足如下特征 若左子树不空，则左子树上的所有结点值均小于根结点值
若右子树不空，则右子树上的所有结点值均大于或等于根结点值 左右子树分别也是二叉排序树 typedef TelemType RcdType; typedef KeyType int; void Insert_BST(BiTree &T, TElemType e) 在二叉排序树中插入一个结点

66 void Insert_BST(BiTree &T, TElemType e) {
s=new BiTNode; s->data=e;s->lchild=s->rchild=NULL; if(!T)T=s; //第一个结点 else{ p=T; while(p) if(e.key<p->data.key){f=p;p=p->lchild;} else {f=p;p=p->rchild;} if(e.key<f->data.key)f->lchild=s; else f->rchild=s; }//else }

67 利用二叉排序树排序 void BSTSort(SqTable &L) { BiTree=NULL;
for(i=1;i<L.length;i++); Insert_BST(T,L.r[i]); i=1; InOrder(T,Output(T,L,i)); } //BSTSort Void Output(BiTree T,SqTable L,int &i){ L.r[i++]=T->data; }

68 补充：求排序二叉树的最大元素 keytype getmax(BiTree &T) { if(!T) errormessage(“NULL Tree,Can’t get value!”); return -1; } p=T; while(p->rchild)p=p->rchild; return p->data.key;

69 6.6哈夫曼树及其应用 路径：树中一个结点到另一结点之间的分支 路径长度：路径上分支的数目 树的路径长度：树根到每个结点的路径长度之和
结点带权路径长度：从树根到该结点之间的路径长度与该结点上所带权值的乘积 树的带权路径长度：WPL＝Σωklk (叶子结点) 最优二叉树（霍夫曼树）: n个叶子构成的所有二叉树中，其中WPL最小的二叉树称霍夫曼树。

70 例 将百分制转换为五分制 分数 0~59 60~69 70~79 80~89 90~100 比例 0.05 0.15 0.40 0.30 0.10 <60 <80 不及 <70 <70 <90 及格 <80 <60 中 良 优 中 <90 不及 及格 良 优 10000个输入数据，左图需要判断31500次，右图为22000次

71 霍夫曼树算法 1)根据给定的n个权值{w1,w wn}，构成n颗二叉树的集合F＝{T1,T Tn}，每个二叉树只有一个带权Wi的根结点。 2)在F中选取两颗根结点的权值最小的树作为左右子树，构造一个新二叉树，且置其根结点的权值为两个子树根结点权值之和。 3)在F中删除这两颗树，同时在F中加入新树。 4)重复2）、3）直至F只含一颗树为止

72 霍夫曼树存储结构 创建霍夫曼树 typedef struct{ int weight; int parent,lchild,rchild;
}HTNode; typedef HTNode *HuffTree; 创建霍夫曼树 15 6 3 1 2 9 4 5

73 void HuffmanTree(HuffTree &HT, WeightType *w, int n){
m=n* //计算哈夫曼树结点总数m HT=new HTNode[m+1]; //分配HT数组空间，0号单元空闲 for(i=1;i<=m;i++){ //初始化数组HT[] HT[i].weight= i<=n ? w[i]: 0; HT[i].lchild=HT[i].rchild=HT[i].parent=0; } for(i=n+1;i<=m;i++){ //主循环，完成n-1次合并 Select(HT,n,i,s1,s2); //在HT[1..i-1]中选择parent为0且weight为最小的两个结点, HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; HT[s1].parent=HT[s2].parent=i; }//HuffmanTree

74 Huffman树终态 Huffman树初态 1 2 4 3 5 6 7 8 9 1 2 6 4 8 3 7 5 9 15 weight
parent lchild rchild 1 2 4 3 5 6 7 8 9 weight parent lchild rchild 1 2 6 4 8 3 7 5 9 15 Huffman树终态 Huffman树初态

75 例 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计霍夫曼编码
前缀编码： 任一字符的编码都不是另一字符编码的前缀 霍夫曼编码： 以n种字符出现的概率（频率）为权，设计一个赫夫曼树，由此得到的二进制前缀编码 例 有8个字符a、b、c、d、e、f、g、h，出现频率为5%、29%、7%、8%、14%、23%、3%、11%，设计霍夫曼编码 先序遍历 HuffmanCoding Coding

76 void HuffmanCoding(HuffTree HT, char **&HC, int n){
//从哈夫曼树HT上求得n个叶子结点的哈夫曼编码 //并存入数组HC中 Stack S; //S是一个字符型的顺序栈 InitStack(S); //初始化栈S； HC=(char**)malloc(sizeof(char*)* (n+1)) //分配数组HC的空间 Coding(HT,2*n-1,HC,S); //哈夫曼树根结点下标为2n-1 }//HuffmanCoding

77 void Coding(HuffTree HT,int root,char **HC,SqStack &S){
if(root==0)return; if(HT[root].lchild==0){ //root是树叶 push(S, ‘\0’); //字符串结束标志‘\0’进栈 HC[root]=(char*)malloc((StackLength(S)); strcpy(HC[root], S.elem); //复制叶子的编码 Pop(S, ch); //字符串结束标志‘\0’出栈 } Push(S,‘0’); //向左转,‘0’进栈 coding(HT, HT[root].lchild, HC, S); //遍历左子树 Pop(S); Push(S,‘1’); //向右转,‘1’进栈 coding(HT, HT[root].rchild, HC, S); //遍历右子树 }//Coding

78 F D 1 C A B E 5 6 7 4 3 HT weight parent lchild rchild 1 4 8 2 3 7 10 5 9 6 11 15 26 HC 1 2 3 4 5 6 110\0 1111\0 10\0 00\0 1110\0 01\0

79 堆排序 堆排序的实现 typedef SqTable HeapType;
调整为堆 ，从结点[n/2]到1依次调整 交换数据，再调整堆顶元素，恢复成堆 typedef SqTable HeapType; void HeapAdjust(HeapType &H,int s,int m) 调整H.r[s..m]为大顶堆,其中仅H.r[s]不满足大顶堆条件 void HeapSort(HeapType &H) 从结点[n/2]到1依次调整，使H为大顶堆 交换堆顶与堆底记录，再利用HeapAdjust重新调整为堆 重复进行第二步，直到所有元素有序

80 void HeapAdjust(HeapType &H,int s,int m){
//调整H.r[s..m]为大顶堆,其中仅H.r[s]不满足条件 rc=H.r[s]; for(j=2*s;j<=m;j*=2){ if(j<m && H.r[j].key<H.r[j+1].key)++j; if(rc>=H.r[j].key)break; H.r[s]=H.r[j];s=j; }//for H.r[s]=rc; }

81 void HeapSort(HeapType &H){
for(i=H.length/2;i>0;--i) HeapAdjust(H,i,H.length); w=H.r[1];H.r[1]=H.r[H.length];H.r[H.length]=w; for(i=H.length-1;i>1;--i){ //i为2交换后无需调整 HeapAdjust(H,1,i); w=H.r[1];H.r[1]=H.r[i];H.r[i]=w; }//for }//HeapSort