第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林

Presentation on theme: "第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林"— Presentation transcript:

1 第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林
第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树及其应用

2 1.教学目的 2 .教学要求 掌握一种重要的非线性结构——树的定义、特点、典型算法及在实际中的实用。 ① 理解二叉树的结构特点。
② 掌握二叉树的各种存储结构的特点及适用范围。 ③ 掌握按各种次序遍历二叉树的递归和非递归算法。 ④ 掌握树的各种存储结构、特点。 ⑤ 掌握建立最优二叉树和哈夫曼编码的方法。

3 3．教学重点： 4．教学难点： ① 掌握二叉树的定义、性质和存储结构。 ② 掌握二叉树的遍历方法及递归和非递归算法实现。
③ 掌握建立最优二叉树和哈夫曼编码的方法。 4．教学难点： ① 线索二叉树。 ② 遍历二叉树的递归和非递归算法。

4 6.1 二叉树 6.1.1 二叉树的定义 ——二叉树（Binary Tree）是n（n≥0）个数据元素的有限集合。
D C E F 该集合或者为空, 或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

5 二叉树特点 五种基本形态 ①左子树和右子树是两棵互不相交的二叉树； ②每个结点至多有两棵子树，且有左右之分，次序不能任意颠倒；
③有序性。即若左、右子树颠倒，就成为另一棵二叉树。 五种基本形态 左子树 左子树 左子树 左子树 （ｅ） （ａ） （ｂ） （ｃ） （ｄ）

6 基本术语 结点: 包含一个数据元素及指向子树的分支。 结点的度: 结点所拥有的子树的个数。  叶子结点（终端结点）: 度为0的结点。
分支结点（非终端结点）: 度不为0的结点。 左孩子结点: 结点的左子树的根，称为该结点的左孩子。(右孩子定义相同) 双亲结点: 结点的直接前驱。 兄弟结点: 同一双亲的孩子结点之间互称兄弟结点。 祖先结点: 从根结点到该结点路径上的所有结点.。 子孙结点: 以某结点为根的子树中的任一结点。 二叉树的度: 二叉树中各结点度的最大值。 结点的层次: 从根开始定义，根结点层次为1，根孩子的层次为2，依此类推。 二叉树的高度（深度）: 叶子结点的最大层次数。

7 基本术语 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，称作满二叉树。
顺序表示：从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，……，n）。 (a)满二叉树 (b)非满二叉树

8 基本术语 完全二叉树：深度为k，结点数为n的二叉树，如果其结点1～n的位置序号分别与满二叉树的结点1～n的位置序号一一对应，则为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。 (a)满二叉树 (a)完全二叉树

9 6.1.2 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1)。  证明： 用数学归纳法。
性质2: 深度为k的二叉树至多有2k-1个结点（k≥1）。 性质3: 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。 性质4：具有n个结点的完全二叉树的深度为［log2n］+1。 

10 性质5: 对于具有n个结点的完全二叉树， 如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号， 则对于任意的序号为i的结点有： 
（1）如i=1，则i是根结点，无双亲； 如i>1，则i的结点的双亲结点序号为［i/2］。 （2）如2i>n，则i的结点无左孩子；否则Lchild(i)=2i （3）如2i＋1>n，则i的结点无右孩子；否则Rchild(i)=2i+1

11 6.2 二叉树的基本操作与存储实现 6.2.1 二叉树的基本操作 ⑴初始化操作：Initiate(bt) 初始条件：二叉树bt不存在。
操作结果：构造一个空的二叉树。 ⑵求二叉树bt的根结点：Root(bt) 初始条件：二叉树bt存在。 操作结果：若bt为非空二叉树，返回bt的根，否则，返回“空”。 ⑶建树操作：Create(x，lbt，rbt) 初始条件：二叉树bt不存在。 操作结果：生成一棵以x为根结点，以二叉树lbt和rbt为左子树和右子树的二叉树。

12 ⑷求双亲操作：Parent(bt，x) 初始条件：二叉树bt存在。 操作结果：若结点x是二叉树的根结点或二叉树bt中无结点x，则返回“空”，否则，返回结点x的双亲结点。 ⑸求左孩子操作：LeftChild(bt，x） 初始条件：二叉树bt存在。 操作结果：若结点x为叶子结点或x不在bt中，则返回“空”，否则，返回结点x的左孩子。 ⑹求右孩子操作：ReftChild(bt，x） 初始条件：二叉树bt存在。 操作结果：若结点x为叶子结点或x不在bt中，则返回“空”，否则，返回结点x的右孩子。

13 (7)插入左子树操作：InsertL(bt，x，parent)
操作结果：将以结点x为根且右子树为空的二叉树插入到二叉树bt中作为结点parent的左子树。如果结点parent原来有左子树，则将结点parent原来的左子树作为结点x的右子树。 (8)插入右子树操作：InsertR(bt，x，parent) 初始条件：二叉树bt存在。 操作结果：将以结点x为根且右子树为空的二叉树插入到二叉树bt中作为结点parent的右子树。如果结点parent原来有右子树，则将结点parent原来的右子树作为结点x的右子树。 (9)删除左子树操作：DeleteL(bt，parent) 初始条件：二叉树bt存在。 操作结果：在二叉树bt中删除结点parent的左子树。

14 (10)删除左子树操作：DeleteL(bt，parent)
(11) 查找操作： Search(bt，x) 初始条件：二叉树bt存在。 操作结果：在二叉树bt中查找数据元素x。 (12)遍历操作： Traverse(bt) 初始条件：二叉树bt存在。 操作结果：按某种方式访问二叉树中每个结点一次且仅一次。

15 6.2.2 二叉树的存储 1 顺序存储结构 A B C D E F G H I J K L (a)一棵二叉树 (b)改造后的完全二叉树

16 二叉树的顺序存储表示可用C语言定义如下：
#define MAXNODE typedef datatype SqBiTree[MAXNODE]； 0号单元存放结点数目 SqBiTree bt ;

17 2 链式存储结构 （1）二叉链表存储 LChild Data RChild 数据域 右孩子域 左孩子域

18 二叉链表的存储结构描述用C语言如下： typedef struct Node { datatype data;  struct Node *LChild;  struct Node *RChild;  }BiTNode, *BiTree; BiTree bt; 头指针bt (a) 二叉树 (b) 带头指针的二叉链表

19 LChild Data parent RChild
指向双亲的指针 （2）三叉链表存储 LChild Data parent RChild 优点：既便于查找孩子结点，又便于查找双亲结点； 缺点：增加了空间开销。 (a) 二叉树 (b) 二叉树的三叉链表存储结构

20 尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。
本书后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。 性质：含有n个结点的二叉树必有n＋1个空的链域。

21 6.3 二叉树的遍历 6.3.1 二叉树的遍历方法及递归实现 定义：按某条搜索路径巡访树中的每个结点，使每个结点访问且仅被访问一次。
对二叉树的遍历顺序有六种方式，若约定Lch在前，Rch在后，则有三种方式： (1) Root Lch Rch 前序遍历（先根）；(2) Lch Root Rch 中序遍历（中根）；(3) Lch Rch Root 后序遍历（后根）。

22 递归实现： 1先序遍历： void PreOrder(BiTree bt)  { if (bt! =NULL) { Visit(bt ->data); PreOrder(bt ->LChild); PreOrder(bt ->RChild); } } 若二叉树为空，则空操作，否则依次执行如下3个操作：  (1) 访问根结点；  (2) 先序遍历左子树；  (3) 先序遍历右子树。

23 2中序遍历： void InOrder(BiTree bt)  { if (bt! =NULL) { InOrder(bt ->LChild); Visit(bt ->data); InOrder(bt ->RChild); } } 若二叉树为空，则空操作，否则依次执行如下3个操作：  (1) 中序遍历左子树；  (2) 访问根结点；  (3) 中序遍历右子树。

24 3后序遍历： void PostOrder(BiTree bt)  { if (bt! =NULL) { PostOrder(bt ->LChild); PostOrder(bt ->RChild); Visit(bt ->data); } } 若二叉树为空，则空操作，否则依次执行如下3个操作：  (1) 先序遍历左子树； (2) 先序遍历右子树； (3) 访问根结点。

25 举例1： 先序遍历过程： A A B D C E G H F B C E D H F G 先序遍历结果： B A D F G C E H

26 中序遍历过程： A B D C E G H F A B C E D H F G 中序遍历结果： B F D G A C E H

27 后序遍历过程： A B D C E G H F A B C E D H F G 后序遍历结果： B A F G D H E C

28 最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c）-d/e。
举例2： 最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c）-d/e。 - + * / e c d b a 表达式的前缀、中缀、后缀形式： 前缀： -+a*bc/de  中缀： a+b*c-d/e  后缀： abc*+de/-  前缀表达式称为波兰表达式； 后缀表达式被称作逆波兰表达式。

29 6.3.2二叉树遍历的非递归实现 算法思想: 1 先序遍历的非递归实现
令p指向根结点，访问当前结点p，并将p入栈，然后另p指向当前结点的左孩子结点，若p不空，继续访问p，并将p入栈，直到p为空。弹出栈顶元素赋给p，并令p指向当前结点的右孩子结点。 重复，当p为空或栈空时遍历结束。

30 算法实现1： void PreOrder（BiTree root） { InitStack (&S);  p=root;
while(p! =NULL || !IsEmpty(S)) { if (p! =NULL) ｛ Visit(p->data); Push(&S, p);  p=p->LChild;｝  } else if( !IsEmpty(S)) 　　 { Pop(&S, &p);  p=p->RChild;} }

31 算法实现2： void NRPreOrder(BiTree bt) { BiTree stack[MAXNODE], p; int top;
if (bt==NULL) return; top=0; p=bt; while(!(p==NULL && top==0)) { while(p!=NULL) { visite(p->data); if (top<MAXNODE-1) { stack[top]=p; top++; } else { printf(“栈溢出”)； return； } p=p->lchild； } 栈空时结束 将当前指针p压栈 if (top<=0) return; else { top--; p=stack[top]; p=p->rchild; } } 指向p的左孩子

32 算法实现1： 算法思想: 2 中序遍历的非递归实现 void InOrder（BiTree root）
{ InitStack (&S);  p=root; while(p! =NULL || !IsEmpty(S)) { if (p! =NULL)  { Push(&S, p);  p=p->LChild; } else if( !IsEmpty(S)) 　　 {Pop(&S, &p); Visit(p->data);  p=p->RChild; } } } 算法思想: 中序遍历的非递归算法的实现，只需将先序遍历的非递归算法中的visite(p->data)移到p=stack[top]和p=p->rchild之间即可。

33 算法实现2： void inorder(BiTree root) { top=0; p=bt; 
do{ while(p! =NULL) {if (top>m) return(′overflow′);  top=top+1;  stack[top]=p;  p=p->LChild; } if(top! =0) {p=stack[top];  top=top-1;  Visit(p->data);  p=p->RChild; } } } while(p! =NULL || top! =0) } 遍历左子树 访问根节点 遍历右子树

34 3 后序遍历的非递归实现 算法思想: 在后序遍历过程中，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，令： 当结点指针进、出栈时，其标志flag也同时进、出栈。 { 1 第一次出栈，结点不能访问 2 第二次出栈，结点可以访问 flag＝ 数据类型定义： typedef struct { BiTree link; int flag; } stacktype;

35 算法实现1： Void Postorder(Bitree root) {initstack(s); p=root;
while(p!=NULL || !stackempty(s)) { if (p!=NULL) {push(s, p); flag=1; p=p->lch；} else {pop(s, p); if (flag= =1) { push(s, p); flag=2; p=p->rch; } else {visited(p->data); p=NULL;} }

36 算法实现2： void PostOrder（BiTree root） { BiTNode * p, *q； 
BiTNode **S；  int top=0;  q=NULL;  p=root;  S=(BiTNode**)malloc(sizeof(BiTNode*)*NUM); while(p! =NULL || top!=0) { while(p! =NULL) { top=++; s［top］=p; p=p->LChild; }  if(top>0) { p=s［top］;  if((p->RChild==NULL) ||(p->RChild==q)) {visit(p->data); q=p;  top--;  p=NULL; }  else  p=p->RChild; } } free(s);  } NUM为预定义的常数

37 6.3.3二叉树的层次遍历算法 算法思想: 用队列实现 从根开始，根入队列，若队列不空，取出访问， 若左孩子不空，左孩子入队列；
算法思想: 用队列实现 从根开始，根入队列，若队列不空，取出访问， 若左孩子不空，左孩子入队列； 若右孩子不空，右孩子入队列； 重复。当队列为空时，二叉树的层次遍历结束。

38 算法实现1： void LevelOrder(BiTree bt) { p=bt; if (p==NULL) return;
Inqueue(p); while(!Empty(q)) { Visite(q->data); if(p->lch!=NULL) { Inqueue(p->lch); } if p->rch!=NULL) { Inqueue(p->rch); 根入队列 将队首结点的左孩子入队列 将队首结点的右孩子入队列

39 算法实现2： void LevelOrder(BiTree bt)
{ BiTree Queue[MAXNODE]; int front , rear; if (bt==NULL) return; front=-1; rear=0; queue[rear]=bt; while(front!=rear) { front++; Visite(queue[front]->data); if(queue[front]->lchild!=NULL) { rear++; queue[rear]=queue[front]->lchild; } if (queue[front]->rchild!=NULL) queue[rear]=queue[front]->rchild; } }}

40 6.3.4 遍历序列恢复二叉树 已知一棵二叉树的先序序列与中序序列分别为： A B C D E F G H I
遍历序列恢复二叉树 已知一棵二叉树的先序序列与中序序列分别为： A B C D E F G H I B C A E D G H F I 试恢复该二叉树。 A BC B DEFGHI D FGHI F C E G I H

41 6.3.5 遍历二叉树的应用 例6.1 建立二叉链表方式存储的二叉树
例6.1 建立二叉链表方式存储的二叉树 给定一棵二叉树，我们可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，我们也可以创建相应的二叉链表。 AB.DF..G..C.E.H.. 其中用小圆点表示空子树。

42 算法如下: void CreateBiTree(BiTree *bt) {char ch;  ch=getchar(); 
if(ch==′.′) *bt=NULL;  else{ *bt=(BiTree)malloc(sizeof(BiTNode));  (*bt)->data=ch;  CreateBiTree(&((*bt)->LChild));  CreateBiTree(&((*bt)->RChild));  } }

43 例6.2 输出二叉树中的结点 遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的结点并无次序要求，因此可用三种遍历中的任何一种算法完成。 算法如下: void PreOrder(BiTree root)  { if (root! =NULL) { printf (root ->data);  PreOrder(root ->LChild);  PreOrder(root ->RChild); } }

44 例6.3 输出二叉树中的叶子结点 输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否有满足叶子结点的条件。 算法如下: void PreOrder(BiTree root)  { if (root! =NULL) { if (root ->LChild==NULL && root ->RChild==NULL) printf (root ->data);  PreOrder(root ->LChild);  PreOrder(root ->RChild);  }

45 算法如下: 例6.4 统计叶子结点数目  void Countleaf(BiTree root) { if(root! =NULL)
{ Countleaf(root->LChild);  Countleaf(root->RChild);  if (root ->LChild==NULL && root ->RChild==NULL)  LeafCount++;  } }

46 在bt->lchild为根结点指针的二叉树中查找数据元素x 在bt->rchild为根结点指针的二叉树中查找数据元素x
例6.5在二叉树中查找数据元素 Search(bt，x)功能是在二叉链表bt中查找元素x。查找成功时返回该结点的指针；查找失败时返回空指针。 算法如下: 在bt->lchild为根结点指针的二叉树中查找数据元素x BiTree Search(BiTree bt，datatype x) { BiTree p; if (bt->data==x) return bt; if(bt->lchild!=NULL) return(Search(bt->lchild, x)); if(bt->rchild!=NULL) return(Search(bt->rchild, x)); return NULL; } 查找成功返回 在bt->rchild为根结点指针的二叉树中查找数据元素x 查找失败返回

47 6.4 线索二叉树 1 线索二叉树的定义 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。
6.4 线索二叉树 1 线索二叉树的定义 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。 n个结点的二叉链表中共有n+1个空链域。 指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。

48 2 线索二叉树的结构 方法一： 为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下所示： LChild Ltag Data
Rtag RChild Ltag　　 指示孩子 ＝  Rtag　　1　 指示前驱,后继 指向前驱和后继结点的指针叫做线索； 以这种结构组成的二叉链表作二叉树的存储结构，叫做线索链表； 对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化； 线索化了的二叉树称为线索二叉树。

49 举例：

50 方法二： 不改变结点结构，仅在作为线索的地址前加一个负号，即负的地址表示线索，正的地址表示指针。 本书采用第一种方法介绍线索二叉树的存储

51 线索二叉树的结点结构描述用C语言如下： typedef char datatype; typedef struct BiThrNode { datatype data; struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag; unsigned rtag; } BiThrNodeType, *BiThrTree;

52 1)建立一棵中序线索二叉树 int InOrderThr(BiThrTree *head,BiThrTree T) { if(!(*head =(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))) return 0; (*head)->ltag=0; (*head)->rtag=1; (*head)->rchild=*head; if(!T) (*head)->lchild =*head; else { (*head)->lchild=T; pre= head; InThreading(T); pre->rchild=*head; pre->rtag=1; (*head)->rchild=pre; } return 1;

53 void InTreading(BiThrTree p)
{ /*中序遍历进行中序线索化*/ if (p) { InThreading(p->lchild); if (!p->lchild) { p->ltag=1; p->lchild=pre; } if(!pre->rchild) { pre->rtag=1; pre->rchild=p; pre=p; InThreading(p->rchild);

54 2)找结点的中序前驱结点 算法思想： 根据线索二叉树的基本概念和存储结构可知，对于结点p， 当p->Ltag=1时，p->LChild指向p的前驱。 当p->Ltag=0时，p->LChild指向p的左孩子。 由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。 void InPre(BiTNode *p, BiTNode *pre) { if(p->Ltag==1) pre= p->LChild;  else  { for(q= p->LChild; q->Rtag==0; q=q->RChild);  pre=q; }}

55 3)在中序线索树中找结点后继 算法思想： 对于结点p， 若要找其后继结点，当p->Rtag=1时， p->RChild即为p的后继结点； 当p->Rtag=0时， 说明p有右子树，此时p的中序后继结点即为其右子树的“最左下端”的结点。 算法实现： void InSucc(BiTNode *p, BiTNode *succ)  {if (p->Rtag==1) succ= p-> RChild; /*直接利用线索*/ else { /*在p的右子树中查找“最左下端”结点*/ for(q= p->RChild; q->Ltag==0 ; q=q->LChild );  succ=q; }}

56 6.5 树和森林 6.5.1 树和森林的定义 A B C D E F H I G 树（Tree）是n（n≥0）个有限数据元素的集合。 根
6.5 树和森林 6.5.1 树和森林的定义 树（Tree）是n（n≥0）个有限数据元素的集合。 根 当n==0时，称这棵树为空树。 当n>0时， （1）有一个数据元素称为树的根结点，根结点没有前驱。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 子树T2 子树T1 A B C D E F H I G

57 A C B D E F H I G 树的定义还可形式化的描述为二元组的形式： T＝（D，R） ADT Tree
数据对象：D={t| t ∈ D} 数据关系：R： 若D中仅含有一个数据元素，则R为空集 否则R={H}，H是如下的二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。 (2) 除root以外，D中每个结点在关系H下都有且仅有一个前驱。 A C B D E F H I G 树的特点： （1）根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 （2）树中所有结点可以有零个或多个后继结点。

58 A B C C D E F G H I 概念： 在二叉树中介绍的有关概念在树中仍然适用。
有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，则称为无序树。 森林（forest）：零棵或有限棵不相交的树的集合称为森林。 任何一棵树，删去根结点就变成了森林。 A B C C D E F G H I

59 A C B D E F H I G T 根结点 双亲结点 树的基本操作 X结点 X结点 （1）Initiate(t)：初始化一棵空树t。
（2）Root(x)：求结点x所在树的根结点。 （3）Parent(t，x)：求树t中结点x的双亲结点。 （4）Child(t，x，i)：求树t中结点x的第i个孩子结点。 （5）RightSibling(t，x)：求树t中结点x的第一个右边兄弟结点。 （6）Insert(t，x，i，s)：把以s为根结点的树插入到树t中作为结点x的第i棵子树。 （7）Delete(t，x，i)：在树t中删除结点x的第i棵子树。 （8）Tranverse(t)：是树的遍历操作，即按某种方式访问树t中的每个结点，且使每个结点只被访问一次。 B的右兄弟 T ……. s

60 6.5.2 树的存储结构 A C B D E F H I G 1. 双亲表示法
1. 双亲表示法 用一组连续的空间来存储树中的结点，同时附设一个指示器来指示其双亲结点在表中的位置。 Data Parent 序号 data parent 1 2 3 4 5 6 7 8 A C B D E F H I G A B C D E F G H I -1 1 1 1 2 4 4

61 A C B D E F H I G #define MAXNODE <结点的最大个数> typedef struct {
datatype data; int parent; }NodeType; NodeType t[MAXNODE]; 操作分析： Parent(t, x) 操作 Root(x) 操作 Child(t, x, i)操作 序号 data parent 1 2 3 4 5 6 7 8 A B C D E F G H I -1 A C B D E F H I G 1 1 1 2 4 4

62 A C B D E F H I G 2.孩子表示法 1）多重链表法 #define MAXSON <树的度数>
typedef struct TreeNode { datatype data; struct TreeNode *son[MAXSON]; } NodeType; 操作分析： Parent(t, x) 操作 Root(x) 操作 Child(t, x, i)操作 A C B D E F H I G

63 A C B D E F H I G 2）孩子链表表示法 把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。
n个结点共有n个孩子链表 n个结点的数据和n个孩子链表的头指针又组成一个顺序表。 #define MAXNODE <树中结点的最大个数> typedef struct ChildNode{ int childcode; struct ChildNode *nextchild; } ChildNode; typedef struct { datatype data; ChildNode *firstchild; }NodeType; NodeType t[MAXNODE]; A C B D E F H I G 操作分析： Parent(t, x) 操作 Root(x) 操作 Child(t, x, i)操作

64 3. 双亲孩子表示法 是将双亲表示法和孩子表示法相结合 A C B D E F H I G 双亲孩子表示法

65 A C B D E F H I G 4. 孩子兄弟表示法(树的二叉链表表示法) typedef struct TreeNode {
datatype data; struct TreeNode *FirstChild; struct TreeNode *Nextsibling; }NodeType; 方法：每个结点除其信息域外，两个指针分别指向该结点的第一个孩子和下一个兄弟。 A C B D E F H I G 孩子兄弟表示法

66 ② 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。
5. 树、森林与二叉树的转换 1）树转换为二叉树 方法： ① 树中所有相邻兄弟之间加一条连线。 ② 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 ③ 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。 A B C D C E F G D F G

67 2）森林转换为二叉树 方法： ① 将森林中的每棵树转换成相应的二叉树。 ② 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

68 森林转换为二叉树的过程演示： A B D E F C G H I J K A C G C D B H D E G I J E H F K I

69 ① 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来；
3) 二叉树转换为树和森林 方法： ① 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来； ② 删去原二叉树中所有的双亲结点与右孩子结点的连线； ③ 整理由①、②两步所得到的树或森林，使之结构层次分明。 A E B A E G F G C B C D F I K I D K

70 6.5.3 树和森林的遍历 1.树的遍历 1）先根遍历 若树为空，遍历结束。否则： ① 访问根结点；
② 按照从左到右的顺序先根遍历根结点的每一棵子树。 A 结果为： A B E F C D G B C D E F G

71 ① 按照从左到右的顺序后根遍历根结点的每一棵子树。 ② 访问根结点；
2）后根遍历 若树为空，遍历结束。否则： ① 按照从左到右的顺序后根遍历根结点的每一棵子树。 ② 访问根结点； A 结果为： E F B C G D A B C D E F G

72 2.森林的遍历 1）前序遍历 若森林为空，遍历结束。否则： ① 访问森林中第一棵树的根结点； ② 前序遍历第一棵树的根结点的子树森林；
③ 前序遍历去掉第一棵树后的子森林。 G A C H I B D E F J K 前序遍历： A B C D E F G H J I K

73 2）中序遍历 若森林为空，遍历结束。否则： ① 中序遍历第一棵树的根结点的子树森林； ② 访问森林中第一棵树的根结点；
③ 中序遍历去掉第一棵树后的子森林。 G A C H I B D E F J K 中序遍历： B A D E F C J H K I G

74 ① 后序遍历森林中第一棵树的根结点的子树森林。 ② 后序遍历除去第一棵树之后剩余的树构成的森林。 ③ 访问第一棵树的根结点。
3） 后序遍历 若森林为空，遍历结束。否则： ① 后序遍历森林中第一棵树的根结点的子树森林。 ② 后序遍历除去第一棵树之后剩余的树构成的森林。 ③ 访问第一棵树的根结点。 G A C H I B D E F J K 后序遍历： B F E D J K I H G C A

75 6.5 哈夫曼树及其应用 例如，要编制一个将百分制转换为五级分制的程序。 if (a<60) b=〝bad〝;
6.5 哈夫曼树及其应用 例如，要编制一个将百分制转换为五级分制的程序。 if (a<60) b=〝bad〝; else if (a<70) b=〝pass〝； else if (a<80) b=〝general〝； else if (a<90) b=〝good〝； else b=〝excellent〝; 在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示： 分数 － － － － －100 比例数

76

77 6.5 哈夫曼树及其应用 A C B D E F H I G 6.6.1 哈夫曼树 1. 路径和路径长度
6.5 哈夫曼树及其应用 A C B D E F H I G 哈夫曼树 1. 路径和路径长度 路径：从一个结点到另一个结点之间的分支序列. 路径长度：从一个结点到另一个结点所经过的分支数目。 5 2 4 6 1 2. 结点的权和带权路径长度 实际应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。 把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。 H： 3*6

78 3. 二叉树的带权路径长度 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为： 其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。 WPL＝2×2＋4×2＋5×2＋3×2＝28。

79 4. 哈夫曼树的概念 哈夫曼（Haffman）树，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造具有最小带权路径长度的二叉树。 如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？ 根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。 特点：值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。

80 例如：以(1，3，5，7) 为叶子构造二叉树： 这五棵树的带权路径长度分别为： a）WPL＝1×2＋3×2＋5×2＋7×2＝32 b）WPL＝1×3＋3×3＋5×2＋7×1＝29 c）WPL＝1×2＋3×3＋5×3＋7×1＝33 d）WPL＝7×3＋5×3＋3×2＋1×1＝43 e）WPL＝7×1＋5×2＋3×3＋1×3＝29

81 5. 哈夫曼树的构造： （1）用给定的n个权值{w1, w2, …, wn} 构成n棵二叉树的集合 F={T1, T2, …, Tn}， 其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树为空。 （2）在F中选择两棵根结点权值最小的二叉树作为左、右子树构造一个新的二叉树，新二叉树的根结点权值为其左右子树的根结点权值之和。 （3）从F中删除被选中的两棵二叉树， 同时把新构成的二叉树加入到森林F中。 （4）重复(2)、(3)操作， 直到森林中只含有一棵二叉树为止， 这棵二叉树就是哈夫曼树。

82 哈夫曼树建立过程 

83 设置结构数组HuffNode保存哈夫曼树中各结点的信息，数组大小设置为2n－1(具有n个叶结点的哈树共有2n－1个结点)。
哈夫曼树的存储 设置结构数组HuffNode保存哈夫曼树中各结点的信息，数组大小设置为2n－1(具有n个叶结点的哈树共有2n－1个结点)。 结构： weight lchild parent rchild 其中，weight域保存结点的权值 lchild和rchild分别保存结点左、右孩子在数组中序号。 weight lchild rchild parent 2 -1 5 3 6 7 8 1 10 15 4 25 1 2 3 4 5 6 7 8

84 HNodeType HuffNode[m ];
哈夫曼树的构造算法实现 weight lchild rchild parent typedef struct { int weight; int parent; int lchild; int rchild; }HNodeType 3 -1 -1 -1 8 -1 -1 -1 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 HNodeType HuffNode[m ]; -1 -1 -1 void HaffmanTree(HNodeType HuffNode[ ]) { int i, j, x1, x2, n; scanf(〞%d〞, &n); for(i=0; i<2*n-1; i++ ) /*数组HuffNode[ ]初始化*/ { HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } -1 -1 -1 -1 -1 -1 for(i=0; i<n; i++ ) scanf(“%d”, &HuffNode[i].weight);

85 { select(HuffNode, i-1, x1, x2); 
for(i=n; i<m; i++) { select(HuffNode, i-1, x1, x2);  /*在HuffNode[0]~HuffNode[i-1]的范围内选择两个parent为-1且weight 最小的结点， 其序号分别赋值给x1、 x2返回*/ HuffNode [x1].parent=i; HuffNode [x2].parent=i;  HuffNode [i]. lchild=x1; HuffNode [i]. rchild=x2;  HuffNode [i].weight=HuffNode [x1].weight+HuffNode [x2].weight; } parent rchild lchild weight -1 3 8 7 5 2 1 4 6 25 x2 5 x2 7 10 15 10 x1 7 x2 6 15 5 5 5 5 5 7 8 x1 5 x1 5 4 6 3 8 7 7 8 2 5 2 3 3 x1 2 3 10 3 5 8 x2 15 2 1 8 25 6 7

86 哈夫曼树编码 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。 例如，设传送的电文为ABACCDA 字符 编码 A 000 B 010 C 100 D 111 字符 编码 A 00 B 01 C 10 D 11 字符 编码 A B 110 C 10 D 111 字符 编码 A 01 B 010 C 001 D 10 (a)编码，代码为 ，长度为21。 (b)编码，代码为 ，长度为14 (c)编码，代码为 ，长度仅为13 (d)编码， 这个存在解码二义性

87 哈夫曼树可用于构造使电文的编码总长最短的编码方案，且不会产生上述二义性问题。
字符 s t a e c 字符出现的次数 按规定：0左1右， 则有 c s e a t

88 设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为权值，构造一棵哈夫曼树.
规定左分支代表0，右分支代表1，从根到每个叶结点所经过的路径分支组成的0和1的序列为该结点对应字符的编码，称之为哈夫曼编码。 下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分： （1）构造哈夫曼树； （2）在哈夫曼树上求叶结点的编码。

89 void HaffmanCode ( ) /*生成哈夫曼编码*/ { HNodeType HuffNode[MAXNODE];
哈夫曼编码算法: typedef struct { int bit[MAXBIT]; int start; } HCodeType; void HaffmanCode ( ) /*生成哈夫曼编码*/ { HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF], cd ; int i, j, c, p; HuffmanTree (HuffNode ); for (i=0; i<n; i++) { cd.start=n-1; c=i; p=HuffNode[c].parent; weight lchild rchild parent 3 -1 5 8 7 2 6 10 4 15 1 25 1 2 3 4 5 6 7 8

90 p=HuffNode[c].parent; while(p!=0) { if (HuffNode[p].lchild==c)
for (i=0; i<n; i++) { cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=0) { if (HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent; } for (j=cd.start+1; j<n; j++) HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start; } { for (j=HuffCode[i].start+1; j<n; j++) printf( “%ld”, HuffCode[i].bit[j] ); printf(“\n”); }} weight lchild rchild parent 3 -1 5 8 7 2 6 10 4 15 1 25 1 2 3 4 5 6 7 8