《第6章树和二叉树ppt课件》由会员分享，可在线阅读，更多相关《第6章树和二叉树ppt课件（114页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与技术学院计算机科学与技术学院数据结构数据结构第6章 树和二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构主要内容6.1 树的定义和根本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树和森林6.6 赫夫曼树及其运用计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和根本术语(1)树Tree是n(n 0)个结点的有限集。在恣意一棵非空树中: A、有且仅有一个称为根的结点； B、当n 2时，其他结点分为m(m 0) 个互不相交的子集，每个子集本身又是一棵树，称为根的子树。 以上是一个递归的定义在树的定义中又用到了树的概念，由此可见递归是
2、树的固有特性。ABMLKJIHGFEDC计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和根本术语(2)ABMLKJIHGFEDC树根：A 每个子集都是满足树的定义的树，称为A的子树B子树、C子树、D子树。 树根A没有直接前驱；其他结点有且仅有一个直接前驱有，有0个或多个直接后继。三个互不相交的子集： B, E, F, K, L C ,G D, H, I, J, M 树的特征：层次性和分支性计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.1 树的定义和根本术语(3)结点的度：结点的非空子树个数树的度：树内各结点度的最大值分支结点(非终端结点) ：度非0的结点
3、叶子结点(终端结点)：度为0的结点孩子：结点的子树的根双亲：孩子的直接前驱结点兄弟：同一个双亲的孩子结点互称为兄弟子孙：以某结点为根的子树中的任一结点祖先：从根到该结点所分支上的一切结点堂兄:双亲在同一层的结点计算机科学与技术学院计算机科学与技术学院数据结构数据结构结点的层次：从根开场定义起，根为第一层，根的孩子为第二层。假设某结点在第L层，那么其子树的根在第L+1层。树的深度高度：结点层次的最大值有序树和无序树：假设树中一切结点的的各子树看成是从从至右是有次序的即不能置换，称为有序树，否那么称为无序树。森林：mm0个树的集合ABMLKJIHGFEDCTree = (A ( B ( E ( K
4、 , L ), F ), C ( G ), D ( G, H ( M ), I, J ) ) )6.1 树的定义和根本术语(4)计算机科学与技术学院计算机科学与技术学院数据结构数据结构树的根本操作：树的根本操作：构造空树构造空树InitTree(&T);销毁树销毁树DestroyTree(&T);创建树创建树CreateTree(&T, definition);清空树清空树ClearTree(&T);判别空树判别空树TreeEmpty(T);求树的深度求树的深度TreeDepth(T);求双亲求双亲parent(T, cur_e);求长子求长子LeftChild(T, cur_e);求右邻兄弟
5、求右邻兄弟RightSibling(T, cur_e);插入子树插入子树InsertChild(&T, &p, i, c);删除子树删除子树DeleteChild(&T, &p, i);遍历树遍历树TraverseTree(T, visite();6.1 树的定义和根本术语(5)计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2 二叉树二叉树的定义二叉树的性质二叉树的存储构造计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(1)二叉树是另一种树型构造，它的特点是每个结点至多只需两 棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分
6、，其次序不能恣意颠倒。二叉树可以为空，称为空二叉树;非空二叉树一定有两个子树；左、右子树有次序关系，不能互换；二叉树可以有5种根本形状：二叉树不是结点的度都不超越2的有序树.6.2 二叉树根根左子树右子树根根根根根根计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(2)具有三个结点的树与二叉树6.2 二叉树A、三个结点的树有两种不同的形状B、三个结点的二叉树有五种不同的形状树型构造的共同特征：层次性、分支性计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.1 二叉树的定义(3)二叉二叉树的根本操作的根本操作初始化空二叉初始化空二叉树InitBiTr
7、ee(&T)销毁毁二叉二叉树DestroyBiTree(&T)创建二叉建二叉树CreateBiTree(&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)删除子除子树DeleteCh
8、ild(T, p, LR)先序遍先序遍历二叉二叉树PreOrderTraverse(T,visite()中序遍中序遍历二叉二叉树InOrderTraverse(T,visite()后序遍后序遍历二叉二叉树PostOrderTraverse(T,visite()按按层次遍次遍历levelTraverse(T, visite()6.2 二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2 二叉树二叉树的定义二叉树的性质二叉树的存储构造计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.2 二叉树的性质(1)性性质1 在二叉在二叉树的第的第i层上至多有上至多有2i-1个个
9、结点点(i 1 )；性性质2 深度深度为k的二叉的二叉树上至多有上至多有2k-1个个结点点(k 1 ) ；性性质3 设恣意一棵二叉恣意一棵二叉树中有中有n0个度个度为0的的结点，点，n2个度个度为2个个结点，那么有：点，那么有：n0 = n2+1；6.2 二叉树满二叉树：一棵深度为k且有 2k1个结点的二叉树。即：一切非终端结点的度都等于2，且一切树叶都分布在同一个层次上。完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进展编号，当且仅当编号与深度为k的满二叉树中前n个结点一一对应。计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.2.2 二叉树的性质(2)性性质4 完全
10、二叉完全二叉树的深度的深度为k log2n +1 或或 k= log2(n+1) ；性性质5 将完全二叉将完全二叉树自上而下，自左向右地自上而下，自左向右地编号，号，对恣意一恣意一结点点i1 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
11、);/访根根 PreOrderTraverse (T-lchild); PreOrderTraverse (T-rchild);计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(2)先序遍先序遍历二叉二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(3)中序遍中序遍历二叉二叉树 假假设二叉二叉树为空，那么空操作；否那么空，那么空操作；否那么中序遍中序遍历左子左子树；访问根；根；中序遍中序遍历右子右子树；6.3 遍历二叉树根根
12、void InOrderTraverse (BiTree T) if (!T) return; InOrderTraverse (T-lchild); visit(T-data);/访根根 InOrderTraverse (T-rchild);计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(4)中序遍历二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(5)后序遍后序遍历二叉二叉树 假假设二叉二叉树为空，那么空操作；否那么空
13、，那么空操作；否那么后序遍后序遍历左子左子树；后序遍后序遍历右子右子树；访问根；根；6.3 遍历二叉树根根void PostOrderTraverse (BiTree T) if (!T) return; PostOrderTraverse (T-lchild); PostOrderTraverse (T-rchild); visit(T-data);/访根根计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.2 遍历二叉树的递归与非递归算法(6)先序遍先序遍历二叉二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH计算机科学与技术学院计算机科学与技术学院数
14、据结构数据结构6.3.2 遍历二叉树递归与非递归算法(7)中序遍中序遍历的非的非递归算法算法(借助堆借助堆栈实现)void InOrderTraverse ( BiTree bt, void(*visit)(BiTree) /中序遍中序遍历的非的非递归算法算法 InitStack(S); Push(S,T); While (!StackEmpty(S) /栈非空非空时 While (GetTop(S,p)&P) Push(S,p-lchild); /不断向左走到不断向左走到头，并将所，并将所阅历的的结点点入入栈 Pop(s,p); /将空指将空指针退出退出栈S If (!StackEmpty(
15、S) /栈非空非空时 Pop(s,p); /弹出出结点点p If(!visit(p-data) return ERROR; Push(S,p-rchild); /将将结点点p的右子的右子树入入栈 /if /while/InOrderTraverse6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 知一棵度知一棵度为m的的树中有中有N1个度个度为1的的结点，点，N2个度个度为2的的结点，点，.， Nm个度个度为m的的结点，点，试问该树中有中有多少个叶子多少个叶子结点。点。6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构解答解答:处理此理此类
16、问题的关的关键是要把是要把树的的结点个数和点个数和树中各中各结点的度点的度联络起起来。来。设该树中叶子中叶子结点个数点个数为N0。那么那么该树结点个数点个数为N0+N1+.+Nm=，又，又该树的的结点个数也点个数也为1+所以所以6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 用一用一维数数组存放的一棵二叉存放的一棵二叉树如以下如以下图所示。所示。写出后序遍写出后序遍历该二叉二叉树时访问结点的序列。点的序列。解答：解答：GHDBEFCA6.3 遍历二叉树ABCDEFGHABCDEFGH计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 设m和和n分分别为
17、二叉二叉树中的两个中的两个结点，点，问：1当当n在在m的左方，先序遍的左方，先序遍历时n在在m的前面的前面吗？中序遍？中序遍历时n在在m的前面的前面吗？2当当n在在m的右方，中序遍的右方，中序遍历时n在在m的前面的前面吗？3当当n是是m的祖先，先序遍的祖先，先序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？4当当n是是m的子的子孙，中序遍，中序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构1当当n在在m的左方，先序遍的左方，先序遍历时n在在m的前面的前面吗？中序遍？中序
18、遍历时n在在m的前面的前面吗？6.3 遍历二叉树mnnm(1)(2)解答：解答：1n在在m的左方可以有上的左方可以有上图所示的两种情况。由于先序遍所示的两种情况。由于先序遍历为“根左右，因此由上根左右，因此由上图可知，先序遍可知，先序遍历中，中， n可以在可以在m的前面，的前面，也可以在也可以在m的后面；中序遍的后面；中序遍历为“左根右，由上左根右，由上图可知，中序遍可知，中序遍历中中n必在必在m的前面。的前面。计算机科学与技术学院计算机科学与技术学院数据结构数据结构2当当n在在m的右方，中序遍的右方，中序遍历时n在在m的前面的前面吗？6.3 遍历二叉树nmmn(1)(2)解答：解答：2中序遍
19、中序遍历序列中，序列中，n必在必在m的后面。的后面。计算机科学与技术学院计算机科学与技术学院数据结构数据结构3当当n是是m的祖先，先序遍的祖先，先序遍历时n在在m的前面的前面吗？后序遍？后序遍历时n在在m的前面的前面吗？6.3 遍历二叉树解答：解答：3先序遍先序遍历时，祖先必定在子，祖先必定在子孙的前面；后序遍的前面；后序遍历时，祖先必在子祖先必在子孙的后面。的后面。对于中序遍于中序遍历，左孩子及其子，左孩子及其子孙必定在祖必定在祖先的前面，而右孩子及其子先的前面，而右孩子及其子孙必定在祖先的后面。必定在祖先的后面。4 当当n是是m的子的子孙，中序遍，中序遍历时n在在m的前面的前面吗？后序遍？
20、后序遍历时n在在m的前面的前面吗？解答：由解答：由3可知，中序遍可知，中序遍历时，n能能够在在m之前，也能之前，也能够在在m之之后。而后序遍后。而后序遍历时，n必定在必定在m的前面。的前面。计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 给定一棵用二叉定一棵用二叉链表表示的二叉表表示的二叉树，每，每个个结点都有点都有2个指个指针lchild,rchild)，分，分别用来表示指向其左、右子女，用来表示指向其左、右子女，该树的根的根结点指点指针为t，试编写一个非写一个非递归求二叉求二叉树的的叶子叶子结点数目的算法函数。点数目的算法函数。6.3 遍历二叉树计算机科学与技术学院计算机科学
21、与技术学院数据结构数据结构解析：此解析：此题是要求是要求编写算法求出二叉写算法求出二叉链表表示二表表示二叉叉树的叶子的叶子结点的个数，并且曾点的个数，并且曾经给出了出了该二叉二叉树的根本存的根本存储构造，留意构造，留意这里要求用非里要求用非递归的方的方法法进展求解。其展求解。其实求解二叉求解二叉树中叶子中叶子结点的个数，点的个数，可以采用非可以采用非递归的方法的方法进展二叉展二叉树的遍的遍历。在遍。在遍历的的过程中假程中假设遇到了叶子遇到了叶子结点，那么将其点，那么将其统计到叶子到叶子结点的个数里面。当遍点的个数里面。当遍历完好个二叉完好个二叉树时，也就求出了叶子也就求出了叶子结点的个数。算法
22、的思想是首先点的个数。算法的思想是首先定定义二叉二叉树的二叉的二叉链表的存表的存储构造，采用中序遍构造，采用中序遍历二叉二叉树的方法。的方法。这里用到里用到辅助助栈S，先将根，先将根结点点入入栈，当，当栈非空非空时，让指指针不断向左走到尽到，不断向左走到尽到，并将所并将所阅历的的结点入点入栈。再将空指。再将空指针退退栈，弹出出栈顶结点。假点。假设该结点是叶子点是叶子结点，那么叶子数点，那么叶子数目目变量量count加加1。然后再将。然后再将该结点的右子点的右子树入入栈，中序遍中序遍历完好个二叉完好个二叉树后，函数前往叶子后，函数前往叶子总数数count。6.3 遍历二叉树计算机科学与技术学院计
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 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构 Push(S,t)
24、; /将二叉将二叉树的根的根结点入点入栈 while(!StackEmpty(S) /栈非空非空时 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的右子
25、的右子树入入栈 /if /whilereturn count; /函数前往叶子函数前往叶子结点的数目点的数目/CountLeaf6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构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
26、(p-data); /访问 if(p-rchild) push(S,p-rchild); /右孩子右孩子进栈 p=p-lchild; 6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.3 表达式求值表达式求值 6.3 遍历二叉树算术表达式中的二叉树表示二元算符右操作数左操作数一元算符右操作数Model ：a+b*(c-d)-e/fabcdef+*-/先序遍历得到前缀表达式：- + a * b c d / e f中
27、序遍历得到中缀表达式：a + b * ( c d ) e / f后序遍历得到后缀表达式：a b c d - * + e f / - 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法表达式求值表达式求值二叉树的运算举例二叉树的运算举例层序遍历二叉树层序遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.4 二叉树的运算举例(1)计算二叉树中的结点数计算二叉树中的结点数 Number() 思绪：二叉树结点数思绪：二叉树结点数1+左子树结点数左子树结点数+右子树结点数右子树结点
28、数6.3 遍历二叉树int Number(BiTree 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); 计算机科学与技术学院计算机科学与技术学院数据结构数据结构计算二叉算二叉树中叶子中叶子结点的数目点的数目 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-rc
30、hild, n); 计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例 知深度知深度为h的二叉的二叉树以一以一维数数组BT(1:2h-1)作作为其存其存储构造，构造，请写一算法，求写一算法，求该二叉二叉树中叶中叶结点的个数。点的个数。6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树int Leafs(BiTree bt,int h) /层序遍历二叉树，统计叶子结点的个数层序遍历二叉树，统计叶子结点的个数 len=2h-1; count=0;for(i=1;ilen) count+; /i结点没有孩子，结点没有孩子，i结点就是叶子结点结点就是
31、叶子结点 else if(bt2*i+1=0&bt2*i=0) count+; /i结点的左右孩子均为空，结点的左右孩子均为空，i结点就是叶子结点结点就是叶子结点return count;计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.4 二叉树的运算举例(3)计算二叉算二叉树的深度的深度 Depth() 思思绪： 深度深度 = max(左子左子树深度，右子深度，右子树深度深度) + 16.3 遍历二叉树int Depth(BiTree bt) if(!bt) return 0; hl=Depth(bt-lchild); /计算计算bt的左子树深度的左子树深度 hr=Depth
32、(bt-rchild); /计算计算bt的右子树深度的右子树深度 return (hlhr ? (h1+1):(hr+1) 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3 遍历二叉树遍历二叉树遍历二叉树遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法表达式求值表达式求值二叉树的运算举例二叉树的运算举例层序遍历二叉树层序遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.5 层序遍历二叉树(1)自上而下、自左向右地遍自上而下、自左向右地遍历二叉二叉树，先被，先被访问结点的孩点的孩子先被子先被访问。遍。遍历思想思想为：空空树, 终了。了。初始化一个空初
33、始化一个空队列列Q, 树根入根入队;队头e元素出元素出队, 访问e;假假设e有左孩子有左孩子, 那么左孩子入那么左孩子入队;假假设e有右孩子有右孩子, 那么右孩子入那么右孩子入队;假假设队列不空列不空转3; 否那么否那么终了了6.3 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.3.5 层序遍历二叉树(2)算法算法 LevelTraverse() void LevelTraverse(BiTree bt) /按按层次遍次遍历二叉二叉树算法算法 if( !bt ) return ; /空空树 InitQueue(Q); /初始化空初始化空队列列Q EnQueue(Q, b
34、t); /根入根入队 while( !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 遍历二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 6.4 线索二叉树线索二叉树(1)(1)二叉二叉树的遍的遍历序列是序列是线性序列。在二叉性序列。在二叉树上找某个上找某个结点在某种遍点在某种遍历序序列中的直接前列中的直接
35、前驱或直接后或直接后继，只能在，只能在对二叉二叉树遍遍历时动态求得。求得。如何在遍如何在遍历过程中保管下程中保管下结点的前点的前驱和后和后继的信息呢？最直接的方法的信息呢？最直接的方法也也许就是就是给每个每个结点添加两个指点添加两个指针。这样做会使得构造的存做会使得构造的存储密度大密度大大降低。大降低。做如下做如下规定：定： 假假设结点有左子点有左子树，那么其，那么其lchild域指向其左孩子，否那么指向域指向其左孩子，否那么指向其前其前驱；假；假设结点有右子点有右子树，那么其，那么其rchild域指向其右孩子，否那么指域指向其右孩子，否那么指向其后向其后继。 其中：其中：6.4 线索二叉树l
36、childLTagdataRTagrchildLtag = 0 lchild域指向结点的左孩子域指向结点的左孩子 1 lchild域指向结点的前驱域指向结点的前驱Rtag = 0 lchild域指向结点的右孩子域指向结点的右孩子 1 lchild域指向结点的后继域指向结点的后继计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 6.4 线索二叉树线索二叉树(2)(2)二叉二叉树的二叉的二叉线索存索存储表示：表示：6.4 线索二叉树typedef enum PointerTagLink, Thread;typedef struct BiThrNode TElemType data;
37、struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; /左右左右标志志BiThrNode, * BiThrTree;中序线索二叉树：13274651327465NULLNULL中序线索二叉树中序线索二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.4 线索二叉树(3)二叉树的二叉线索存储：6.4 线索二叉树1327465NULLNULL中序线索二叉树1 23 5 6 4 7 中序遍历序列中序遍历序列的起始点的起始点中序遍历序列中序遍历序列的终端点的终端点带头结点的中序线索二叉树带头结点的中序线索二叉树?计算机科学与技
38、术学院计算机科学与技术学院数据结构数据结构6.4 线索二叉树(4)线索化，就是在知二叉索化，就是在知二叉链的前提下，填写每个的前提下，填写每个结点左点左线索索LTag域和右域和右线索索RTag域。域。假假设要建立中要建立中(先、后序先、后序线索，那么在中索，那么在中(先、后序遍先、后序遍历过程程中完成中完成线索化操作。索化操作。经过中序遍中序遍历建立中序建立中序线索化索化链表的算法在教材表的算法在教材P.134,中。中。遍遍历线索二叉索二叉树 在在线索二叉索二叉树中，由于可以直接找到每个中，由于可以直接找到每个结点的后点的后继或前或前驱，所以遍所以遍历可以用非可以用非递归的方法的方法实现，而且
39、不用借助，而且不用借助栈.(算法算法 P.134)6.4 线索二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构以双向以双向线索索链表表为二叉二叉树的存的存储构造构造时的中序遍的中序遍历算法算法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 线索二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构中序遍中序遍历建立中序建立中序线索化二叉索化二叉链表的算法表的
41、算法6.6：Status 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=
42、Thrt; InThreading(T); /调用函数，中序遍用函数，中序遍历过程中中序程中中序线索化二叉索化二叉树T pre-rchild=Thrt;pre-RTag=Thread; /调用函数后，用函数后，pre指向指向最后一个最后一个结点最后一个点最后一个结点点线索化索化 Thrt-rchild=pre; /elsereturn OK; /InorderThreading 6.4 线索二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构递归中序中序线索化二叉索化二叉树的算法的算法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 线索二叉树计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储构造森林与二叉树的转换树和森林的遍历计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.1 树的存储构造(1)双亲表示法6.5 树和森林RAGKFHEDCB1A02B03C00R-14D15E16F37G68H69K6#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent;PTNode;typedef struct PTNode
45、 nodesMAX_TREE_SIZE; int r,n; /根位置和根位置和结点数目点数目 Ptree;计算机科学与技术学院计算机科学与技术学院数据结构数据结构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-17计算机科学与技术学院计算机科学与技术学院数据结构数据结构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、科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储构造森林与二叉树之间的转换树和森林的遍历计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.2 森林和二叉树之间的转换(1)树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以独一地转换成一棵右子树为空的二叉树。6.5 树和森林ABDECABDEC森林转化为二叉树：把森林中的每一棵树转换成二叉树；将一切二叉树的树根用线相连；以第一棵二叉树的树根为圆心，顺时针转45度。ABDEC计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.2 森林和二叉树之间的转换(2)6.5 树和森林ABDCEFGHJI
48、ABDCEFGHJIABDCEFGHJI计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5 树和森林树的存储构造森林与二叉树之间的转换树和森林的遍历计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.3 树和森林的遍历(1)先序遍历树：假设树不空，那先序遍历树：假设树不空，那么么 访问根；访问根； 从左至右先序遍历根的各个从左至右先序遍历根的各个子树。子树。6.5 树和森林RAGKFHEDCB后序遍历树：假设树不空，那后序遍历树：假设树不空，那么么 从左至右后序遍历根的各个从左至右后序遍历根的各个子树。子树。 访问根。访问根。RAGKFHEDCB先根序列：先根序列：RA
49、DEBCFGHKRADEBCFGHK后根序列：后根序列：DEABGHKFCRDEABGHKFCR先序序列：先序序列：RADEBCFGHKRADEBCFGHK中序序列：中序序列：DEABGHKFCRDEABGHKFCR后序序列：后序序列：EDKHGFCBAREDKHGFCBAR等价计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.3 树和森林的遍历(2)先序遍先序遍历树，等价于先序遍，等价于先序遍历由由这棵棵树转换而成的二叉而成的二叉树；后序遍后序遍历树，等价于中序遍，等价于中序遍历由由这棵棵树转换而成的二叉而成的二叉树；6.5 树和森林先序遍历森林：假设森林不空，那么先序遍历森林
50、：假设森林不空，那么 访问第一棵树的根结点；访问第一棵树的根结点； 先序遍历第一棵树根结点的子树森林；先序遍历第一棵树根结点的子树森林； 先序遍历森林中去掉第一棵树后剩下的树构成的森林先序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林：假设森林不空，那么中序遍历森林：假设森林不空，那么 中序遍历第一棵树根结点的子树森林；中序遍历第一棵树根结点的子树森林； 访问第一棵树的根结点；访问第一棵树的根结点； 中序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林中去掉第一棵树后剩下的树构成的森林计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.5.3 树和森林的遍历(3)6.5
51、树和森林ABDCEFGHJIABDCEFGHJI等价先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG后序序列：DCBFJIHGEA计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用最优二叉树赫夫曼树赫夫曼树的构造赫夫曼编码计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介等价关系和等价类的定义等价关系和等价类的定义等价类的划分算法等价类的划分算法计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介等价关系的定义：等价关系的定
52、义：设R为定义在集合S上的一个关系，假设R是自反的，对称的和传送的，那么R称为等价关系。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介对称的。从对称的。从T的序偶表示式中可以看出的序偶表示式中可以看出T是传送的，逐个检查序偶，如是传送的，逐个检查序偶，如T, T,有有T;同理，同理， T, T,有有T。故。故T是是R上的等价关系。同样地，从关系矩阵亦可验证上的等价关系。同样地，从关系矩阵亦可验证T是等价关系。是等价关系。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介计算机科学与技术学院计算机科学与技术学院数据结构数
53、据结构补充-树的运用：等价类问题简介等价类的定义：等价类的定义： 设设X为集合为集合S上的等价关系，对任何上的等价关系，对任何xS，由由 xR = y| ys xRy 给出的集合给出的集合xR S 称为由称为由x S生成的一个生成的一个R等价类。等价类。假设假设R是集合是集合S上的一个等价关系，那么由这上的一个等价关系，那么由这个等价关系可产生这个集合的独一划分。即个等价关系可产生这个集合的独一划分。即可以按可以按R将将S划分为假设干不相交的子集划分为假设干不相交的子集S1,S2,.,它们的并即为它们的并即为S，那么这些子集，那么这些子集Si便称为便称为S的的R等价类。等价类。计算机科学与技术
54、学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介等价问题是现实世界中广泛存在的一等价问题是现实世界中广泛存在的一种关系，许多运用问题可以归结为按种关系，许多运用问题可以归结为按给定的等价关系划分某集合为等价类，给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。通常称这类问题为等价问题。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介等价关系和等价类的定义等
55、价关系和等价类的定义等价类的划分算法等价类的划分算法计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介划分等价类的算法划分等价类的算法P140):假设集合假设集合S有有n个元素，个元素，m个形如个形如(x,y)(x,yS的等价的等价偶对确定了等价关系偶对确定了等价关系R，现求，现求S的划分。确定等价类的的划分。确定等价类的算法如下：算法如下：1令令S中每个元素各自构成一个只含单个成员的子集，中每个元素各自构成一个只含单个成员的子集，记着记着S1,S2,.,Sn。2反复读入反复读入m个偶对，对每个偶对个偶对，对每个偶对x,y),断定断定x和和y所属子集。不失普
56、通性，假设所属子集。不失普通性，假设xSi,ySj,假设假设SiSj,那那么将么将Si并入并入Sj,并置并置Si为空或将为空或将Sj并入并入Si,并置并置Sj为空为空)。那么当那么当m个偶对都被处置过后，个偶对都被处置过后，S1,S2,.,Sn中一切非中一切非空子集即为空子集即为S的的R等价类。等价类。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介等价类的划分算法，需求对集合进展的操作有等价类的划分算法，需求对集合进展的操作有3个：个：1是构造只含单个成员的集合；是构造只含单个成员的集合；2是断定某个单元素所在的子集；是断定某个单元素所在的子集；3归并两
57、个互不相交的集合为一个集合。归并两个互不相交的集合为一个集合。由此，我们需求一个包含这由此，我们需求一个包含这3种操作的笼统数据类型种操作的笼统数据类型MFSet。ADT MFSet 数据对象：假设设数据对象：假设设S是是MFSet型的集合，那么它由型的集合，那么它由n(n0)个子集个子集Si(i=1,2,.,n)构成，每个子集的成员都是构成，每个子集的成员都是子界子界-maxnumber.maxnumber内的整数；内的整数；计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介数据关系：数据关系：S1S2. Sn=S Si S(i=1,2,.,n)根本操作：
58、根本操作： Initial(&S,n,x1,x2,.,xn); /初始化操作。初始化操作。 操作结果：构造一个由操作结果：构造一个由n个子集每个子集只含单个成员个子集每个子集只含单个成员xi)构成的集合构成的集合S。 Find(S,x); /S 是已存在的集合，是已存在的集合，x是是S中某个子集的成中某个子集的成员。查找函员。查找函 /数，确定数，确定S中中x所属子集所属子集Si Merge(&S,i,j); /Si和和Sj是是S中的连个互不相交的非空集中的连个互不相交的非空集合。归并操作，将合。归并操作，将Si和和Sj中的一个并入另一个中。中的一个并入另一个中。ADT MFSet;计算机科学
59、与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介ADT MFSet用什么实现？该笼统数据类型以集合为根底，用什么实现？该笼统数据类型以集合为根底，需求实现需求实现3种根本操作，我们可利用树型构造表示种根本操作，我们可利用树型构造表示MFSet。如何表示呢？如何表示呢？商定：以森林商定：以森林F=(T1,T2,.,Tn)表示表示MFSet型的集合型的集合S,森林森林中的每一棵树中的每一棵树Ti(i=1,2,.,n)表示表示S中的一个元素中的一个元素子子集集Si(Si S,i=1,2,.,n),树中每个结点表示子集中的一树中每个结点表示子集中的一个成员个成员x,为操作方
60、便，令每个结点中含有一个指向其双为操作方便，令每个结点中含有一个指向其双亲的指针，并商定根结点的成员兼作子集的称号。亲的指针，并商定根结点的成员兼作子集的称号。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介如：子集如：子集S1=1,3,6,9和和S2=(2,8,10)可以用树型构造分别可以用树型构造分别表示如下：表示如下：1369(a)2810(b)计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介由于各子集的成员均不一样，这种树型构造易于实现查找由于各子集的成员均不一样，这种树型构造易于实现查找和合并操作。和合并操作
61、。1369(a)2810(b)合并1369(c)2810计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介为便于操作的实现，我们采用双亲表示法作为树的存储构为便于操作的实现，我们采用双亲表示法作为树的存储构造。造。typedef PTree MFSet; /MFSet采用树的双亲存储表示采用树的双亲存储表示计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介查找操作的实现算法查找操作的实现算法6.8：int find_mfset(MFSet S,int i) /查找成员查找成员i所属子集所属子集Si的根的根/根结点成员兼作子
62、集的称根结点成员兼作子集的称 if(iS.n) return -1; /i不属于不属于S中任一子集中任一子集 for(j=i;S.nodesj.parent0;j=S.nodesj.parent) ; return j; /find_mfset算法的时间复杂度为算法的时间复杂度为O(h)，h为树的深度。为树的深度。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介集合合并操作的实现算法集合合并操作的实现算法6.9：Status merge_mfset(MFSet &S,int i,int j) /将将s中两个互不相交的子集中两个互不相交的子集Si和和Sj合并
63、合并(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) 。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介集合合并操作的实现算法集合合并操作的实现算法6.9所构成的树的深度与所构成的树的深度与树的构成过程有关。一个极端的例子树的构成过程有关。一个极端的例子P142-图图6.19树的深度影响
64、了查找操作的复杂度。树的深度影响了查找操作的复杂度。为了使生成的树的深度下降，改良的方法：为了使生成的树的深度下降，改良的方法：在在“并操作之前，先判别子集中所含成员的数目，并操作之前，先判别子集中所含成员的数目，然后将成员少的子集根结点指向含成员多的子集的然后将成员少的子集根结点指向含成员多的子集的根。根。为此，相应的存储构造修正为：令根结点的为此，相应的存储构造修正为：令根结点的parent存存储子集中所含成员数目的负值。储子集中所含成员数目的负值。计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的运用：等价类问题简介修正后的合并算法如下修正后的合并算法如下(算法算法6.1
65、0)：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) /Si所含结点成员个数少于所含结点成员个数少于Sj所含成员个数所含成员个数 S.nodesj.parent+= S.nodesi.parent ; S.nodesi.parent=j; /将将Si并入并入Sj中去中去/if计算机科学与技术学院计算机科学与技术学院数据结构数据结构补充-树的
66、运用：等价类问题简介 else/将将Sj并入并入Si中去中去 S.nodesi.parent+= S.nodesj.parent ; S.nodesj.parent=i; /else return OK; /mix_mfset可以证明，按算法可以证明，按算法6.10进展进展“并操作得到的集合树，并操作得到的集合树，其深度不超越其深度不超越 log2n+1 ，n为集合为集合S中一切子集中一切子集所含成员的总和。所含成员的总和。计算机科学与技术学院计算机科学与技术学院数据结构数据结构例例6-1 假设集合假设集合S=x|1x n是正整数是正整数,R是是S上的一个等价关系。上的一个等价关系。R=(1,
67、2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),.，现求，现求S的等价类。的等价类。123456789n.-1-1-1-1-1-1-1-1-1-1s1s2s3s4s5s6s7s8s9sn计算机科学与技术学院计算机科学与技术学院数据结构数据结构分别处置各个等价偶对分别处置各个等价偶对(1,2),(3,4),(5,6),(7,8):.21-221-234-2处置偶对处置偶对(1,3)(合并合并s1和和S3)=21-434s1s1s39n56-2s578-2s7s9sn.9n56-2s578-2s7s9sn.计算机科学与技术学院计算机科学与技术学院数据结构数据结构处置偶
68、对处置偶对(5,7)(合并合并s5和和s7)=21-434s19ns9sn.56-4s578计算机科学与技术学院计算机科学与技术学院数据结构数据结构处置偶对处置偶对(1,5)(合并合并s1和和s5)=9ns9sn.21-834s15678随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，还可以进一步将算法还可以进一步将算法6.8改良改良=算法算法6.11。当所查元素。当所查元素i不在树的第二层时，在算不在树的第二层时，在算法中添加一个法中添加一个“紧缩途径的功能，即将一切从根到元素紧缩途径的功能，即将一切
69、从根到元素i途径上的元素都变成树途径上的元素都变成树根的孩子。根的孩子。计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.1 最优二叉树赫夫曼树(1)途径：从一个结点到另一个结点所经过的分支。途径：从一个结点到另一个结点所经过的分支。途径长度途径长度L：途径上分支的数目。：途径上分支的数目。树的途径长度：从树根到每一个结点的途径产度之和。树的途径长度：从树根到每一个结点的途径产度之和。树的带权途径长度：树中一切的叶子结点的带权途径长度之和，通常树的带权途径长度：树中一切的叶子结点的带权途径长度之和，通常记作：记作：6.6 赫夫曼树及其运用AB CD7524CDAB7524C752
70、4ADBWPL=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计算机科学与技术学院计算机科学与技术学院数据结构数据结构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=35
71、1.哈夫曼树不一定是最矮的树2.哈夫曼树形状能够不独一计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用最优二叉树赫夫曼树赫夫曼树的构造赫夫曼编码计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.2 赫夫曼树的构造(1)1952年，年，Huffman提出了一个构造最提出了一个构造最优二叉二叉树的一个精巧算法，被人的一个精巧算法，被人们称称为Huffman算法算法 。算法的思想：算法的思想：将将权值为w1, w2, ., wn的的n个叶子构成一个具有个叶子构成一个具有n棵棵树的森林的森林F；从森林从森林F中中选取根取根权值最小的两棵最小的两棵树，分，分
72、别作作为左子左子树和右子和右子树，再新添一个，再新添一个结点做点做为根，合并成一棵新的二叉根，合并成一棵新的二叉树，新二叉，新二叉树根的根的权值等于左、右子等于左、右子树根根权值之和；之和；反复反复2，直到，直到F中只剩下一棵中只剩下一棵树为止，止，这棵棵树就是所求的就是所求的Huffman树。6.6 赫夫曼树及其运用A7B5C2D46A7B5C2D4611A7B5C2D461118A7B5C2D4计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.2 赫夫曼树的构造(2)构造构造n个叶子的哈夫曼个叶子的哈夫曼树需求需求经过n-1次合并，每次合并都要添加一个新次合并，每次合并都要添
73、加一个新结点。点。所以所以n个叶子的哈夫曼个叶子的哈夫曼树上有且上有且仅有有2n-1个个结点。点。哈夫曼哈夫曼树上不存在度上不存在度为1的的结点。我点。我们把把这种不存在度种不存在度为1的的结点的二叉点的二叉树称称为严厉二叉二叉树或正那么二叉或正那么二叉树。6.6 赫夫曼树及其运用存储表示：存储表示：typedef struct unsigned int child; unsigned int parent, lchild,rchild;HTNode, *HuffmanTree; 构造算法参见教材构造算法参见教材P.147计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树
74、及其运用最优二叉树赫夫曼树赫夫曼树的构造赫夫曼编码计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(1)6.6 赫夫曼树及其运用 编码发送 ： 电文 0,1 序列 (比特流)接纳： 0, 1序列 电文 解码例如： 电文“abcdedacafcfadcacfdaef 字符集 a, b, c, d, e, f 字符出现次数 6, 1, 5, 4, 2, 4 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(2)6.6 赫夫曼树及其运用电文“abcdedacafcfadcacfdaef字符集 a, b, c, d, e, f 编码方案：ab
75、cdef串长特点等长编码等长编码00000101001110010166串长太大不等长编码不等长编码010001101137有多义性前缀码前缀码1011000111011110056好前缀码：任何字符的编码都不是其他字符编码的前缀不等长编码： 010001101101000011001100100.等长编码： 000001010011100011000010000101010000.前缀码： 101100011101111110110011011.计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6.3 赫夫曼编码(3)6.6 赫夫曼树及其运用A:(0)B:(10)C:(110)D:
76、(111)ABCD010101前缀编码例如如何得到使电文长度最短的二进制前缀编码呢？ 假设每种字符在电文中出现的次数为wi，其编码长度为l，电文中只需n种字符，那么电文的总长度为： 对应到二叉树上，假设位置wi为叶子结点的权，l为从树根到叶子结点的途径长度，那么电文的总长度恰好为二叉树上带权途径长度。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵赫夫曼树的问题。算法的详细实现见教材 P.147,148计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用typedef struct unsigned int weight; /结点的权重结点的权
77、重 unsigned int parent,lchild,rchild; /双亲、左孩子和右孩子双亲、左孩子和右孩子“指针指针(数组中的下标数组中的下标HTNode,*HuffmanTree; /HuffmanTree HT; 哈夫曼树哈夫曼树HT的类型为一维数组类型，即为指的类型为一维数组类型，即为指/向结点的指针构造数组名向结点的指针构造数组名-动态分配数组存储哈夫曼树动态分配数组存储哈夫曼树typedef char * HuffmanCode;/ HuffmanCode HC; HCi(i=1n)分别存储第分别存储第i个字符的前缀编个字符的前缀编/码码.HCi为一维字为一维字/ 符数组名
78、符数组名,一维字符数组的长度为一维字符数组的长度为n最大最大/长度，包含一个终了符长度，包含一个终了符0各个字符的前缀编码不定长。各个字符的前缀编码不定长。/HC是一维字符数组的数组名，其类型为一个是一维字符数组的数组名，其类型为一个 指向一维字符指向一维字符/数组数组(长度为长度为n)的指针。的指针。char (*HC)n 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用构造哈夫曼树，并求哈夫曼编码的算法：构造哈夫曼树，并求哈夫曼编码的算法：void HuffmanCoding(HuffmanTree &HT,HuffmanCode& HC,int *w,in
79、t n)void HuffmanCoding(HuffmanTree &HT,HuffmanCode& HC,int *w,int n)/w/w存放存放n n个字符的权值，即个字符的权值，即w w为一维整型数组名。构造哈夫曼树为一维整型数组名。构造哈夫曼树HT,HT,并求出并求出n n个字个字符的哈夫曼编码符的哈夫曼编码HC.HC.if(n=1) return;if(n=1) return;m=2*n-1;/m=2*n-1;/构造出来的哈夫曼树的结点总数为构造出来的哈夫曼树的结点总数为m m，其中叶子结点树为，其中叶子结点树为n n，新添加的，新添加的 /结点分支结点数目为结点分支结点数目为n
80、-1).n-1).HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/HT0HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/HT0未用，实践运用未用，实践运用/HT1HTm/HT1HTm存储所构造的哈夫曼树的各个结点。即用动态数组存储哈夫曼树。存储所构造的哈夫曼树的各个结点。即用动态数组存储哈夫曼树。for(p=HTfor(p=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个带权的叶子结点个带
81、权的叶子结点(weight, parent,lchild(weight, parent,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 ;/初始化其他待生成的新结点分初始化其他待生成的新结点分/支结点支结点计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用for(i=n+1;i=m;i+) /for(i=n+1;i=m;i+) /构造哈夫曼树
82、，分别添加修正构造哈夫曼树，分别添加修正/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的二的二/叉树，并修正它们之间的关系。叉树，并修正它们之间的关系。H
83、Ts1.parent=i; HTs2.parent=i; /HTs1.parent=i; HTs2.parent=i; /修正修正s1s1和和s2s2的的parentparent值值HTi.lchild=s1; HTi.rchild=s2; /HTi.lchild=s1; HTi.rchild=s2; /修正修正HTiHTi的的lchildlchild和和 /rchild /rchild值值HTi.weight=HTs1.weight+HTs2.weight; /HTi.weight=HTs1.weight+HTs2.weight; /修正修正HTiHTi的的 /weight /weight值
84、值 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用/求所构造的哈夫曼树中求所构造的哈夫曼树中n n个字符叶子结点的哈夫曼编码个字符叶子结点的哈夫曼编码从从/叶子到根的逆向求解叶子到根的逆向求解HC=(HuffmanCode)malloc(n+1)*sizeof(char*);HC=(HuffmanCode)malloc(n+1)*sizeof(char*);？/分配存储分配存储n n/个字符的哈夫曼编码的头指向向量指针数组。个字符的哈夫曼编码的头指向向量指针数组。HC0HC0未用。未用。/HCi/HCii=1.n)i=1.n)存储第存储第i i个字符的哈夫曼编
85、码。个字符的哈夫曼编码。/ HC=(char(*)n)malloc(n+1/ HC=(char(*)n)malloc(n+1*sizeof(charn);*sizeof(charn);cd=(char*)malloc(n*sizeof(char);/cdcd=(char*)malloc(n*sizeof(char);/cd存储各个字符编码的临存储各个字符编码的临/时任务空间，时任务空间，cdcd为一维动态字符数组为一维动态字符数组. .cdn-1=0; /cdn-1=0; /编码终了标志编码终了标志for(i=1;i=n;i+) /for(i=1;i=n;i+) /求第求第i i个字符的哈夫曼
86、编码个字符的哈夫曼编码, ,结果存储于结果存储于 /HCi /HCi中。中。 ? ? 计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用for(i=1;i=n;i+) /for(i=1;i=n;i+) /求第求第i i个字符的哈夫曼编码个字符的哈夫曼编码, ,结果存储于结果存储于 /HCi /HCi中。中。 start=n-1; start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / /从叶子到根逆向求编码从叶子到根逆向
87、求编码 if(HTf.lchild=c) cd-start=0; if(HTf.lchild=c) cd-start=0; else cd-start=1; else cd-start=1; HCi=(char*)malloc(sizeof(char);/ HCi=(char*)malloc(sizeof(char);/为第为第i i个字符的编码分个字符的编码分 /配存储空间配存储空间HTiHTi，即，即HCiHCi存储第存储第i i个字符的哈夫曼编码。个字符的哈夫曼编码。 strcpy(HCi,&cdstart);/ strcpy(HCi,&cdstart);/编码存储在编码存储在cdsta
88、rt.n-1cdstart.n-1中，中， / /其中其中cdn-1cdn-1为终了标志为终了标志00 free(cd); / free(cd); /释放任务空间释放任务空间cdcd/HuffmanCoding/HuffmanCoding计算机科学与技术学院计算机科学与技术学院数据结构数据结构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组合？组合？) )计算机科学与技术学院计算机科学与技术学院数据结构数据结构6.6 赫夫曼树及其运用* * 树的计数树的计数 P152 P152
