a h哈夫曼二叉树编码_最优二叉树怎么画_二叉树 哈夫曼

* A B C D E A B D C E T 后序序列：CBEDA 后序线索二叉树 0 0 0 0 1 1 1 1 1 1 ^ A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 头结点： lt 0, lc指向根结点 rt 1, rc指向遍历序列中最后一个结点 遍历序列中第一个结点的lc域和最后 一个结点的rc域都指向头结点 A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 ^ * 中序线索化二叉树 思路： 先创建一个头结点, 在进行中序遍历过程中需保留当前结点p的前驱结点的指针，设为pre，在p不空的情况下： 1、遍历左子树（左子树线索化） 2、对空指针线索化： a 若p- lc NULL，则使p- lt 1,且p- lc pre; b 若pre- rc NULL,则使pre- rt 1,且pre- rc p;pre p; 3、遍历右子树（右子树线索化） 算法 按中序线索化二叉树 A B C D E t 0 1 pr p i P- A JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; //头结点 if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; A B D C E bt ^ ^ ^ ^ ^ ^ 0 0 0 0 0 0 0 0 0 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr p i P- A P- B JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 0 0 0 0 0 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr P NULL i P- A P- B JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 0 0 0 0 0 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr P i P- A 输出:B JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 0 0 0 0 0 0 1 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ t 0 1 pr P 输出:B i P- A P- C JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 0 0 0 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ t 0 1 pr P NULL i P- A P- C 输出:B JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 0 0 0 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ ^ t 0 1 pr P i P- A 输出: B C JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 0 0 0 0 1 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ t 0 1 pr P NULL i P- A 输出: B C JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 0 0 1 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ ^ t 0 1 pr P i 输出: B C A JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 0 0 1 0 1 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ t 0 1 P i 输出: B C A pr P- D JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ t 0 1 P i 输出: B C A pr P- D P- E JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ t 0 1 P NULL i 输出: B C A pr P- D P- E JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 0 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ ^ t 0 1 P i 输出: B C A E pr P- D JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 0 1 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ t 0 1 P NULL i 输出: B C A E pr P- D JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 1 算法 按中序线索化二叉树 A B C D E A B D C E bt ^ ^ t 0 1 P i 输出: B C A E D pr JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 0 1 1 1 算法 按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt ^ t 0 1 P NULL i 输出: B C A E D pr JD *zxxsh JD *bt JD *p,*pr,*s[M],*t; int i 0; t JD * malloc sizeof JD ; t- lt 0; t- rt 1; t- rc t; if bt NULL t- lc t; else t- lc bt; pr t; p bt; do while p! NULL s[i++] p; p p- lc; if i 0 p s[--i]; printf "%c ",p- data ; if p- lc NULL p- lt 1; p- lc pr; if pr- rc NULL pr- rt 1; pr- rc p; pr p; p p- rc; while i 0||p! NULL ; pr- rc t; pr- rt 1; t- rc pr; return t ; 0 0 0 0 1 0 1 1 1 1 1 * 算法 按中序线索化二叉树 A B C D E 输出: B C A E D A B D C E t 0 1 1 1 1 1 1 1 0 0 0 0 * JD *pre; //全局变量 void Thread JD *&p if p! NULL Thread p- lc ; if p- lc NULL p- lc pre; p- lt 1; else p- lt 0; if pre- rc NULL pre- rc p; pre- rt 1; else pre- rt 0; pre p; Thread p- rc ; JD *CreatThread JD *bt JD *h; h JD * malloc sizeof JD ; h- lt 0; h- rt 1; h- rc bt; //头结点 if bt NULL h- lc head; else h- lc bt; pre h; Thread bt ; pre- rc h; pre- rt 1; h- rc pre; return h; 递归算法： * 算法 按中序线索化二叉树 遍历中序线索二叉树 在中序线索二叉树中找结点后继的方法： （1）若rt 1, 则rc域直接指向其后继 （2）若rt 0, 则结点的后继应是其右子树的左链尾（lt 1 的结点 在中序线索二叉树中找结点前驱的方法： （1）若lt 1, 则lc域直接指向其前驱 （2）若lt 0, 则结点的前驱应是其左子树的右链尾（rt 1 的结点 A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 * 中序线索二叉树的基本运算 1、查找中序序列的第一个结点 2、查找中序序列的最后一个结点 3、查找结点p的前驱结点 4、查找结点p的后继结点 5、输出中序遍历结果 6、输出逆中序遍历结果 * 1、查找中序序列的第一个结点 从根沿左指针向下到达最左下结点，即为中序的第一个结点。

JD *FirstNode JD *bt JD *p bt- lc; while p- lt 0 p p- lc; return p; 2、查找中序序列的最后一个结点 头结点的rc指向中序的最后一个结点。 JD *LastNode JD *bt return bt- rc; * 3、查找p结点的前驱结点 若p- lt 1,则p- lc为前驱；否则，查找p结点的左孩子的最右下结点，该结点即为p的前驱 JD *PreNode JD *p JD *pre; pre p- lc; if p- lt! 1 while pre- rt 0 pre pre- rc; return pre ; * 4、查找p结点的后继结点 若p- rt 0,则p- lc为后继；否则，查找p结点的右孩子的最左下结点，该结点即为p的后继 JD *PostNode JD *p JD *post; post p- rc; if p- rt! 1 while post- lt 0 post post- lc; return post ; * 5、输出中序遍历序列 先访问第一个结点，继续访问其后继，直到遍历完所有结点。 void ThreadInorder JD *bt JD *p; p FirstNode bt ; while p! bt cout p- data; p PostNode p ; * 6、输出逆中序遍历序列 先访问最后一个结点，继续访问其前驱，直到遍历完所有结点。

void ThreadInorder1 JD *bt JD *p; p LastNode bt ; while p! bt cout p- data; p PreNode p ; * 按层次遍历 按层次遍历需要一个队列，开始时将整棵树的根结点入队，然后每从队列中删除一个结点并输出该结点时，把它的非空左、右孩子结点入队，当队列为空时算法结束。 void Levelorder JD *bt JD *p; JD *q[QueSize]; int front 0,rear 0; if bt! NULL rear rear+1 %QueSize; q[rear] bt; while front! rear front front+1 % QueSize; p q[fornt]; printf “%c”,p- data ; if p- left! NULL rear rear+1 %QueSize; q[rear] p- left; if p- right! NULL rear rear+1 %QueSize; q[rear] p- right; //end of while * 说明：对于先序、中序、后序遍历序列中： 由先序和中序遍历结果可以唯一确定一棵二叉树。

由后序和中序遍历结果可以唯一确定一棵二叉树。 由先序和后序遍历结果不能唯一确定一棵二叉树。 若一棵二叉树的先序、中序序列相同，则该二叉树的形态为： 空树、只有根结点、右单支 若一棵二叉树的后序、中序序列相同，则该二叉树的形态为： 空树、只有根结点、左单支 若一棵二叉树的先序、后序序列相同，则该二叉树的形态为： 空树、只有根结点 * 例：一棵二叉树的先根、中根遍历结果如下，画出该二叉树。 先根：ABCDEFG 中根：EAFG 练习：二叉树的后序、中序周游结果如下，画出该二叉树。 后序：座机电话号码 （每位数字代表一个结点） 中序：座机电话号码 A B F C D E G * 作业： 1、假定一棵二叉树的广义表表示为 a b c ,d e,f ，分别写出它的先序、中序、后序和层次遍历的结果。 2、已知一棵二叉树的先序和中序序列，求该二叉树的后序序列。 先序：ABCDEFGHIJ 中序：CBAEFDIHJG 3、已知一棵二叉树的中根和后根序列，求该二叉树的深度和度为2、度为1和叶子结点数。 中根：EAGIHJF 后根：CEDBIJHGFA 4、一个二叉树的先序、中序和后序分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。

先序：__B__F__ICEH__G 中序：D__KFIA__EJC__ 后序：__K__FBHJ__G__A 答: ABDFKICEHJG DBKFIAHEJCG DKIFBHJEGCA * 遍历算法应用 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C ? ? D E ? G ? ? F ? ? ? A B C D E F G JD *crt_bt_pre JD *bt char ch; scanf "%c",&ch ; getchar ; if ch ‘ ‘ bt NULL; else bt JD * malloc sizeof JD ; bt- data ch; bt- lchild crt_bt_pre bt- lchild ; bt- rchild crt_bt_pre bt- rchild ; return bt ; * 遍历算法应用 续 A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 统计二叉树中叶子结点个数算法 * #include #include typedef struct node char data; struct node *lchild,*rchild; JD; void countleaf JD *bt,int *count if bt! NULL if bt- lchild NULL && bt- rchild NULL *count ++; return; countleaf bt- lchild,count ; countleaf bt- rchild,count ; JD *crt_bt_pre JD *bt char ch; printf "ch " ; scanf "%c",&ch ; getchar ; if ch ‘ ' bt NULL; else bt JD * malloc sizeof JD ; bt- data ch; bt- lchild crt_bt_pre bt- lchild ; bt- rchild crt_bt_pre bt- rchild ; return bt ; void main JD *head NULL; int count 0; head crt_bt_pre head ; countleaf head,&count ; printf "leaf node is %d\n",count ; * 遍历算法应用 续 求二叉树深度算法 A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ * JD *crt_bt_pre JD *bt …………. void treedepth JD *bt,int *l,int *h int l1 0,l2 0,h1 0,h2 0; if bt! NULL *l ++; if *l *h *h *l; treedepth bt- lchild,&l1,&h1 ; treedepth bt- rchild,&l2,&h2 ; if h1 h2 *h *h+h1; else *h *h+h2; void main JD *head NULL; int level 0,high 0; head crt_bt_pre head ; treedepth head,&level,&high ; printf "depth is %d\n",high ; * 6.4 树和森林 树的性质 性质1：树中的结点数等于所有结点的度数加1。

性质2：度为k的数中第i层上至多有ki-1个结点 i 1 . 性质3：深度为h的k叉树至多有 kh-1 / k-1 个结点。 性质4：具有n个结点的k叉树的最小深度为 * 树的存储结构 双亲数组存储 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 数据存储结构的定义: typedef struct node datatype data; int parent; JD; JD t[M]; * a b c d e f h g i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9 6 0 1 2 3 4 5 7 8 9 data parent 0号单元不用或 存结点个数 如何找孩子结点 如何找兄弟结点 * 孩子链表存储 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d data child1 child2 ………. childD data degree child1 child2 ………. childd 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表 孩子结点：typedef struct node int child; //该结点在表头数组中下标 struct node *next; //指向下一孩子结点 JD; 表头结点：typedef struct tnode datatype data; //数据域 struct node *fc; //指向第一个孩子结点 TD; TD t[M]; //t[0]不用 * a b c d e f h g i 6 0 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 ^ 4 5 ^ ^ 9 7 8 ^ 6 ^ ^ ^ ^ ^ 如何找双亲结点 * 带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 4 5 9 7 8 6 ^ ^ ^ ^ ^ ^ ^ ^ ^ 0 1 2 2 3 5 5 5 1 parent a b c d e f h g i 表头结点：typedef struct tnode datatype data; int parent; struct node *fc; TD; TD t[M]; 孩子结点：typedef struct node int child; struct node *next; JD; * 孩子兄弟链式存储（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点. 特点 操作容易 破坏了树的层次 typedef struct node datatype data; struct node *fch, *nsib; JD; a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ * 树与二叉树转换 A C B E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 对应 孩子兄弟存储 二叉链表存储 解释 解释 * 6.5 二叉树的应用 哈夫曼树 Huffman ——带权路径长度最短的树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径. 路径长度：路径上的分支数 树的带权路径长度：树中所有叶子结点带权结点的路径长度之和 Huffman树——设有n个权值 w1,w2,……wn ，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树 或最优二叉树 。

* 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 a b c d 7 5 2 4 WPL 7*2+5*2+2*2+4*2 36 d c a b 2 4 7 5 WPL 7*3+5*3+2*1+4*2 46 a b c d 7 5 2 4 WPL 7*1+5*2+2*3+4*3 35 满二叉树或完全二叉树不一定是最优二叉树。 权值越大的结点离根越近的二叉树为最优二叉树。 * 构造Huffman树的方法——Huffman算法 构造Huffman树步骤 根据给定的n个权值 w1,w2,……wn ，构造n棵只有根结点的二叉树，令其权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树 * 例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 a 7 b 5 c 2 d 4 6 11 18 * 例 w 5, 29, 7, 8, 14, 23, 3, 11 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 8 7 15 14 29 23 3 5 8 11 11 3 5 8 19 14 29 23 8 7 15 11 3 5 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42 29 14 8 7 15 29 58 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 WPL ？ 271 Huffman树不唯一. * Huffman算法实现 一棵有n个叶子结点的Huffman树有2n-1个结点 Huffman树没有度为1的结点， 又 叶子结点数为度为2的结点数加1。

故 Huffman树的总结点数为：n+ n-1 2n-1 采用顺序存储结构——一维结构数组 结点类型定义 typedef struct int data; int pa,lc,rc; JD; * lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 0 0 0 7 5 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 7 5 2 4 6 0 0 lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 5 5 0 0 0 k x1 3,x2 4 m1 2,m2 4 2 lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6110 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k x1 2,x2 5 m1 5,m2 6 3 lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0 0 0 4 5 6 76 5 5 6 7 0 k x1 1,x2 6 m1 7,m2 11 4 * #define M 50 #define MAX 100 typedef struct int data; int pa,lc,rc; JD; void huffman int n,int w[],JD t[] int i,j,k,x1,x2,m1,m2; for i 1;i 2*n ;i++ t[i].pa t[i].lc t[i].rc 0; if i n t[i].data w[i]; else t[i].data 0; for i 1;i n;i++ m1 m2 MAX; x1 x2 0; for j 1;j n+i ;j++ if t[j].data m1 && t[j].pa 0 m2 m1; x2 x1; m1 t[j].data; x1 j; else if t[j].data m2 && t[j].pa 0 m2 t[j].data; x2 j; k n+i; t[x1].pa t[x2].pa k; t[k].data m1+m2; t[k].lc x1; t[k].rc x2; Huffman树应用 最佳判定树 等级 分数段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 0.05 0.15 0.40 0.30 0.10 a 60 a 90 a 80 a 70 E Y N D Y N C Y N B Y N A 70?a 80 a 60 C Y N B Y N D Y N E Y N A 80?a 90 60?a 70 E A D B C a 80 a 70 a 60 a 90 E Y N D Y N C Y N B Y N A * Huffman编码：数据通信用的二进制编码 思想：根据字符出现频率编码，使电文总长最短 编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列 例 要传输的字符集 D C,A,S,T, ; 字符出现频率 w 2,4,2,3,3 C S 3 3 6 4 2 2 4 8 14 T ; A 0 0 1 1 0 1 1 0 T : 00 ; : 01 A : 10 C : 110 S : 111 * 译码：从Huffman树根开始，从待译码电文中逐位取码。

若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束 例 电文是 CAS;CAT;SAT;AT 其编码 “1XXXXXXXXXX1XXXXXXXXXX1000011000” 电文为“1101000” 译文只能是“CAT” C S 3 3 6 4 2 2 4 8 14 T ; A 0 0 1 1 0 1 1 0 T : 00 ; : 01 A : 10 C : 110 S : 111 * 作业： 1、如果一棵Huffman树T有n0个叶子结点，那么，树T有多少个结点？给出求解过程。 提示：Huffman树只有度为2和0的结点，又n0 n2+1,n no+n2 故：n 2n0-1 2、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点构造一棵Huffman树，并计算带权路径长度。 3、在一份电文使用了五种字符，即a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的Huffman树，并求出每个字符的Huffman编码。 * 线索二叉树 定义： 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点 线索：指向前驱或后继结点的指针 线索二叉树：加上线索的二叉链表表示的二叉树 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程 实现 在有n个结点的二叉链表中必定有n+1个空链域 索二叉树的结点中增加两个标志域 lt :若 lt 0, lc 域指向左孩子；若 lt 1, lc域指向其前驱 rt :若 rt 0, rc 域指向右孩子；若 rt 1, rc域指向其后继 结点定义： typedef struct node int data; int lt, rt; struct node *lc, *rc; JD; lc lt data rt rc * A B C D E A B D C E T 先序序列：ABCDE 先序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 * A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 ^ * 树 * 6.1 树的定义 定义 定义：树 tree 是n n 0 个结点的有限集T，其中在非空树中： 有且仅有一个特定的结点，称为树的根 root 当n 1时，其余结点可分为m m 0 个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树 subtree 特点： 树中至少有一个结点 ——根 非空树 树中各子树是互不相交的集合 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 * A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树 子树 子树 * 树的其它表示方法 F I J G K L M A B C D E H 嵌套集合表示法 A K L F C G D H M I J B E 凹入表示法 A B E K,L ,F ,C G ,D H M ,I,J 广义表表示法 * 基本术语 结点 node ——树中的元素，包括数据项及若干指向其子树的分支 结点的度 degree ——结点拥有的子树数 树的度——一棵树中最大的结点度数 叶子 leaf ——度为0的结点 孩子 child ——结点子树的根称为该结点的孩子 双亲 parents ——孩子结点的上层结点 兄弟 sibling ——同一双亲的孩子 结点的层次 level ——从根结点算起，根为第一层，它的孩子为第二层…… 树的深度 depth /高度——树中结点的最大层次数 森林 forest ——m m?0 棵互不相交的树的集合 * A B C D E F G H I J K L M 结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 结点A的层次：1 结点M的层次：4 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先 * 6.2 二叉树 定义 定义：二叉树是n?0个结点的有限集，它或为空树 n 0 ，或由一个根结点和两棵分别称为左、右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态 A 只有根结点 的二叉树 ? 空二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空 度为2的有序树 * 练习： 给出3个结点A、B和C构成的所有形态的二叉树（不考虑结点值的差异） A B C A B C A B C A B C A B C * 二叉树性质 性质1： 性质2：深度为k的二叉树至多有 个结点 k?1 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 n2+1。

或：二叉树的叶子结点数等于双分支结点数加1。 * 几种特殊形式的二叉树 满二叉树 定义： 特点：每一层上的结点数都是最大结点数 完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1 性质 性质4： * 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 * 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i 1?i?n ，有： 1 如果i 1，则结点i是二叉树的根，无双亲；如果i 1，则其双亲是?i/2? 2 如果2i n，则结点i无左孩子；如果2i?n，则其左孩子是2i 3 如果2i+1 n，则结点i无右孩子；如果2i+1?n，则其右孩子是2i+1 * 作业： 1、已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 1、设度为0、1、2的结点数及总结点数分别为n0、n1、n2、n。

则： n0 50 n n0+n1+n2 n-1 n1+2n2 得：n2 49 故：n-1 n1+2*49 n n1+99 所以当n1 0时，n最少，所以n至少有99个结点。二叉树 哈夫曼 * 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 * typedef ElemType SqBinTree[MaxSize]; 二叉树顺序存储结构的类型定义为： 注：下标为0的位置不用或用于存放二叉树的结点数。 练习： 假设二叉树的存储结构如下，画出对应的二叉树。 25 15 36 10 20 32 48 4 11 18 0 1 2 3 4 5 6 7 8 9 10 9 I D P C F M E H N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 * 链式存储结构 二叉链表 typedef struct node ElemType data; struct node *lchild, *rchild; BTNode; lchild data rchild A B C D E F G 在n个结点的二叉链表中，有n+1个空指针域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ * 三叉链表 typedef struct node ElemType data; struct node *lchild, *rchild, *parent; JD; lchild data parent rchild A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ * 6.3 遍历二叉树和线索二叉树 树的遍历 遍历——如何按某条搜索路径访问二叉树中的每个顶点，使每个节点被访问一次且仅被访问一次 常用方法 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点. * 二叉树的遍历 方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点 D L R LDR、LRD、DLR RDL、RLD、DRL * A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: * A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: * A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A 后序遍历: B * - + / a * b - e f c d 先序遍历： 中序遍历： 后序遍历： 层次遍历： - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f * 算法 递归算法 void Preorder JD *bt //先序遍历 if bt! NULL printf "%d\t",bt- data ; Preorder bt- lchild ; Preorder bt- rchild ; typedef struct node ElemType data; struct node *lchild,*rchild; JD; * 主程序 Pre T 返回 返回 pre T R ; 返回 返回 pre T R ; A C B D T B printf B ; pre T L ; B T A printf A ; pre T L ; A T D printf D ; pre T L ; D T C printf C ; pre T L ; C 返回 T 左是空返回 pre T R ; T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre T R ; 先序序列：A B D C * void Inorder JD *bt //中序遍历 if bt! NULL Inorder bt- lchild ; printf "%d\t",bt- data ; Inorder bt- rchild ; void Postorder JD *bt //后序遍历 if bt! NULL Postorder bt- lchild ; Postorder bt- rchild ; printf "%d\t",bt- data ; * 非递归算法 A B C D E F G p i P- A 1 A B C D E F G p i P- A P- B 2 A B C D E F G p i P- A P- B P- C 3 p NULL A B C D E F G i P- A P- B 访问：C 4 中序遍历 * p A B C D E F G i P- A 访问：C B 5 A B C D E F G i P- A P- D 访问：C B p 6 A B C D E F G i P- A P- D P- E 访问：C B p 7 A B C D E F G i P- A P- D 访问：C B E p 8 * A B C D E F G i P- A P- D P- G 访问：C B E P NULL 9 A B C D E F G i P- A 访问：C B E G D p 11 A B C D E F G i P- A P- F 访问：C B E G D p 12 A B C D E F G i P- A P- D 访问：C B E G p 10 * A B C D E F G i P- A 访问：C B E G D F p NULL 13 A B C D E F G i 访问：C B E G D F A p 14 A B C D E F G i 访问：C B E G D F A p NULL 15 * void inorder JD *bt int i 0; JD *p,*s[M]; p bt; do while p! NULL s[i++] p; p p- lchild; if i 0 p s[--i]; printf "%d\t",p- data ; p p- rchild; while i 0||p! NULL ;

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-33127-1.html