《第6章树和二叉树》由会员分享，可在线阅读，更多相关《第6章树和二叉树（114页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与技术学院计算机科学与技术学院数据结构数据结构第6章 树和二叉树1计算机科学与技术学院计算机科学与技术学院数据结构数据结构主要内容6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树和森林6.6 赫夫曼树及其应用2计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和基本术语(1)树（Tree）是n(n 0)个结点的有限集。在任意一棵非空树中: A、有且仅有一个称为根的结点； B、当n 2时，其余结点分为m(m 0) 个互不相交的子集，每个子集本身又是一棵树，称为根的子树。 以上是一个递归的定义在树的定义中又用到了树的概念，由此可
2、见递归是树的固有特性。ABMLKJIHGFEDC3计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和基本术语(2)ABMLKJIHGFEDC树根：A 每个子集都是满足树的定义的树，称为A的子树B子树、C子树、D子树。 树根A没有直接前驱；其余结点有且仅有一个直接前驱有，有0个或多个直接后继。三个互不相交的子集： B, E, F, K, L C ,G D, H, I, J, M 树的特征：层次性和分支性4计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和基本术语(3)结点的度：结点的非空子树个数树的度：树内各结点度的最大值分支结点(非终端结点) ：
3、度非0的结点叶子结点(终端结点)：度为0的结点孩子：结点的子树的根双亲：孩子的直接前驱结点兄弟：同一个双亲的孩子结点互称为兄弟子孙：以某结点为根的子树中的任一结点祖先：从根到该结点所分支上的所有结点堂兄:双亲在同一层的结点5计算机科学与技术学院计算机科学与技术学院数据结构数据结构结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根在第L+1层。树的深度（高度）：结点层次的最大值有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。森林：m（m0）个树的集合ABMLKJIHGFEDCTree = (A (
4、B ( E ( K , L ), F ), C ( G ), D ( G, H ( M ), I, J ) ) )6.1 树的定义和基本术语(4)6计算机科学与技术学院计算机科学与技术学院数据结构数据结构树的基本操作：树的基本操作：构造空树InitTree(&T);销毁树DestroyTree(&T);创建树CreateTree(&T, definition);清空树ClearTree(&T);判断空树TreeEmpty(T);求树的深度TreeDepth(T);求双亲parent(T, cur_e);求长子LeftChild(T, cur_e);求右邻兄弟RightSibling(T, cu
5、r_e);插入子树InsertChild(&T, &p, i, c);删除子树DeleteChild(&T, &p, i);遍历树TraverseTree(T, visite();6.1 树的定义和基本术语(5)7计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2 二叉树二叉树的定义二叉树的性质二叉树的存储结构8计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(1)二叉树是另一种树型结构，它的特点是每个结点至多只有两 棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树可以为空，称为空二叉树;非空二叉树一
6、定有两个子树；左、右子树有次序关系，不能互换；二叉树可以有5种基本形态：二叉树不是结点的度都不超过2的有序树.6.2 二叉树根根左子树右子树根根根根根根9计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(2)具有三个结点的树与二叉树6.2 二叉树A、三个结点的树有两种不同的形态B、三个结点的二叉树有五种不同的形态树型结构的共同特征：层次性、分支性10计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(3)二叉二叉树的基本操作的基本操作初始化空二叉树InitBiTree(&T)销毁二叉树DestroyBiTree(&T)创建二叉树Cr
7、eateBiTree(&T, definition)清空二叉树ClearBiTree(&T)判断空二叉树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)先序遍历二叉树PreOrderTraverse(T,visite()中序遍历二叉树InOrderTraverse(T,visit
8、e()后序遍历二叉树PostOrderTraverse(T,visite()按层次遍历levelTraverse(T, visite()6.2 二叉树11计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2 二叉树二叉树的定义二叉树的性质二叉树的存储结构12计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.2 二叉树的性质(1)性性质1 在二叉在二叉树的第的第i层上至多有上至多有2i-1个个结点点(i 1 )；性性质2 深度深度为k的二叉的二叉树上至多有上至多有2k-1个个结点点(k 1 ) ；性性质3 设任意一棵二叉任意一棵二叉树中有中有n0个度个度为0的的结点，点，
9、n2个度个度为2个个结点，点，则有：有：n0 = n2+1；6.2 二叉树满二叉树：一棵深度为k且有 2k1个结点的二叉树。即：所有非终端结点的度都等于2，且所有树叶都分布在同一个层次上。完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进行编号，当且仅当编号与深度为k的满二叉树中前n个结点一一对应。13计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.2 二叉树的性质(2)性性质4 完全二叉树的深度为完全二叉树的深度为k log2n +1 或或 k= log2(n+1) ；性性质5 将完全二叉树自上而下，自左向右地编号，对将完全二叉树自上而下，自左向右地编号，对任意一
10、任意一结点点i（1 i n）的）的结点点X有：有： A、若、若i1，则X是根；若是根；若i1, 则X的的PARENT(i)= i/2 ; B、若、若X有左孩子，有左孩子，则X左孩子左孩子LCHILD(i)=2i； C、若、若X有右孩子，有右孩子，则X右孩子右孩子RCHILD(i)=2i1； D、若、若i为奇数且奇数且i1，则X的左兄弟的左兄弟为i1； E、若、若i为偶数且偶数且idata);/访根根 PreOrderTraverse (T-lchild); PreOrderTraverse (T-rchild);25计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树
11、的递归与非递归算法(2)先序遍先序遍历二叉二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH26计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(3)中序遍中序遍历二叉二叉树 若二叉若二叉树为空，空，则空操作；否空操作；否则u中序遍中序遍历左子左子树；u访问根；根；u中序遍中序遍历右子右子树；6.3 遍历二叉树根根void InOrderTraverse (BiTree T) if (!T) return; InOrderTraverse (T-lchild); visit(T-data);/访根根 InOrderTra
12、verse (T-rchild);27计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(4)中序遍历二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH28计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(5)后序遍后序遍历二叉二叉树 若二叉若二叉树为空，空，则空操作；否空操作；否则u后序遍后序遍历左子左子树；u后序遍后序遍历右子右子树；u访问根；根；6.3 遍历二叉树根根void PostOrderTraverse (BiTree T) if (!T) return; Po
13、stOrderTraverse (T-lchild); PostOrderTraverse (T-rchild); visit(T-data);/访根根29计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(6)先序遍先序遍历二叉二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH30计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树递归与非递归算法(7)中序遍中序遍历的非的非递归算法算法(借助堆栈实现借助堆栈实现)void InOrderTraverse ( BiTree bt, void(*v
14、isit)(BiTree) /中序遍中序遍历的非的非递归算法算法 InitStack(S); Push(S,T); While (!StackEmpty(S) /栈非空非空时 While (GetTop(S,p)&P) Push(S,p-lchild); /一直向左走到一直向左走到头，并将所，并将所经历的的结点入点入栈 Pop(s,p); /将空指将空指针退出退出栈S If (!StackEmpty(S) /栈非空非空时 Pop(s,p); /弹出出结点点p If(!visit(p-data) return ERROR; Push(S,p-rchild); /将将结点点p的右子的右子树入入栈
15、/if /while/InOrderTraverse6.3 遍历二叉树31计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 已知一棵度已知一棵度为m的的树中有中有N1个度个度为1的的结点，点，N2个度个度为2的的结点，点，.， Nm个度个度为m的的结点，点，试问该树中有多中有多少个叶子少个叶子结点。点。6.3 遍历二叉树32计算机科学与技术学院计算机科学与技术学院数据结构数据结构解答解答:解决此解决此类问题的关的关键是要把是要把树的的结点个数和点个数和树中各中各结点的度点的度联系起系起来。来。设该树中叶子中叶子结点个数点个数为N0。则该树结点个数点个数为N0+N1+.+Nm=，又，
16、又该树的的结点个数也点个数也为1+所以所以6.3 遍历二叉树33计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 用一用一维数数组存放的一棵二叉存放的一棵二叉树如下如下图所示。写所示。写出后序遍出后序遍历该二叉二叉树时访问结点的序列。点的序列。解答：解答：GHDBEFCA6.3 遍历二叉树ABCDEFGHABCDEFGH34计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 设m和和n分分别为二叉二叉树中的两个中的两个结点，点，问：（1）当）当n在在m的左方，先序遍的左方，先序遍历时n在在m的前面的前面吗？中序遍？中序遍历时n在在m的前面的前面吗？（2）当）当n在在m的右
17、方，中序遍的右方，中序遍历时n在在m的前面的前面吗？（3）当）当n是是m的祖先，先序遍的祖先，先序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？（4）当）当n是是m的子的子孙，中序遍，中序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？6.3 遍历二叉树35计算机科学与技术学院计算机科学与技术学院数据结构数据结构（1）当）当n在在m的左方，先序遍的左方，先序遍历时n在在m的前面的前面吗？中序遍？中序遍历时n在在m的前面的前面吗？6.3 遍历二叉树mnnm(1)(2)解答：（解答：（1）n在在m的左方可以有上的左方可以有上图所示的两种情况。因所示
18、的两种情况。因为先序遍先序遍历为“根左右根左右”，因此由上，因此由上图可知，先序遍可知，先序遍历中，中， n可以在可以在m的前面，的前面，也可以在也可以在m的后面；中序遍的后面；中序遍历为“左根右左根右”，由上，由上图可知，中序遍可知，中序遍历中中n必在必在m的前面。的前面。36计算机科学与技术学院计算机科学与技术学院数据结构数据结构（2）当）当n在在m的右方，中序遍的右方，中序遍历时n在在m的前面的前面吗？6.3 遍历二叉树nmmn(1)(2)解答：（解答：（2）中序遍）中序遍历序列中，序列中，n必在必在m的后面。的后面。37计算机科学与技术学院计算机科学与技术学院数据结构数据结构（3）当）
19、当n是是m的祖先，先序遍的祖先，先序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？6.3 遍历二叉树解答：（解答：（3）先序遍）先序遍历时，祖先必定在子，祖先必定在子孙的前面；后序遍的前面；后序遍历时，祖先必在子祖先必在子孙的后面。（的后面。（对于中序遍于中序遍历，左孩子及其子，左孩子及其子孙必定在祖必定在祖先的前面，而右孩子及其子先的前面，而右孩子及其子孙必定在祖先的后面。）必定在祖先的后面。）（4） 当当n是是m的子的子孙，中序遍，中序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？解答：由（解答：由（3）可知，中序遍）可知，中序遍历时，n
20、可能在可能在m之前，也可能在之前，也可能在m之之后。而后序遍后。而后序遍历时，n必定在必定在m的前面。的前面。38计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 给定一棵用二叉定一棵用二叉链表表示的二叉表表示的二叉树，每，每个个结点都有点都有2个指个指针（lchild,rchild)，分，分别用来表示指向其左、右子女，用来表示指向其左、右子女，该树的根的根结点指点指针为t，试编写一个非写一个非递归求二叉求二叉树的的叶子叶子结点数目的算法函数。点数目的算法函数。6.3 遍历二叉树39计算机科学与技术学院计算机科学与技术学院数据结构数据结构解析：解析：本本题是要求是要求编写算法求出二
21、叉写算法求出二叉链表表示二表表示二叉叉树的叶子的叶子结点的个数，并且已点的个数，并且已经给出了出了该二叉二叉树的基本存的基本存储结构，构，注意注意这里要求用非里要求用非递归的方的方法法进行求解行求解。其。其实求解二叉求解二叉树中叶子中叶子结点的个数，点的个数，可以采用非可以采用非递归的方法的方法进行二叉行二叉树的遍的遍历。在遍在遍历的的过程中如果遇到了叶子程中如果遇到了叶子结点，点，则将其将其统计到到叶子叶子结点的个数里面。当遍点的个数里面。当遍历完整个二叉完整个二叉树时，也就求出了叶子也就求出了叶子结点的个数。点的个数。算法的思想是首先算法的思想是首先定定义二叉二叉树的二叉的二叉链表的存表的
22、存储结构，构，采用中序遍采用中序遍历二叉二叉树的方法的方法。这里用到里用到辅助助栈S，先将根，先将根结点点入入栈，当，当栈非空非空时，让指指针一直向左走到尽到，一直向左走到尽到，并将所并将所经历的的结点入点入栈。再将空指。再将空指针退退栈，弹出出栈顶结点。若点。若该结点是叶子点是叶子结点，点，则叶子数目叶子数目变量量count加加1。然后再将。然后再将该结点的右子点的右子树入入栈，中，中序遍序遍历完整个二叉完整个二叉树后，函数返回叶子后，函数返回叶子总数数count。6.3 遍历二叉树40计算机科学与技术学院计算机科学与技术学院数据结构数据结构答案：答案：二叉二叉树的二叉的二叉链表的存表的存储
23、结构：构：typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指左右孩子指针BiTNode,*BiTree;int CountLeaf(BiTree t) BiTree p; /定定义工作指工作指针p int count=0; /初始化叶子数目初始化叶子数目变量量count InitStack(S); /建立空建立空栈 6.3 遍历二叉树41计算机科学与技术学院计算机科学与技术学院数据结构数据结构 Push(S,t); /将二叉将二叉树的根的根结点入点入栈 while(!StackEmpty(S
24、) /栈非空非空时 while(GetTop(S,p)&p) Push(S,p-lchild);/一直向左走到一直向左走到头，并将所，并将所经历的的结点入点入栈 Pop(S,p); /将空指将空指针退出退出栈S if(!StackEmpty(S) /栈非空非空时 Pop(S,p); /弹出出结点点p if(p-lchild=NULL&p-rchild=NULL) /若若结点点p为叶子叶子结点点 count+; /该二叉二叉树的叶子的叶子结点数目加点数目加1 Push(S,p-rchild); /将将结点点p的右子的右子树入入栈 /if /whilereturn count; /函数返回叶子函数
25、返回叶子结点的数目点的数目/CountLeaf6.3 遍历二叉树42计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树递归与非递归算法(8)先序遍先序遍历的非的非递归算法算法(借助堆栈实现借助堆栈实现)void PreOrderTraverse (BiTree bt)if (!bt) return;InitStack(S); push(S, bt); /树根的指根的指针进栈while (!EmptyStack(S)pop(S, p);while(p) /沿着左沿着左链一路向下一路向下 visit(p-data); /访问 if(p-rchild) push(S,p-
26、rchild); /右孩子右孩子进栈 p=p-lchild; 6.3 遍历二叉树43计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树44计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.3 表达式求值表达式求值 6.3 遍历二叉树算术表达式中的二叉树表示二元算符右操作数左操作数一元算符右操作数Model ：a+b*(c-d)-e/fabcdef+*-/先序遍历得到前缀表达式：- + a * b c d / e f中序遍历得到中缀表达式：a + b * ( c d ) e / f
27、后序遍历得到后缀表达式：a b c d - * + e f / - 45计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法表达式求值表达式求值二叉树的运算举例二叉树的运算举例层序遍历二叉树层序遍历二叉树46计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.4 二叉树的运算举例(1)计算二叉树中的结点数计算二叉树中的结点数 Number() 思路：二叉树结点数思路：二叉树结点数1+左子树结点数左子树结点数+右子树结点数右子树结点数6.3 遍历二叉树int Number(BiTree
28、bt) if(!bt) return 0; /空二叉树空二叉树 else nl=Number(bt-lchild); nr=Number(bt-rchild); return 1+nl+nr; void Number(BiTree bt, int &n) if(!bt) return; n+; /累加结点数累加结点数 Number(bt-lchild, n); Number(bt-rchild, n); 47计算机科学与技术学院计算机科学与技术学院数据结构数据结构计算二叉算二叉树中叶子中叶子结点的数目点的数目 Leafs() 思路：叶子数左子思路：叶子数左子树叶子数叶子数+右子右子树叶子数叶子
29、数6.3.4 二叉树的运算举例(2)6.3 遍历二叉树int Leafs(BiTree bt) if(!bt) return 0; /空二叉树空二叉树 if(！bt-lchild & ！bt-rchild) return 1; LL=Leafs(bt-lchild); LR=Leafs(bt-rchild); return LL+LR; void Leafs(BiTree bt，int &n) if(!bt) return ; if(!bt-lchild & !bt-rchild) n+; Leafs(bt-lchild, n); Leafs(bt-rchild, n); 48计算机科学与技术
30、学院计算机科学与技术学院数据结构数据结构例例 已知深度已知深度为h的二叉的二叉树以一以一维数数组BT(1:2h-1)作作为其存其存储结构，构，请写一算法，求写一算法，求该二叉二叉树中叶中叶结点的个数。点的个数。6.3 遍历二叉树49计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树int Leafs(BiTree bt,int h) /层序遍历二叉树，统计叶子结点的个数层序遍历二叉树，统计叶子结点的个数 len=2h-1; count=0;for(i=1;ilen) count+; /i结点没有孩子，结点没有孩子，i结点就是叶子结点结点就是叶子结点 else if(bt
31、2*i+1=0&bt2*i=0) count+; /i结点的左右孩子均为空，结点的左右孩子均为空，i结点就是叶子结点结点就是叶子结点return count;50计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.4 二叉树的运算举例(3)计算二叉算二叉树的深度的深度 Depth() 思路：思路： 深度深度 = max(左子左子树深度，右子深度，右子树深度深度) + 16.3 遍历二叉树int Depth(BiTree bt) if(!bt) return 0; hl=Depth(bt-lchild); /计算计算bt的左子树深度的左子树深度 hr=Depth(bt-rchild)
32、; /计算计算bt的右子树深度的右子树深度 return (hlhr ? (h1+1):(hr+1) 51计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法表达式求值表达式求值二叉树的运算举例二叉树的运算举例层序遍历二叉树层序遍历二叉树52计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.5 层序遍历二叉树(1)自上而下自上而下、自左向右自左向右地遍地遍历二叉二叉树，先被先被访问结点的孩子先被点的孩子先被访问。遍遍历思想思想为：空空树, 结束。束。初始化一个空初始化一个空队列列Q,
33、 树根入根入队;队头e元素出元素出队, 访问e;如果如果e有左孩子有左孩子, 则左孩子入左孩子入队;如果如果e有右孩子有右孩子, 则右孩子入右孩子入队;如果如果队列不空列不空转3; 否否则结束束6.3 遍历二叉树53计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.5 层序遍历二叉树(2)算法算法 LevelTraverse() void LevelTraverse(BiTree bt) /按按层次遍次遍历二叉二叉树算法算法 if( !bt ) return ; /空空树 InitQueue(Q); /初始化空初始化空队列列Q EnQueue(Q, bt); /根入根入队 whi
34、le( !EmptyQueue(Q) ) DeQueue(Q, p); /队头p出出队 visit(p-data); /访问p if(p-lchild) EnQueue(Q，p-lchild); /p的左孩子入的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入的右孩子入队 6.3 遍历二叉树54计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 6.4 线索二叉树线索二叉树(1)(1)二叉二叉树的遍的遍历序列是序列是线性序列。在二叉性序列。在二叉树上找某个上找某个结点在某种遍点在某种遍历序序列中的直接前列中的直接前驱或直接后或直接后继，
35、只能在，只能在对二叉二叉树遍遍历时动态求得。求得。如何在遍如何在遍历过程中保留下程中保留下结点的前点的前驱和后和后继的信息呢？最直接的的信息呢？最直接的办法法也也许就是就是给每个每个结点增加两个指点增加两个指针。这样做会使得做会使得结构的存构的存储密度大密度大大降低。大降低。做如下做如下规定：定： 若若结点有左子点有左子树，则其其lchild域指向其左孩子，否域指向其左孩子，否则指向其前指向其前驱；若；若结点有右子点有右子树，则其其rchild域指向其右孩子，否域指向其右孩子，否则指向其后指向其后继。 其中：其中：6.4 线索二叉树lchildLTagdataRTagrchildLtag =
36、0 lchild域指向结点的左孩子域指向结点的左孩子 1 lchild域指向结点的前驱域指向结点的前驱Rtag = 0 lchild域指向结点的右孩子域指向结点的右孩子 1 lchild域指向结点的后继域指向结点的后继55计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 6.4 线索二叉树线索二叉树(2)(2)二叉二叉树的二叉的二叉线索存索存储表示表示：6.4 线索二叉树typedef enum PointerTagLink, Thread;typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rc
37、hild; PointerTag Ltag, Rtag; /左右标志左右标志BiThrNode, * BiThrTree;中序线索二叉树：13274651327465NULLNULL中序线索二叉树中序线索二叉树56计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 线索二叉树(3)二叉树的二叉线索存储：6.4 线索二叉树1327465NULLNULL中序线索二叉树1 23 5 6 4 7 中序遍历序列中序遍历序列的起始点的起始点中序遍历序列中序遍历序列的终端点的终端点带头结点的中序线索二叉树带头结点的中序线索二叉树?57计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4
38、 线索二叉树(4)线索化，就是在已知二叉索化，就是在已知二叉链的前提下，填写每个的前提下，填写每个结点左点左线索索LTag域和右域和右线索索RTag域。域。若要建立中若要建立中(先、后）序先、后）序线索，索，则在中在中(先、后）序遍先、后）序遍历过程中完程中完成成线索化操作。索化操作。通通过中序遍中序遍历建立中序建立中序线索化索化链表的算法在教材表的算法在教材P.134,135中。中。遍遍历线索二叉索二叉树 在在线索二叉索二叉树中，由于可以直接找到每个中，由于可以直接找到每个结点的后点的后继或前或前驱，所以遍所以遍历可以用非可以用非递归的方法的方法实现，而且不必借助，而且不必借助栈.(算法算法
39、 P.134)6.4 线索二叉树58计算机科学与技术学院计算机科学与技术学院数据结构数据结构以双向以双向线索索链表表为二叉二叉树的存的存储结构构时的的中序遍中序遍历算法算法（6.5）：）：Status InorderTraverse_Thr(BiThree T, Status (*Visit)(TElemType e) /T为头结点指点指针,中序遍中序遍历带头结点的点的线索二叉索二叉树Tp=T-lchild; /p指向根指向根结点点while(p!=T) /空空树或遍或遍历结束束时，p=T while(p-LTag=link) p=p-lchild; /沿左指沿左指针找中序序列第一个找中序序列
40、第一个结点点 if(!Visit(p-data) return ERROR; /访问左子左子树为空的空的结点点 while(p-RTag=Thread&p-rchild!=T) p=p-rchild; Visit(p-data); /访问后后继结点点 p=p-rchild; /若若p有右孩子，有右孩子，则p指向其右孩子指向其右孩子结点，点，进入入while/whilereturn OK;/InorderTraverse_Thr6.4 线索二叉树59计算机科学与技术学院计算机科学与技术学院数据结构数据结构中序遍中序遍历建立中序建立中序线索化二叉索化二叉链表的算法（表的算法（6.6）：）：Stat
41、us InorderThreading(BiThrTree& Thrt,BiThrTree T)/中序遍中序遍历二叉二叉树T，并将其中序，并将其中序线索化，索化，Thrt指向指向头结点点 if（！（！（Thrt=new BiThrNode)） exit(OVERFLOW); Thrt-LTag=Link; Thrt-RTag=Thread; /建立建立头结点点 Thrt-rchild=Thrt; /初始初始时，右指，右指针回指回指 if(!T) Thrt-lchild=Thrt; /若二叉若二叉树为空，空，则左指左指针回指回指 else Thrt-lchild=T; pre=Thrt; InT
42、hreading(T); /调用函数，中序遍用函数，中序遍历过程中中序程中中序线索化二叉索化二叉树T pre-rchild=Thrt;pre-RTag=Thread; /（调用函数后，用函数后，pre指向最指向最后一个后一个结点）最后一个点）最后一个结点点线索化索化 Thrt-rchild=pre; /elsereturn OK; /InorderThreading 6.4 线索二叉树60计算机科学与技术学院计算机科学与技术学院数据结构数据结构递归中序中序线索化二叉索化二叉树的算法（的算法（6.7）：）：void InThreading(BiThrTree& p) if(p) InThread
43、(p-lchild); /左子左子树线索化索化 if(!p-lchild) /前前驱线索索 p-LTag=Thread;p-lchild=pre; /if if(!pre-rchild) /后后继线索索 pre-RTag=Thread;pre-rchild=p; /if pre=p; /p指向当前指向当前结点，点，pre指向中序序列中指向中序序列中p的前的前驱,开始开始时 /pre=Thrt, p=T InThreading(p-rchild); /右子右子树线索化索化/InThreading/递归函数最底函数最底层首先找到中序序列的第一个首先找到中序序列的第一个结点点p，对其前其前驱线索，索
44、，对pre(此此时为头结点指点指针Thrt）进行后行后继线索，再索，再继续6.4 线索二叉树61计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储结构森林与二叉树的转换树和森林的遍历62计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.1 树的存储结构(1)双亲表示法6.5 树和森林RAGKFHEDCB1A02B03C00R-14D15E16F37G68H69K6#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent;PTNode;typedef struct
45、 PTNode nodesMAX_TREE_SIZE; int r,n; /根位置和结点数目根位置和结点数目 Ptree;63计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.1 树的存储结构(2)孩子表示法6.5 树和森林RAGKFHEDCBtypedef struct CTNode int child; struct CTNode *next; *ChildPtr;typedef struct TElemType data; ChildPtr firstchild;CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; int r,n;
46、/根位置和结点数目根位置和结点数目 CTree;1B 2C03D 0A4R5E 6F7G 8H 9K 5 36 2 109 8-1764计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.1 树的存储结构(1)孩子-兄弟表示法6.5 树和森林RAGKFHEDCBtypedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling;CSNode, CSTree;firstchilddatanextsiblingK H G F C E B D AR 树的孩子兄弟表示可以将树转化为二叉树树的孩子兄弟表示
47、可以将树转化为二叉树65计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储结构森林与二叉树之间的转换树和森林的遍历66计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.2 森林和二叉树之间的转换(1)树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以唯一地转换成一棵右子树为空的二叉树。6.5 树和森林ABDECABDEC森林转化为二叉树：把森林中的每一棵树转换成二叉树；将所有二叉树的树根用线相连；以第一棵二叉树的树根为圆心，顺时针转45度。ABDEC67计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.2 森林和二叉树之间的转换(2
48、)6.5 树和森林ABDCEFGHJIABDCEFGHJIABDCEFGHJI68计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储结构森林与二叉树之间的转换树和森林的遍历69计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.3 树和森林的遍历(1)先序遍历树先序遍历树：若树不空，则：若树不空，则1. 访问根；访问根；2. 从左至右先序遍历根的各个子树。从左至右先序遍历根的各个子树。6.5 树和森林RAGKFHEDCB后序遍历树后序遍历树：若树不空，则：若树不空，则1. 从左至右后序遍历根的各个子树。从左至右后序遍历根的各个子树。 2. 访问根。访问
49、根。RAGKFHEDCB先根序列：先根序列：RADEBCFGHKRADEBCFGHK后根序列：后根序列：DEABGHKFCRDEABGHKFCR先序序列：先序序列：RADEBCFGHKRADEBCFGHK中序序列：中序序列：DEABGHKFCRDEABGHKFCR后序序列：后序序列：EDKHGFCBAREDKHGFCBAR等价70计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.3 树和森林的遍历(2)先先序遍序遍历树，等价于，等价于先先序遍序遍历由由这棵棵树转换而成的二叉而成的二叉树；后后序遍序遍历树，等价于，等价于中中序遍序遍历由由这棵棵树转换而成的二叉而成的二叉树；6.5
50、树和森林先序遍历森林先序遍历森林：若森林不空，则：若森林不空，则1. 访问第一棵树的根结点；访问第一棵树的根结点；2. 先序遍历第一棵树根结点的子树森林；先序遍历第一棵树根结点的子树森林；3. 先序遍历森林中去掉第一棵树后剩下的树构成的森林先序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林中序遍历森林：若森林不空，则：若森林不空，则1. 中序遍历第一棵树根结点的子树森林；中序遍历第一棵树根结点的子树森林；2. 访问第一棵树的根结点；访问第一棵树的根结点； 3. 中序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林中去掉第一棵树后剩下的树构成的森林71计算机科学与技术学院计算机科学
51、与技术学院数据结构数据结构6.5.3 树和森林的遍历(3)6.5 树和森林ABDCEFGHJIABDCEFGHJI等价先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG后序序列：DCBFJIHGEA72计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用最优二叉树（赫夫曼树）赫夫曼树的构造赫夫曼编码73计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价关系和等价类的定义等价关系和等价类的定义等价类的划分算法等价类的划分算法74计算机科学与技术学院计算机科
52、学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价关系的定义：等价关系的定义：设R为定义在集合S上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。75计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）对称的。从对称的。从T的序偶表示式中可以看出的序偶表示式中可以看出T是传递的，逐个检查序偶，如是传递的，逐个检查序偶，如 T, T,有有 T;同理，同理， T, T,有有T。故。故T是是R上上的等价关系。同样地，从关系矩阵亦可验证的等价关系。同样地，从关系矩阵亦可验证T是等价关系。是等价关系。76计算机科学与技术学院计算机科学与技
53、术学院数据结构数据结构补充-树的应用：等价类问题（简介）77计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价类的定义：等价类的定义： 设设X为集合为集合S上的上的等价关系等价关系，对任何，对任何x S，由由 xR = y| y s xRy 给出的集合给出的集合xR S 称为由称为由x S生成的一个生成的一个R等价类。等价类。若若R是集合是集合S上的一个等价关系，则由这个等上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以价关系可产生这个集合的唯一划分。即可以按按R将将S划分为若干不相交的子集划分为若干不相交的子集S1,S2,.,它它
54、们的并即为们的并即为S，则这些子集，则这些子集Si便称为便称为S的的R等等价类。价类。78计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价问题等价问题是现实世界中广泛存在的一是现实世界中广泛存在的一种关系，许多应用问题可以归结为种关系，许多应用问题可以归结为按按给定的等价关系给定的等价关系划分划分某集合为某集合为等价类等价类，通常称这类问题为通常称这类问题为等价问题等价问题。79计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）80计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类
55、问题（简介）81计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价关系和等价类的定义等价关系和等价类的定义等价类的划分算法等价类的划分算法82计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）划分等价类的算法划分等价类的算法（P140):假设集合假设集合S有有n个元素，个元素，m个形如个形如(x,y)(x,y S）的等价偶）的等价偶对确定了等价关系对确定了等价关系R，现求，现求S的划分。确定等价类的算的划分。确定等价类的算法如下：法如下：（1）令）令S中每个元素各自形成一个只含单个成员的子集，中每个元素各自形成
56、一个只含单个成员的子集，记着记着S1,S2,.,Sn。（2）重复读入）重复读入m个偶对，对每个偶对（个偶对，对每个偶对（x,y),判定判定x和和y所所属子集。不失一般性，假设属子集。不失一般性，假设x Si,ySj,若若SiSj,则将则将Si并并入入Sj,并置并置Si为空（或将为空（或将Sj并入并入Si,并置并置Sj为空为空)。则当。则当m个个偶对都被处理过后，偶对都被处理过后，S1,S2,.,Sn中所有非空子集即为中所有非空子集即为S的的R等价类。等价类。83计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）等价类的划分算法，需要对集合进行的操作有等价
57、类的划分算法，需要对集合进行的操作有3个：个：（1）是构造只含单个成员的集合；）是构造只含单个成员的集合；（2）是判定某个单元素所在的子集；）是判定某个单元素所在的子集；（3）归并两个互不相交的集合为一个集合。）归并两个互不相交的集合为一个集合。由此，我们需要一个包含这由此，我们需要一个包含这3种操作的抽象数据类型种操作的抽象数据类型MFSet。ADT MFSet 数据对象：若设数据对象：若设S是是MFSet型的集合，则它由型的集合，则它由n(n0)个子集个子集Si(i=1,2,.,n)构成，每个子集的成员都是子界构成，每个子集的成员都是子界-maxnumber.maxnumber内的整数；内
58、的整数；84计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）数据关系数据关系：S1 S2 . Sn=S Si S(i=1,2,.,n)基本操作基本操作： Initial(&S,n,x1,x2,.,xn); /初始化操作。初始化操作。 操作结果：构造一个由操作结果：构造一个由n个子集（每个子集只含单个成员个子集（每个子集只含单个成员xi)构成的集合构成的集合S。 Find(S,x); /S 是已存在的集合，是已存在的集合，x是是S中某个子集的成中某个子集的成员。查找函员。查找函 /数，确定数，确定S中中x所属子集所属子集Si Merge(&S,i,j);
59、 /Si和和Sj是是S中的连个互不相交的非空集合。中的连个互不相交的非空集合。归并操作，将归并操作，将Si和和Sj中的一个并入另一个中。中的一个并入另一个中。ADT MFSet;85计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）ADT MFSet用什么实现？该抽象数据类型以用什么实现？该抽象数据类型以集合集合为基础，为基础，需要实现需要实现3种基本操作，我们可利用种基本操作，我们可利用树型结构表示树型结构表示MFSet。如何表示呢？如何表示呢？约定：约定：以森林以森林F=(T1,T2,.,Tn)表示表示MFSet型的集合型的集合S,森林森林中的每一棵
60、树中的每一棵树Ti(i=1,2,.,n)表示表示S中的一个元素中的一个元素子子集集Si(Si S,i=1,2,.,n),树中每个结点表示子集中的一个树中每个结点表示子集中的一个成员成员x,为操作方便，令每个结点中含有一个指向其双亲为操作方便，令每个结点中含有一个指向其双亲的指针，并约定根结点的成员兼作子集的名称。的指针，并约定根结点的成员兼作子集的名称。86计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）如：子集如：子集S1=1,3,6,9和和S2=(2,8,10)可以用树型结构分别可以用树型结构分别表示如下：表示如下：1369(a)2810(b)87
61、计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）由于各子集的成员均不相同，这种树型结构易于实现查找由于各子集的成员均不相同，这种树型结构易于实现查找和合并操作。和合并操作。1369(a)2810(b)合并1369(c)281088计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）为便于操作的实现，我们采用双亲表示法作为树的存储结为便于操作的实现，我们采用双亲表示法作为树的存储结构。构。typedef PTree MFSet; /MFSet采用树的双亲存储表示采用树的双亲存储表示89计算机科学与技术学院计算机科学与
62、技术学院数据结构数据结构补充-树的应用：等价类问题（简介）查找操作的实现（算法查找操作的实现（算法6.8）：）：int find_mfset(MFSet S,int i) /查找成员查找成员i所属子集所属子集Si的根的根/（根结点成员兼作子集的称）（根结点成员兼作子集的称） if(iS.n) return -1; /i不属于不属于S中任一子集中任一子集 for(j=i;S.nodesj.parent0;j=S.nodesj.parent) ; return j; /find_mfset算法的时间复杂度为算法的时间复杂度为O(h)，h为树的深度。为树的深度。90计算机科学与技术学院计算机科学与技
63、术学院数据结构数据结构补充-树的应用：等价类问题（简介）集合合并操作的实现（算法集合合并操作的实现（算法6.9）：）：Status merge_mfset(MFSet &S,int i,int j) /将将s中两个互不相交的子集中两个互不相交的子集Si和和Sj合并合并(Si并入并入Sj)。/s.nodesi和和s.nodesj分别为子集分别为子集Si和和Sj的根的根 if(iS.n|j1|jS.n) return ERROR;s.nodesi.parent=j; /将将Si并入并入Sj中去中去 return OK; /merge_mfset算法的时间复杂度为算法的时间复杂度为O(1) 。91计
64、算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）集合合并操作的实现（算法集合合并操作的实现（算法6.9）所形成的）所形成的树的深度与树的深度与树的形成过程有关树的形成过程有关。一个极端的例子。一个极端的例子P142-图图6.19树的深度影响了查找操作的复杂度树的深度影响了查找操作的复杂度。为了使生成的树的深度下降，为了使生成的树的深度下降，改进改进的方法：的方法：在在“并并”操作之前，先判断子集中所含成员的数目，操作之前，先判断子集中所含成员的数目，然后然后将成员少的子集根结点指向含成员多的子集的将成员少的子集根结点指向含成员多的子集的根根。为此，相应的
65、存储结构修改为：令为此，相应的存储结构修改为：令根结点的根结点的parent存存储子集中所含成员数目的储子集中所含成员数目的负值负值。92计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介）修改后的合并算法如下修改后的合并算法如下(算法算法6.10)：Status merge_mfset(MFSet &S,int i,int j) /将将s中两个互不相交的子集中两个互不相交的子集Si和和Sj合并合并(?并入并入?)。/s.nodesi和和s.nodesj分别为子集分别为子集Si和和Sj的根的根 if(iS.n|j1|jS.nodesj.parent) /S
66、i所含结点（成员）个数少于所含结点（成员）个数少于Sj所含成员个数所含成员个数 S.nodesj.parent+= S.nodesi.parent ; S.nodesi.parent=j; /将将Si并入并入Sj中去中去/if93计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的应用：等价类问题（简介） else/将将Sj并入并入Si中去中去 S.nodesi.parent+= S.nodesj.parent ; S.nodesj.parent=i; /else return OK; /mix_mfset可以证明，按算法可以证明，按算法6.10进行进行“并并”操作得到的集合树，
67、操作得到的集合树，其深度不超过其深度不超过 log2n+1 ，n为集合为集合S中所有子集中所有子集所含成员的总和。所含成员的总和。94计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例6-1 假设集合假设集合S=x|1x n是正整数是正整数,R是是S上的一个等价关系。上的一个等价关系。R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),.，现求，现求S的等价类。的等价类。123456789n.-1-1-1-1-1-1-1-1-1-1s1s2s3s4s5s6s7s8s9sn95计算机科学与技术学院计算机科学与技术学院数据结构数据结构分别处理各个等价偶
68、对分别处理各个等价偶对(1,2),(3,4),(5,6),(7,8):.21-221-234-2处理偶对处理偶对(1,3)(合并合并s1和和S3)=21-434s1s1s39n56-2s578-2s7s9sn.9n56-2s578-2s7s9sn.96计算机科学与技术学院计算机科学与技术学院数据结构数据结构处理偶对处理偶对(5,7)(合并合并s5和和s7)=21-434s19ns9sn.56-4s57897计算机科学与技术学院计算机科学与技术学院数据结构数据结构处理偶对处理偶对(1,5)(合并合并s1和和s5)=9ns9sn.21-834s15678随着子集的合并，树的深度也越来越大，为了进一
69、步确定元素所在集合的时间，随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，还可以进一步将还可以进一步将算法算法6.8改进改进=算法算法6.11。当所查元素。当所查元素i不在树的第二层时，在算不在树的第二层时，在算法中增加一个法中增加一个“压缩路径压缩路径”的功能，即将所有从根到元素的功能，即将所有从根到元素i路径上的元素都变成树路径上的元素都变成树根的孩子。根的孩子。98计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.1 最优二叉树（赫夫曼树）(1)路径路径：从一个结点到另一个结点所经过的分支。：从一个结点到另一个结点所经过的分支。路径长度路径长度L：路径
70、上分支的数目。：路径上分支的数目。树的路径长度树的路径长度：从树根到每一个结点的路径产度之和。：从树根到每一个结点的路径产度之和。树的带权路径长度树的带权路径长度：树中所有的叶子结点的带权路径长度之和，通常：树中所有的叶子结点的带权路径长度之和，通常记作：记作：6.6 赫夫曼树及其应用AB CD7524CDAB7524C7524ADBWPL=7*2+5*2+2*2+4*2=36WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35WPL=7*1+5*2+2*3+4*3=35
71、99计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.1 最优二叉树（赫夫曼树）(2)哈夫曼树：由权值为w1,w2,.,wn)的n片叶子构成的所有二叉树中，WPL值最小的二叉树。6.6 赫夫曼树及其应用C7524ADBWPL=7*1+5*2+2*3+4*3=35C7524ADBWPL=7*1+5*2+2*3+4*3=351.哈夫曼树不一定是最矮的树2.哈夫曼树形态可能不唯一100计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用最优二叉树（赫夫曼树）赫夫曼树的构造赫夫曼编码101计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.2 赫夫
72、曼树的构造(1)1952年，年，Huffman提出了一个构造最提出了一个构造最优二叉二叉树的一个精巧算法，被人的一个精巧算法，被人们称称为Huffman算法算法 。算法的思想：算法的思想：将权值为将权值为w1, w2, ., wn的的n个叶子构成一个具有个叶子构成一个具有n棵树的森林棵树的森林F；从森林从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和；根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和；重复重复2，直到
73、，直到F中只剩下一棵树为止，这棵树就是所求的中只剩下一棵树为止，这棵树就是所求的Huffman树。树。6.6 赫夫曼树及其应用A7B5C2D46A7B5C2D4611A7B5C2D461118A7B5C2D4102计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.2 赫夫曼树的构造(2)构造构造n个叶子的哈夫曼个叶子的哈夫曼树需要需要经过n-1次合并，每次合并都要增加一个新次合并，每次合并都要增加一个新结点。点。所以所以n个叶子的哈夫曼个叶子的哈夫曼树上有且上有且仅有有2n-1个个结点。点。哈夫曼哈夫曼树上不上不存在度存在度为1的的结点。我点。我们把把这种不存在度种不存在度为1的
74、的结点的二叉点的二叉树称称为严格二叉格二叉树或或正正则二叉二叉树。6.6 赫夫曼树及其应用存储表示：存储表示：typedef struct unsigned int child; unsigned int parent, lchild,rchild;HTNode, *HuffmanTree; 构造算法参见教材（构造算法参见教材（P.147）103计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用最优二叉树（赫夫曼树）赫夫曼树的构造赫夫曼编码104计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(1)6.6 赫夫曼树及其应用 编码编码发
75、送发送 ： 电文电文 0,1 序列序列 (比特流比特流)接收接收： 0, 1序列序列 电文电文 解码解码例如：例如： 电文电文“abcdedacafcfadcacfdaef” 字符集字符集 a, b, c, d, e, f 字符出现次数字符出现次数 6, 1, 5, 4, 2, 4 105计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(2)6.6 赫夫曼树及其应用电文“abcdedacafcfadcacfdaef”字符集 a, b, c, d, e, f 编码方案：abcdef串长特点等长编码等长编码00000101001110010166串长太大不等长编码不等
76、长编码010001101137有多义性前缀码前缀码1011000111011110056好前缀码：任何字符的编码都不是其他字符编码的前缀不等长编码： 010001101101000011001100100.等长编码： 000001010011100011000010000101010000.前缀码： 101100011101111110110011011.106计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(3)6.6 赫夫曼树及其应用A:(0)B:(10)C:(110)D:(111)ABCD010101前缀编码示例如何得到使电文长度最短的二进制前缀编码呢？ 假
77、设每种字符在电文中出现的次数为wi，其编码长度为l，电文中只有n种字符，则电文的总长度为： 对应到二叉树上，若位置wi为叶子结点的权，l为从树根到叶子结点的路径长度，则电文的总长度恰好为二叉树上带权路径长度。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵赫夫曼树的问题。算法的具体实现见教材 P.147,148107计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用typedef struct unsigned int weight; /结点的权重结点的权重 unsigned int parent,lchild,rchild; /双亲、左孩子
78、和右孩子双亲、左孩子和右孩子“指针指针”(数组中的下标）数组中的下标）HTNode,*HuffmanTree; /HuffmanTree HT; 哈夫曼树哈夫曼树HT的类型为一维数组类型，即为指的类型为一维数组类型，即为指/向结点的指针（结构数组名）向结点的指针（结构数组名）-动态分配数组存储哈夫曼树动态分配数组存储哈夫曼树typedef char * HuffmanCode;/ HuffmanCode HC; HCi(i=1n)分别存储第分别存储第i个字符的前缀编个字符的前缀编/码码.HCi为一维字为一维字/ 符数组（名）符数组（名）,一维字符数组的长度为一维字符数组的长度为n（最大（最大/
79、长度，包含一个结束符长度，包含一个结束符0）（各个字符的前缀编码不定长）。）（各个字符的前缀编码不定长）。/HC是一维字符数组的数组（名），其类型为一个是一维字符数组的数组（名），其类型为一个 指向一维字符指向一维字符/数组数组(长度为长度为n)的指针。的指针。char (*HC)n 108计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用构造哈夫曼树，并求哈夫曼编码的算法：构造哈夫曼树，并求哈夫曼编码的算法：void void HuffmanCoding(HuffmanTreeHuffmanCoding(HuffmanTree & &HT,HuffmanCode
80、HT,HuffmanCode& & HC,intHC,int * *w,intw,int n) n)/w/w存放存放n n个字符的权值，即个字符的权值，即w w为一维整型数组名。构造哈夫曼树为一维整型数组名。构造哈夫曼树HT,HT,并求出并求出n n个字个字符的哈夫曼编码符的哈夫曼编码HC.HC.if(nif(n=1) return;=1) return;m=2*n-1;m=2*n-1;/构造出来的哈夫曼树的结点总数为构造出来的哈夫曼树的结点总数为m m，其中叶子结点树为，其中叶子结点树为n n，新增加的，新增加的 /结点（分支结点数目为结点（分支结点数目为n-1).n-1).HT=(Huff
81、manTree)malloc(m+1)*sizeof(HTNodeHT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/HT0);/HT0未用，实际使用未用，实际使用/HT1HTm/HT1HTm存储所构造的哈夫曼树的各个结点。即用动态数组存储哈夫曼树。存储所构造的哈夫曼树的各个结点。即用动态数组存储哈夫曼树。for(pfor(p=HT=HT？, i=1;i=n; i+, p+, +w) *p= *w,0,0,0 ;, i=1;i=n; i+, p+, +w) *p= *w,0,0,0 ;/初始化初始化n n个带权的叶子结点个带权的叶子结点(weight, (w
82、eight, parent,lchildparent,lchild和和rchildrchild值）值）. .若若HT0HT0不不/用的话，则是否应该用的话，则是否应该p=HT+1p=HT+1？for( ; i=m; +i, +p) *p= 0,0,0,0 ;for( ; i=m; +i, +p) *p= 0,0,0,0 ;/初始化其他待生成的新结点（分初始化其他待生成的新结点（分/支结点）支结点）109计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用for(ifor(i=n+1;i=n+1;i=m;im;i+) +) /构造哈夫曼树构造哈夫曼树，分别增加（修正）
83、，分别增加（修正）/HTn+1.2*n-1/HTn+1.2*n-1结点，每次添加（修改）一个。结点，每次添加（修改）一个。SelectHT,i-1,s1,s2; SelectHT,i-1,s1,s2; /在在HT1.i-1HT1.i-1范围内选择范围内选择parentparent为为0 0且且/weight/weight最小的两个结点，其序号分别为最小的两个结点，其序号分别为s1s1和和s2.s2./将将HTs1HTs1和和HTs2HTs2为根的两棵二叉树合并成一棵根为为根的两棵二叉树合并成一棵根为HTiHTi 的二的二/叉树，并修改它们之间的关系。叉树，并修改它们之间的关系。HTs1.par
84、ent=i; HTs2.parent=i; HTs1.parent=i; HTs2.parent=i; /修改修改s1s1和和s2s2的的parentparent值值HTi.lchildHTi.lchild=s1; =s1; HTi.rchildHTi.rchild=s2; =s2; /修改修改HTiHTi 的的lchildlchild和和 /rchildrchild值值HTi.weightHTi.weight=HTs1.weight+HTs2.weight; =HTs1.weight+HTs2.weight; /修改修改HTiHTi 的的 /weight/weight值值 110计算机科学与
85、技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用/求所构造的哈夫曼树中求所构造的哈夫曼树中n n个字符（叶子结点）的哈夫曼编码个字符（叶子结点）的哈夫曼编码从从/叶子到根的逆向求解叶子到根的逆向求解HC=(HuffmanCode)malloc(n+1)*HC=(HuffmanCode)malloc(n+1)*sizeof(charsizeof(char*);*);？/分配存储分配存储n n/个字符的哈夫曼编码的头指向向量（指针数组）。个字符的哈夫曼编码的头指向向量（指针数组）。HC0HC0未用。未用。/HCiHCi （i=1.n)i=1.n)存储第存储第i i个字符的哈夫曼
86、编码。个字符的哈夫曼编码。/ HC=(char(*)n)malloc(n+1/ HC=(char(*)n)malloc(n+1）* *sizeof(charnsizeof(charn););cdcd=(char*)=(char*)malloc(nmalloc(n* *sizeof(charsizeof(char);/cd);/cd存储各个字符编码的临存储各个字符编码的临/时工作空间，时工作空间，cdcd为一维动态字符数组为一维动态字符数组. .cdn-1=cdn-1=00; ; /编码结束标记编码结束标记for(ifor(i=1;i=1;i=n;in;i+) +) /求第求第i i个字符的哈夫
87、曼编码个字符的哈夫曼编码, ,结果存储于结果存储于 /HCiHCi 中。中。 ? ? 111计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用for(ifor(i=1;i=1;i=n;in;i+) +) /求第求第i i个字符的哈夫曼编码个字符的哈夫曼编码, ,结果存储于结果存储于 /HCiHCi 中。中。 start=n-1; start=n-1; for(cfor(c= =i,fi,f= =HTi.parent;fHTi.parent;f!=0;c=!=0;c=f,ff,f= =HTf.parentHTf.parent) ) /从叶子到根逆向求编码从叶子到根逆
88、向求编码 if(HTf.lchildif(HTf.lchild=c) =c) cdcd-start=-start=0 0; ; else else cdcd-start=-start=1 1; ; HCiHCi=(char*)=(char*)malloc(sizeof(charmalloc(sizeof(char);/);/为第为第i i个字符的编码分个字符的编码分 /配存储空间配存储空间HTiHTi ，即，即HCiHCi 存储第存储第i i个字符的哈夫曼编码。个字符的哈夫曼编码。 strcpy(HCi,&cdstartstrcpy(HCi,&cdstart);/);/编码存储在编码存储在cd
89、start.n-1cdstart.n-1中，中， /其中其中cdn-1cdn-1为结束标记为结束标记00 free(cdfree(cd);); /释放工作空间释放工作空间cdcd/HuffmanCodingHuffmanCoding112计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用p148 p148 例例6-2 6-2 写出构造哈夫曼树的过程及写出构造哈夫曼树的过程及8 8个字符的哈夫曼编码。个字符的哈夫曼编码。思考思考：（1 1）哈夫曼树唯一吗？）哈夫曼树唯一吗？（2 2）字符的哈夫曼编码唯一吗？）字符的哈夫曼编码唯一吗？对构造哈夫曼树的算法的一点思考？对构造哈夫曼树的算法的一点思考？（选择（选择s1s1和和s2s2时，如果备选权值中时，如果备选权值中出现两个权值相等出现两个权值相等，该，该选哪一个，选择的不一样是否会影响选哪一个，选择的不一样是否会影响WPLWPL值？值？( (应该会，应该会，p148p148例例6-26-2在选择在选择3 3和和5 5后，出现两个权值后，出现两个权值8 8，该选取哪个该选取哪个8 8与与7 7组合？组合？) )113计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其应用* * 树的计数树的计数 P152P152114
