第5章 树和二叉树 北京师范大学 教育技术学院 杨开城.

Presentation on theme: "第5章 树和二叉树 北京师范大学 教育技术学院 杨开城."— Presentation transcript:

1 第5章 树和二叉树 北京师范大学 教育技术学院 杨开城

2 一、树的基本概念 基本术语 树的定义 任何一个非空树是这样一个包含n个结点的有限集合： ⑴唯一存在一个结点R，它没有前驱，被称为根；
⑵当n>1时，除了根之外，其他结点可分为m(m>0)个不相交的子集T1,T2,…,Tm，其中每一个子集都是一棵树，它们的根的前驱是R，这些子集被称为R的子树。 基本术语 根 叶子 分枝结点 内部结点 双亲 孩子 祖先 子孙 兄弟 堂兄弟 度 层次 深度(高度) 有序树 无序树 森林

3 二、二叉树——定义和基本性质(1) 定义：二叉树（Binary Tree）是一种特殊的树形结构。它的特点是每个结点最多有两个子树，而且子树分左右，不能任意颠倒，我们通常称之为左子树和右子树。

4 二、二叉树——定义和基本性质(2) 基本性质： ⑴二叉树的第i层最多有2i-1（i≥1）个结点。 ⑵深度是k的二叉树，最多有2k－1个结点。
⑶设任意一棵二叉树中，叶子结点数为n0，度是1的结点(即单枝结点)数为n1，度为2的结点(即双枝结点)数为n2，则有：n0=n2+1。 ⑷具有n个结点的完全二叉树的深度是 ⑸对于一个n个结点的完全二叉树，自上而下、自左向右给结点编号，根结点编号为1。如果已知某结点编号是i，那么 ①如果i=1，那么结点是根，如果i＞1，那么它的双亲是i/2,即 ②如果2i＞n，那么该结点没有左孩子，否则它的左孩子是2i； ③如果2i+1＞n，那么该结点没有右孩子，否则它的右孩子是2i+1。

5 二、二叉树——存储结构(1) 1．二叉树的顺序存储 #define N 50 /*最大结点数*/
typedef elemtype SQBTREE[N+1]; /*数组0号单元空闲，不存放结点*/

6 二、二叉树——存储结构(2) 2．二叉树的链式存储 二叉链表类型定义： typedef struct btreenode {
char data;/*数据域可以是任意类型*/ struct btreenode *lchild,*rchild; /*指向左右孩子的指针*/ } BTREENODE, *BTREENODEPTR,*BTREE; 三叉链表类型定义： char data; struct btreenode *lchild,*rchild; struct btreenode *parent; /*指向双亲的指针*/ } PBTREENODE, *PBTREENODEPTR,*PBTREE;

7 二、二叉树——建立与销毁(1) 1．二叉树的建立——以广义表字符串作为输入 【算法思想】 例子：
A（B（D（ , H（J , ））, E（ , I））, C（F , G）） 【算法思想】 从左向右扫描广义表字符串，我们会遇到这样几种字符： ①字母，字母代表结点，遇到字母时，当然要建立结点。 需要设定一个栈，将所有左右孩子没有生成完毕的结点保存起来。当前结点的双亲必然是栈顶结点。 ②左括号，左括号前面一定是一个字母。因此遇到左括号时，意味着要生成前面字母结点的左右孩子，这时要将前面字母的结点入栈。 ③逗号，逗号的前面是某个结点的左孩子，后面是某个结点的右孩子。 ④右括号，右括号意味着某个结点的左右孩子都生成完毕，这个结点一定位于栈顶。这时需要出栈操作。

8 二、二叉树——建立与销毁(2) typedef BTREENODEPTR elemtype;
BTREE CreateBtree1(char *str) {/*字符串str是广义表字符串，以它作为输入数据，返回建立的二叉树*/ BTREE root=NULL;/*二叉树根结点指针*/ BTREENODEPTR p; int tag,i,len; int mark;/*记录扫描到的字符类型，1代表字母,2代表(,3代表逗号,4代表)*/ SQSTACK s; /*栈中存放左右孩子为生成完毕的结点*/ if(str[0]==0)return root; /*广义表是空，返回NULL*/ root=(BTREENODEPTR)malloc(sizeof(BTREENODE));/*生成根结点*/ if(root==NULL)return root; /*假设str[0]是字母*/ root->data=str[0]; root->lchild=root->rchild=NULL; len=strlen(str); /*初始化栈，容量是字符串的长度*/ InitSqstack(&s,len);

9 二、二叉树——建立与销毁(3) p=root; /*p指向当前生成的结点*/ mark=1; /*标明扫描到字母*/
for(i=1;str[i]!=0;i++) /*开始从左向右扫描字符串*/ switch(str[i]) { case '(': if(mark==2) return NULL; /*连续出现（,非法*/ mark=2;/*扫描到左括号*/ Push(&s,p);/*将当前结点入栈*/ tag=0;/*标明准备生成左孩子*/ break; case ')': mark=4;/*扫描到右括号*/ /*栈顶结点左右孩子生成完毕，出栈*/ if(!Pop(&s,&p))/*括号不配对*/ return NULL;

10 二、二叉树——建立与销毁(4) case ',': if(mark==3) return NULL; /*连续出现逗号，广义表非法*/
tag=1; /*准备生成栈顶结点的右孩子*/ break; default: if(mark==1) return NULL; /*连续出现两个字母，广义表非法*/ mark=1; /*扫描到字母*/ /*如果栈空，找不到当前结点的双亲，广义表非法*/ if(IsSqstackEmpty(s)) return NULL; /*生成当前结点，并与栈顶结点建立孩子关系*/ p=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p==NULL) return NULL; p->data=str[i]; p->lchild=p->rchild=NULL; if(tag==0) s.elem[s.top]->lchild=p; /*当前结点是栈顶结点的左孩子*/ else s.elem[s.top]->rchild=p; /*当前结点是栈顶结点的左孩子*/ break; } return root; }

11 二、二叉树——建立与销毁(4) 2．二叉树的销毁 void DestroyBtree(BTREE root) {/*销毁二叉树的递归算法*/
A B C D E 2．二叉树的销毁 void DestroyBtree(BTREE root) {/*销毁二叉树的递归算法*/ if(root==NULL)return; /*销毁左子树*/ DestroyBtree(root->lchild); /*销毁右子树*/ DestroyBtree(root->rchild); root->lchild=NULL; root->rchild=NULL; free(root);/*释放结点内存*/ }

12 三、二叉树的遍历——算法(1) 遍历的规则： 遍历的递归算法 先序遍历：A B D H J E I C F G
中序遍历：D J H B E I A F C G 后序遍历：J H D I E B F G C A 层序遍历：A B C D E F G H I J 遍历的递归算法 ⑴先序遍历 void PreOrder(BTREE root, char *str) { /*先序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/ char tmpstr[10]; if(root==NULL)return; sprintf(tmpstr,"%c ",root->data);/*将数据域数据转化为字符串tmpstr*/ strcat(str,tmpstr);/*将tmpstr续接到str后*/ PreOrder(root->lchild,str);/*遍历左子树*/ PreOrder(root->rchild,str);/*遍历右子树*/ }

13 三、二叉树的遍历——算法(2) 遍历的递归算法 ⑵中序遍历 void InOrder(BTREE root,char *str)
{/*中序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/ char tmpstr[10]; if(root==NULL)return; InOrder(root->lchild,str); /*遍历左子树*/ /*开始访问根结点*/ sprintf(tmpstr,"%c ",root->data); /*将数据域数据转化为字符串tmpstr*/ strcat(str,tmpstr); /*将tmpstr续接到str后*/ InOrder(root->rchild,str); /*遍历右子树*/ }

14 三、二叉树的遍历——算法(3) 遍历的递归算法 调用方法 ⑶后序遍历
void PostOrder(BTREE root,char *str) {/*后序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/ char tmpstr[10]; if(root==NULL)return; PostOrder(root->lchild,str); /*遍历左子树*/ PostOrder(root->rchild,str); /*遍历右子树*/ /*开始访问根结点*/ sprintf(tmpstr,"%c ",root->data); strcat(str,tmpstr); } 调用方法 char str[80]; str[0]=0; PreOrder(root,str); printf("%s",str);

15 三、二叉树的遍历——算法(4) 遍历的非递归算法 ⑴先序遍历 void PreOrder1(BTREE root,char *str)
{char tmpstr[20]; SQSTACK s; BTREENODEPTR p; InitSqstack(&s,MAXCOUNT);/*初始化栈,MAXCOUNT根据需要定义*/ p=root;/*p指向根结点*/ Push(&s,p);/*将当前结点入栈*/ while(!IsSqstackEmpty(s)) /*栈中有未遍历的子树*/ { Pop(&s,&p);/*弹出栈顶问题（子树p）*/ sprintf(tmpstr,"%c ",p->data); strcat(str,tmpstr); /*访问这颗子树的根结点*/ /*将p递归分解为它的左右子树，先将右子树入栈，再将左子树入栈*/ if(p->rchild!=NULL)Push(&s,p->rchild); if(p->lchild!=NULL)Push(&s,p->lchild); } DestroySqstack(&s); }

16 三、二叉树的遍历——算法(5) 遍历的非递归算法 ⑵中序遍历 void InOrder1(BTREE root, char *str)
{ char tmpstr[20]; SQSTACK s; BTREENODEPTR p; InitSqstack(&s,MAXCOUNT); p=root; Push(&s,p);/*将初始问题（根结点）入栈*/ while(1) /*无限循环，栈空退出*/ { p=s.elem[s.top]; /*取栈顶问题p*/ while(p->lchild!=NULL) /*只要当前问题p的左孩子不空，就继续向左递归分解*/ { p=p->lchild; /*p被递归分解为它的左孩子*/ Push(&s,p);/*问题p入栈，为了找到p的右孩子，生成第二个问题*/ } while(!IsSqstackEmpty(s)) /*栈中可能会连续存放递归终点的问题*/ { Pop(&s,&p);/*栈顶问题p出栈*/ sprintf(tmpstr,"%c ",p->data); strcat(str,tmpstr); /*无论p是否是递归终点，都要访问p结点自身*/

17 三、二叉树的遍历——算法(6) if(p->rchild!=NULL)
{/*如果p的右孩子不空，将p的右孩子入栈，即将第二个问题入栈*/ Push(&s,p->rchild); break;/*转去继续递归分解*/ } if(IsSqstackEmpty(s)) {/*如果发现栈空，遍历结束*/ DestroySqstack(&s); return;

18 三、二叉树的遍历——算法(7) 遍历的非递归算法 ⑶后序遍历 void PostOrder1(BTREE root, char *str)
{char tmpstr[20]; SQSTACK s; BTREENODEPTR p; InitSqstack(&s,MAXCOUNT); p=root; Push(&s,p);/*将问题p入栈*/ while(1) { p=s.elem[s.top];/*取栈顶问题p*/ while(p->lchild!=NULL) /*当前问题p左孩子不空，需要递归分解*/ { p=p->lchild; /*p递归分解为它的左孩子*/ Push(&s,p); /*将问题p入栈，为了找到它的右孩子，即第二个问题*/ }

19 三、二叉树的遍历——算法(8) while(1) /*出栈处理循环*/
{ if(s.elem[s.top]->rchild!=NULL) {/*如果栈顶结点右孩子不空，栈顶问题需要继续递归分解*/ p=s.elem[s.top]->rchild; /*p指向栈顶结点的右孩子*/ Push(&s,p);/*问题p入栈*/ break;/*转去递归分解*/ } /*栈顶结点右孩子为空，才可以进行出栈处理，可能会将递归终点连续出栈*/ while(!IsSqstackEmpty(s)) { if(s.elem[s.top]->rchild==NULL||s.elem[s.top]->rchild==p) {/*栈顶问题是递归终点的条件：右孩子是空(一般首先遇到) 或者它的右孩子是原栈顶结点p（这个条件只有在出栈处理时才是递归终点的条件）*/ Pop(&s,&p); /*栈顶问题p出栈*/ sprintf(tmpstr,"%c ",p->data);/*访问结点p*/ strcat(str,tmpstr); } else break;/*否则跳出弹出递归终点的循环*/ }

20 三、二叉树的遍历——算法(9) if(IsSqstackEmpty(s)) {/*栈空，则遍历结束*/
DestroySqstack(&s); return; } }//出栈处理while(1)

21 三、二叉树的遍历——算法(10) 层序遍历 void LayerOrder(BTREE root, char *str)
{/*层序遍历二叉树root,遍历结果放在str中，str一开始为空*/ char tmpstr[20]; SQQUEUE qu; BTREENODEPTR p; InitSqqueue(&qu,MAXCOUNT); EnSqqueue(&qu,root); /*将根结点入队*/ while(!IsSqqueueEmpty(qu)) /*只要队列不空就循环，队列空则遍历完毕*/ { DeSqqueue(&qu,&p);/*出队一个结点p*/ sprintf(tmpstr,"%c ",p->data); strcat(str,tmpstr); /*访问结点p*/ if(p->lchild!=NULL)/*将左孩子入队*/ EnSqqueue(&qu,p->lchild); if(p->rchild!=NULL) /*将左孩子入队*/ EnSqqueue(&qu,p->rchild); }

22 三、二叉树的遍历——算法的应用(1) 1．求二叉树的深度 int GetHeight(BTREE root)
int lh,rh; if(root==NULL)return 0; /*空树，深度是0*/ lh=GetHeight(root->lchild); /*递归调用获得左子树的深度*/ rh=GetHeight(root->rchild);/*递归调用获得右子树的深度*/ /*取左右子树深度值大者，作为子树的深度，这个树的深度是子树深度加1*/ if(lh>=rh)return lh+1; else return rh+1; }

23 三、二叉树的遍历——算法的应用(2) 2．计算叶子结点的总数 int CountLeaf(BTREE root)
int lnum,rnum; if(root==NULL)return 0; /*空树，叶子结点个数是0*/ lnum=CountLeaf(root->lchild); /*递归调用求左子树叶子结点个数*/ rnum=CountLeaf(root->rchild);/*递归调用求右子树叶子结点个数*/ /*如果左右子树叶子的和是0，说明当前结点是叶子，返回1；否则返回左右子树叶子结点的和*/ if((lnum+rnum)==0)return 1; else return lnum+rnum; }

24 三、二叉树的遍历——算法的应用(3) 3．利用层序遍历序列建立二叉树 输入数据的例子：“ABC@DE@”和“ABCDE@”
BTREE CreateBtree2(char *str) { /*字符串str中是二叉树的层序输入序列字符串，返回所建立的二叉树*/ BTREE root=NULL; BTREENODEPTR p1,p2; SQQUEUE q; int k; if(str[0]==0)return root; /*生成根结点，数据域是str[0]*/ root=(BTREE)malloc(sizeof(BTREENODE)); if(root==NULL)return NULL; root->data=str[0]; root->lchild=root->rchild=NULL; /*左右孩子默认为空*/ InitSqqueue(&q,100);/*初始化队列*/ EnSqqueue(&q,root); /*将根结点入队*/

25 三、二叉树的遍历——算法的应用(4) k=1; /*k是字符串str的下标，从1开始向后扫描*/
while(!IsSqqueueEmpty(q)) {/*队列不空，意味着还有结点的左右孩子没有建立*/ DeSqqueue(&q,&p1); /*出队一个结点p1*/ if(str[k]!=0) /*如果字符串没有到末尾，可以为p1生成左孩子结点*/ { /*左孩子结点不是空，生成结点*/ { p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL) /*生成结点失败，销毁已经建立的二叉树，返回NULL*/ { DestroyBtree(root); return NULL; } p2->data=str[k]; p2->lchild=p2->rchild=NULL; p1->lchild=p2;/*p2成为p1的左孩子*/ EnSqqueue(&q,p2);/*将p2入队*/ } k++;/*下标先后移动*/ }

26 三、二叉树的遍历——算法的应用(5) if(str[k]!=0) /*未到字符串末尾，可以为结点p1生成右孩子*/
{ p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL) { DestroyBtree(root); return NULL; } p2->data=str[k]; p2->lchild=p2->rchild=NULL; p1->rchild=p2; EnSqqueue(&q,p2); } k++; }//while DestroySqqueue(&q); return root;

27 四、线索化二叉树(1) 【问题】已知一棵二叉树，如何在中序遍历序列中确定结点B和结点I的前驱后继结点呢？ 【结论】
如果结点具有左右子树，我们很容易确定它的前驱和后继。 如果结点的左右孩子是NULL，确定起来就非常繁琐。 由于任何一个二叉树的结点都有两个指针域，当指针域是NULL时，它是空闲的。如果这种情况下，将指针域分别指向前驱和后继，对于查找结点的前驱后继是非常方便的。 用于这个目的的lchild和rchild指针被称为线索。将lchild和rchild分别指向前驱和后继的操作被称为线索化。

28 四、线索化二叉树(2) 线索化的二叉树的数据类型 算法思想 typedef struct thrbtreenode { char data;
int ltag,rtag;/*ltag是0时，lchild指向左孩子，ltag是1时，lchild指向前驱；rtag是0时，rchild指向右孩子，rtag是1时，rchild指向后继*/ struct thrbtreenode *lchild,*rchild; } THRBTREENODE, *THRBTREENODEPTR,*THRBTREE; 算法思想 在中序遍历过程中建立线索； 设置一个全局变量保存在遍历过程中当前结点的前驱； 为了方便使用，我们为线索化了的二叉树设定另一个头结点head，head的左孩子指向真正二叉树的根结点，右孩子最终指向中序序列的最后一个结点（为了方便逆序遍历二叉树时很容易找到最后一个结点）。

29 四、线索化二叉树(3) 线索化算法 THRBTREENODEPTR pre;/*全局变量pre*/
THRBTREE InOrderThread(THRBTREE root) {/*为root建立线索，返回线索化了的二叉树的头结点指针*/ THRBTREE head; /*线索化二叉树的头结点*/ head=(THRBTREENODEPTR)malloc(sizeof(THRBTREENODE)); if(head==NULL)return NULL; pre=NULL;/*pre初始值是NULL*/ head->lchild=root; /*头结点左孩子指向二叉树的根*/ head->rchild=NULL; /*头结点右孩子初始化为NULL*/ InOrderThr(root);/*为二叉树建立线索*/ head->rchild=pre;/*这时，pre指向中序遍历最后一个结点*/ return head; /*返回头结点指针*/ }

30 四、线索化二叉树(4) void InOrderThr(THRBTREE p) /*为二叉树建立线索*/
{ if(p==NULL)return; /*递归终点*/ InOrderThr(p->lchild); /*为左子树建立线索*/ /*这时pre是p的前驱*/ if(pre!=NULL&&pre->rchild==NULL) { /*如果pre不空，并且pre的右孩子是NULL，将pre的右孩子指向p*/ pre->rtag=1; /*表明pre->rchild是线索指针*/ pre->rchild=p; } if(p->lchild==NULL) { /*如果p的左孩子是NULL，将p的左孩子指向pre*/ p->ltag=1; /*表明p->lchild是线索指针*/ p->lchild=pre; pre=p; /*在遍历其他结点之前，pre指向p*/ InOrderThr(p->rchild); /*为右子树建立线索*/

31 四、线索化二叉树(5) 利用中序线索遍历二叉树
void TraverseInOrderThr(THRBTREE root,char *str) {/*遍历线索化了的二叉树，将遍历结果存放在str中*/ char tmpstr[20]; THRBTREENODEPTR p; p=root; /*p指向根结点*/ while(1) /*遍历循环*/ { while(p->ltag==0)/*寻找p的最左端结点*/ p=p->lchild; sprintf(tmpstr,"%c ",p->data); strcat(str,tmpstr); /*访问结点p*/ while(p->rtag==1&&p->rchild!=NULL) /*沿着线索指针遍历后继结点*/ { p=p->rchild; sprintf(tmpstr,"%c ",p->data); strcat(str,tmpstr); } if(p->rchild==NULL)return;/*遇到最后一个结点，返回*/ else p=p->rchild;/*p有右孩子，跳到右分枝*/

32 四、线索化二叉树(6) 先序线索化算法 void PreOrderThr(THRBTREE p) /*先序遍历的线索化操作*/
{ if(p==NULL)return; /*建立pre与p之间的前驱后继关系*/ if(pre!=NULL&&pre->rchild==NULL) { pre->rtag=1; pre->rchild=p; } if(p->lchild==NULL) { p->ltag=1; p->lchild=pre; pre=p;/*pre指向p*/ if(p->ltag==0) PreOrderThr(p->lchild);/*建立左子树的线索*/ if(p->rtag==0) PreOrderThr(p->rchild);/*建立右子树的线索*/

33 四、线索化二叉树(7) 后序线索化算法 void PostOrderThr(THRBTREE p) /*后序遍历的线索化*/
{ if(p==NULL)return; PostOrderThr(p->lchild);/*建立左子树的线索*/ PostOrderThr(p->rchild);/*建立右子树的线索*/ /*建立pre和p之间的前驱后继关系*/ if(pre!=NULL&&pre->rchild==NULL) { pre->rtag=1; pre->rchild=p; } if(p->lchild==NULL) { p->ltag=1; p->lchild=pre; pre=p;/*将p指向pre*/

34 五、哈夫曼树(1) 哈夫曼树，又称最优树，是一种带权路径长度最短的树。 路径长度：树中某结点到其子树另一结点之间的分枝个数。
树的路径长度：从根到每一个结点的路径长度之和。 树的带权路径长度：所有叶子结点带权路径长度之和。 假设一个二叉树有n个叶子结点，每个叶子结点的路径长度是lk ，权值是Wk ，那么整个二叉树的带权路径长度记为： 哈夫曼树可以分为二叉哈夫曼树和多叉哈夫曼树。

35 五、哈夫曼树(2) 【问题】在某两地之间的一次网络通讯业务中，发送的字符串是“ACCEEBBBEECCDDDDCDDEEEE”，并且已知这类通讯业务只发送ABCDE这5种字符。问如何对ABCDE这5种字符进行编码，才使得通讯时发送的数据总量最小（成本最低）？ 【解决方案】 方案1：直接发送字符的ASCII码 发送的数据量： ( )×8=184(比特)。 方案2：A：000 B：001 C：010 D：011 E：100 发送的数据量：( )×3=69(比特) 方案3：A：0 B：1 C：00 D：01 E：001 发送的数据量：1+3+5*2+6*2+8*3=50(比特) 方案4 ： A：000 B：001 C：01 D：10 E：11 发送的数据量：(1+3)*3+(5+6+8)*2=50(比特)

36 五、哈夫曼树(3) 哈夫曼树的构造 将n个带权结点自成n个子树，每个子树只有一个根结点，这样我们就得到一个n棵二叉树的集合F={T1,T2,…,Tn}。 执行循环：选取F中权值最小的两棵树Ti和Tj，生成一棵以这两棵树为左右子树的新二叉树Tk，Tk根结点的权值是Ti和Tj根结点权值之和。将Ti,和Tj从F集合中删除，将Tk加入到F集合中。直到F集合中只有一棵二叉树为止。

37 五、哈夫曼树(4) 初始化存放哈夫曼树的数组 typedef struct { char ch; /*结点字符*/
int w; /*结点权值*/ int lchild,rchild;/*左右孩子，是数组下标*/ }HUFFMANNODE,*HUFFMANTREE; 初始化存放哈夫曼树的数组 HUFFMANTREE InitHuffman(void) {/*接受字符串输入，将字符出现的个数作为权值，返回只包含叶子结点的HUFFMANNODE数组，这个数组的首单元存放叶子结点的个数*/ char str[80]; int num; int i,j,k; HUFFMANTREE ht; HUFFMANNODE tmpht; printf("please input the string for huffman coding:\n"); gets(str);/*输入字符串*/ if(str[0]==0) return NULL; num=1;/*出现的字符个数，即叶子结点个数*/

38 五、哈夫曼树(5) for(i=1;str[i]!=0;i++) /*扫描字符串，计算有多少种字符*/
{ for(j=i-1;j>=0;j--)/*检查str[0..i-1]中有无str[i]*/ if(str[i]==str[j]) break; if(j==-1) num++; /*str[i]第一次出现，num增1*/ } /*n个叶子结点的哈夫曼树，其他结点个数是n-1。还需要1个单元存放叶子结点个数*/ num=2*num; ht=(HUFFMANTREE)malloc(num*sizeof(HUFFMANNODE)); if(ht==NULL)return NULL; for(i=0;i<num;i++)/*初始化所有的数组单元，每个单元自成一棵树*/ { ht[i].w=0;/*权值归零*/ ht[i].lchild=ht[i].rchild=-1;/*左右孩子为空，用-1表示NULL*/

39 五、哈夫曼树(6) num=0;/*叶子结点总量*/
for(i=0;str[i]!=0;i++) /*重新扫描字符串，将计数信息作为结点的权值*/ { for(j=0;j<num;j++)/*寻找与字符str[i]相同的叶子结点*/ if(ht[j+1].ch==str[i]) break; if(j==num) /*未找到，即发现新字符*/ { ht[num+1].ch=str[i]; /*新叶子结点，记录字符信息*/ ht[num+1].w++;/*权值增1，最初是0*/ num++; /*叶子结点个数增1*/ } else ht[j+1].w++; /*找到了，相应的叶子结点权值增1*/

40 五、哈夫曼树(7) for(i=0;i<num-1;i++) /*对叶子结点按照权值升序排序*/ { k=i;
for(j=i+1;j<num;j++) if(ht[j+1].w<ht[k+1].w) k=j; if(k!=i) { tmpht=ht[i+1]; ht[i+1]=ht[k+1]; ht[k+1]=tmpht; } ht[0].w=num;/*用ht的首单元存放叶子结点个数*/ return ht; /*返回数组*/

41 五、哈夫曼树(8) 生成哈夫曼树 int CreateHuffman(HUFFMANTREE ht)
int i,num,k,j,root; HUFFMANNODE hfnode; num=ht[0].w; for(i=1;i<=num-1;i++) /*需要生成num-1个结点，循环num-1次*/ { k=2*i-1;/*每次取得最前面的两个未用结点，必定是两个权值最小的结点, k之前结点相当于从集合F中删除掉了*/ hfnode.w=ht[k].w+ht[k+1].w; /*生成新结点hfnode*/ /*权值大的做右孩子*/ hfnode.rchild=k+1; hfnode.lchild=k;

42 五、哈夫曼树(9) for(j=num+i-1;j>=k+2;j--) /*将新结点hfnode有序插入到数组中*/
if(ht[j].w>hfnode.w) ht[j+1]=ht[j]; else break; ht[j+1]=hfnode; root=j+1;/* root一直跟随新生成的结点,最后一个新生成的结点是根*/ } return root;

43 五、哈夫曼树(10) 哈夫曼编码的递归算法 typedef struct { char ch; /*叶子结点的字符*/
char codestr[20]; /*字符的编码01字符串*/ }HUFFMANCODE; void GetHuffmanCode(HUFFMANTREE ht,int root,char *codestr) {/*哈夫曼树树存放在ht中, root是根,codestr用来暂存叶子结点编码,一开始为空*/ int len; if(ht[root].lchild==-1) /*是叶子结点，记录叶子结点的哈夫曼编码*/ { code[codenum].ch=ht[root].ch; /*codenum是全局变量， 是已获得的编码个数，初始值是0*/ strcpy(code[codenum].codestr,codestr); codenum++;/*编码个数增1*/ }

44 五、哈夫曼树(11) else {/*不是递归终点，继续递归调用*/ len=strlen(codestr);
codestr[len]='0'; /*左分支编码是0*/ /*向左孩子递归之前，调整路径上的编码序列，末尾增加0*/ codestr[len+1]=0; GetHuffmanCode(ht,ht[root].lchild,codestr);/*向左递归*/ /*右分支编码是1，向右孩子递归之前，将原编码末尾0改为1*/ codestr[len-1]='1'; GetHuffmanCode(ht,ht[root].rchild,codestr);/*向右递归*/ /*左右孩子递归返回后，向上返回之前，删掉编码末尾的一位*/ codestr[len-1]=0; }

45 六、树和森林——树的存储(1) 1．孩子表示法 #define MAXSIZE 50 typedef struct childnode {
int child; /*孩子结点下标*/ struct childnode *next; /*下一个孩子*/ }CHILDNODE,*CHILDNODEPTR; typedef struct char data; /*假定树结点的数据域是char型*/ CHILDNODE childlink; /*孩子链表的头结点*/ }CTREENODE; CTREENODE node[MAXSIZE]; /*存放树结点的数组*/ int num,root; /*结点总数和根结点下标*/ }CTREE;

46 六、树和森林——树的存储(2) 2．孩子－双亲表示法 typedef struct {
char data; /*假定树结点的数据域是char型*/ int parent; /*结点的双亲，-1表示NULL*/ CHILDNODE childlink; /*孩子链表的头结点*/ }CPTREENODE;

47 六、树和森林——树的存储(3) 3．孩子－兄弟表示法 typedef struct btreenode {
char data;/*假设数据域是char型*/ struct btreenode * firstchild;/*指向第一个孩子结点*/ struct btreenode * nextsibling; /*指向下一个兄弟结点*/ } CSTREENODE, *CSTREENODEPTR,*CSTREE;

48 六、树和森林——森林与二叉树的转换

49 六、树和森林——树和森林的遍历 1．树的遍历 2．森林的遍历
⑴层序遍历，即从根开始，从左向右、自上而下按层次遍历一个树。这种方式与树的二叉树表示无关。 ⑵先序遍历，即先访问根结点，然后再先序遍历它的各个子树。这个顺序与先序遍历树的二叉树表示是一致的。 ⑶后序遍历，即先后序根结点的各个子树，最后访问根结点。这个顺序与中序遍历树的二叉树表示是一致的。 2．森林的遍历 ⑴层序遍历，即将森林的各棵树的根看成是第一层结点，从这一层开始，自左向右、自上而下遍历各层结点。 ⑵先序遍历，即先序遍历第一棵树，然后先序遍历其他树。这个顺序与先序遍历森林的二叉树表示是一致的。 ⑶中序遍历，即中序遍历第一棵树根结点的子树森林，然后访问第一棵树的根结点，最后中序遍历其他树组成的森林。这个顺序与中序遍历森林的二叉树表示是一致的。

50 导航图(1)

51 导航图(2)

52 导航图(3)

53 导航图(4)

54 导航图(5)

55 导航图(6)