第6章树二叉树

《第6章树二叉树》由会员分享，可在线阅读，更多相关《第6章树二叉树（114页珍藏版）》请在装配图网上搜索。

1、1第6章 树和二叉树2主要内容6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树和森林6.6 赫夫曼树及其应用36.1 树的定义和基本术语(1) 树（Tree）是n(n 0)个结点的有限集。在任意一棵非空树中: A、有且仅有一个称为根的结点； B、当n 2时，其余结点分为m(m 0) 个互不相交的子集，每个子集本身又是一棵树，称为根的子树。 以上是一个递归的定义在树的定义中又用到了树的概念，由此可见递归是树的固有特性。ABMLKJIHGFEDC46.1 树的定义和基本术语(2)ABMLKJIHGFEDC树根：A 每个子集都是满足树的定义的树，称为A的子树B子

2、树、C子树、D子树。 树根A没有直接前驱；其余结点有且仅有一个直接前驱有，有0个或多个直接后继。三个互不相交的子集： B, E, F, K, L C ,G D, H, I, J, M 树的特征：层次性和分支性56.1 树的定义和基本术语(3)结点的度：结点的非空子树个数树的度：树内各结点度的最大值分支结点(非终端结点) ：度非0的结点叶子结点(终端结点)：度为0的结点孩子：结点的子树的根双亲：孩子的直接前驱结点兄弟：同一个双亲的孩子结点互称为兄弟子孙：以某结点为根的子树中的任一结点祖先：从根到该结点所分支上的所有结点堂兄:双亲在同一层的结点6结点的层次：从根开始定义起，根为第一层，根的孩子为第

3、二层。若某结点在第L层，则其子树的根在第L+1层。树的深度（高度）：结点层次的最大值有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。森林：m（m0）个树的集合ABMLKJIHGFEDCTree = (A ( B ( E ( K , L ), F ), C ( G ), D ( G, H ( M ), I, J ) ) )6.1 树的定义和基本术语(4)7树的基本操作：树的基本操作：构造空树InitTree(&T);销毁树DestroyTree(&T);创建树CreateTree(&T, definition);清空树ClearTree

4、(&T);判断空树TreeEmpty(T);求树的深度TreeDepth(T);求双亲parent(T, cur_e);求长子LeftChild(T, cur_e);求右邻兄弟RightSibling(T, cur_e);插入子树InsertChild(&T, &p, i, c);删除子树DeleteChild(&T, &p, i);遍历树TraverseTree(T, visite();6.1 树的定义和基本术语(5)86.2 二叉树 二叉树的定义 二叉树的性质 二叉树的存储结构96.2.1 二叉树的定义(1)二叉树是另一种树型结构，它的特点是每个结点至多只有两 棵子树(即二叉树中不存在度大

5、于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树可以为空，称为空二叉树;非空二叉树一定有两个子树；左、右子树有次序关系，不能互换；二叉树可以有5种基本形态：二叉树不是结点的度都不超过2的有序树.6.2 二叉树根根左子树右子树根根根根根根106.2.1 二叉树的定义(2) 具有三个结点的树与二叉树6.2 二叉树A、三个结点的树有两种不同的形态B、三个结点的二叉树有五种不同的形态树型结构的共同特征：层次性、分支性116.2.1 二叉树的定义(3)二叉树的基本操作二叉树的基本操作 初始化空二叉树InitBiTree(&T) 销毁二叉树DestroyBiTree(&T) 创建二叉

6、树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) 删除子树DeleteChild(T, p, LR) 先序遍历二叉树PreOrderTraverse(T,visite() 中序遍历二叉树InOrderT

7、raverse(T,visite() 后序遍历二叉树PostOrderTraverse(T,visite() 按层次遍历levelTraverse(T, visite()6.2 二叉树126.2 二叉树 二叉树的定义 二叉树的性质 二叉树的存储结构136.2.2 二叉树的性质(1)性质性质1 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i 1 )；性质性质2 深度为深度为k的二叉树上至多有的二叉树上至多有2k-1个结点个结点(k 1 ) ；性质性质3 设任意一棵二叉树中有设任意一棵二叉树中有n0个度为个度为0的结点，的结点，n2个度为个度为2个结点，则有：个结点，则有：

8、n0 = n2+1；6.2 二叉树满二叉树：一棵深度为k且有 2k1个结点的二叉树。即：所有非终端结点的度都等于2，且所有树叶都分布在同一个层次上。完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进行编号，当且仅当编号与深度为k的满二叉树中前n个结点一一对应。146.2.2 二叉树的性质(2) 性质性质4 完全二叉树的深度为完全二叉树的深度为k log2n +1 或或 k= log2(n+1) ； 性质性质5 将完全二叉树自上而下，自左向右地编号，对将完全二叉树自上而下，自左向右地编号，对任意一结点任意一结点i（1 i n）的结点）的结点X有：有： A、若、若i1，则，则X是根；若

9、是根；若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);266.3.2 遍历二叉树的递归与非递归算法(2) 先序遍历二叉树先序遍历二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKG

10、JIH276.3.2 遍历二叉树的递归与非递归算法(3) 中序遍历二叉树中序遍历二叉树 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则u中序遍历左子树；中序遍历左子树；u访问根；访问根；u中序遍历右子树；中序遍历右子树；6.3 遍历二叉树根根void InOrderTraverse (BiTree T) if (!T) return; InOrderTraverse (T-lchild); visit(T-data);/访根访根 InOrderTraverse (T-rchild);286.3.2 遍历二叉树的递归与非递归算法(4) 中序遍历二叉树 6.3 遍历二叉树ABLKJIHG

11、FEDC ACBEDLFKGJIH296.3.2 遍历二叉树的递归与非递归算法(5) 后序遍历二叉树后序遍历二叉树 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则u后序遍历左子树；后序遍历左子树；u后序遍历右子树；后序遍历右子树；u访问根；访问根；6.3 遍历二叉树根根void PostOrderTraverse (BiTree T) if (!T) return; PostOrderTraverse (T-lchild); PostOrderTraverse (T-rchild); visit(T-data);/访根访根306.3.2 遍历二叉树的递归与非递归算法(6) 先序遍历二

12、叉树先序遍历二叉树 6.3 遍历二叉树ABLKJIHGFEDC ACBEDLFKGJIH316.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); /一直向左走到头，并将所经历的结点入栈一直向左走

13、到头，并将所经历的结点入栈 Pop(s,p); /将空指针退出栈将空指针退出栈S If (!StackEmpty(S) /栈非空时栈非空时 Pop(s,p); /弹出结点弹出结点p If(!visit(p-data) return ERROR; Push(S,p-rchild); /将结点将结点p的右子树入栈的右子树入栈 /if /while/InOrderTraverse6.3 遍历二叉树32例例 已知一棵度为已知一棵度为m的树中有的树中有N1个度为个度为1的结点，的结点，N2个度为个度为2的结点，的结点，.， Nm个度为个度为m的结点，试问该的结点，试问该树中有多少个叶子结点。树中有多少个

14、叶子结点。6.3 遍历二叉树33解答解答:解决此类问题的关键是要把树的结点个数和解决此类问题的关键是要把树的结点个数和树中各结点的度联系起来。树中各结点的度联系起来。设该树中叶子结点个数为设该树中叶子结点个数为N0。则该树结点个数为则该树结点个数为N0+N1+.+Nm=，又该树的结点个数也为，又该树的结点个数也为1+所以所以6.3 遍历二叉树0miiN1miiiN001111,1(1)mmmiiiiiiNNiN NiN 34例例 用一维数组存放的一棵二叉树如下图所示。写出后序遍历该二叉用一维数组存放的一棵二叉树如下图所示。写出后序遍历该二叉树时访问结点的序列。树时访问结点的序列。解答：解答：G

15、HDBEFCA6.3 遍历二叉树ABCDEFGHABCDEFGH35例例 设设m和和n分别为二叉树中的两个结点，问：分别为二叉树中的两个结点，问：（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

16、在在m的前面吗？的前面吗？6.3 遍历二叉树36（1）当）当n在在m的左方，先序遍历时的左方，先序遍历时n在在m的前面吗？中序遍历时的前面吗？中序遍历时n在在m的前面吗？的前面吗？6.3 遍历二叉树mnnm(1)(2)解答：（解答：（1）n在在m的左方可以有上图所示的两种情况。因为先序遍的左方可以有上图所示的两种情况。因为先序遍历为历为“根左右根左右”，因此由上图可知，先序遍历中，因此由上图可知，先序遍历中， n可以在可以在m的前的前面，也可以在面，也可以在m的后面；中序遍历为的后面；中序遍历为“左根右左根右”，由上图可知，中，由上图可知，中序遍历中序遍历中n必在必在m的前面。的前面。37（2

17、）当）当n在在m的右方，中序遍历时的右方，中序遍历时n在在m的前面吗？的前面吗？6.3 遍历二叉树nmmn(1)(2)解答：（解答：（2）中序遍历序列中，）中序遍历序列中，n必在必在m的后面。的后面。38（3）当）当n是是m的祖先，先序遍历时的祖先，先序遍历时n在在m的前面吗？后序遍历时的前面吗？后序遍历时n在在m的前面吗？的前面吗？6.3 遍历二叉树解答：（解答：（3）先序遍历时，祖先必定在子孙的前面；后序遍历时，）先序遍历时，祖先必定在子孙的前面；后序遍历时，祖先必在子孙的后面。（对于中序遍历，左孩子及其子孙必定在祖祖先必在子孙的后面。（对于中序遍历，左孩子及其子孙必定在祖先的前面，而右孩

18、子及其子孙必定在祖先的后面。）先的前面，而右孩子及其子孙必定在祖先的后面。）（4） 当当n是是m的子孙，中序遍历时的子孙，中序遍历时n在在m的前面吗？后序遍历时的前面吗？后序遍历时n在在m的前面吗？的前面吗？解答：由（解答：由（3）可知，中序遍历时，）可知，中序遍历时，n可能在可能在m之前，也可能在之前，也可能在m之之后。而后序遍历时，后。而后序遍历时，n必定在必定在m的前面。的前面。39例例 给定一棵用二叉链表表示的二叉树，每个结点都有给定一棵用二叉链表表示的二叉树，每个结点都有2个个指针（指针（lchild,rchild)，分别用来表示指向其左、右子女，分别用来表示指向其左、右子女，该树的

19、根结点指针为该树的根结点指针为t，试编写一个非递归求二叉树的叶，试编写一个非递归求二叉树的叶子结点数目的算法函数。子结点数目的算法函数。6.3 遍历二叉树40解析：解析：本题是要求编写算法求出二叉链表表示二叉树的叶子结点的本题是要求编写算法求出二叉链表表示二叉树的叶子结点的个数，并且已经给出了该二叉树的基本存储结构，个数，并且已经给出了该二叉树的基本存储结构，注意这里要求用注意这里要求用非递归的方法进行求解非递归的方法进行求解。其实求解二叉树中叶子结点的个数，。其实求解二叉树中叶子结点的个数，可以可以采用非递归的方法进行二叉树的遍历采用非递归的方法进行二叉树的遍历。在遍历的过程中如果遇到了在遍

20、历的过程中如果遇到了叶子结点，则将其统计到叶子结点的个数里面。当遍历完整个二叉叶子结点，则将其统计到叶子结点的个数里面。当遍历完整个二叉树时，也就求出了叶子结点的个数。树时，也就求出了叶子结点的个数。算法的思想是首先定义二叉树算法的思想是首先定义二叉树的二叉链表的存储结构，的二叉链表的存储结构，采用中序遍历二叉树的方法采用中序遍历二叉树的方法。这里用到辅。这里用到辅助栈助栈S，先将根结点入栈，当栈非空时，让指针一直向左走到尽到，先将根结点入栈，当栈非空时，让指针一直向左走到尽到，并将所经历的结点入栈。再将空指针退栈，弹出栈顶结点。若该结并将所经历的结点入栈。再将空指针退栈，弹出栈顶结点。若该结

21、点是叶子结点，则叶子数目变量点是叶子结点，则叶子数目变量count加加1。然后再将该结点的右子。然后再将该结点的右子树入栈，中序遍历完整个二叉树后，函数返回叶子总数树入栈，中序遍历完整个二叉树后，函数返回叶子总数count。6.3 遍历二叉树41答案：答案：二叉树的二叉链表的存储结构：二叉树的二叉链表的存储结构：typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针左右孩子指针BiTNode,*BiTree;int CountLeaf(BiTree t) BiTree p; /定义工作指针定义

22、工作指针p int count=0; /初始化叶子数目变量初始化叶子数目变量count InitStack(S); /建立空栈建立空栈 6.3 遍历二叉树42 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(p

23、-lchild=NULL&p-rchild=NULL) /若结点若结点p为叶子结点为叶子结点 count+; /该二叉树的叶子结点数目加该二叉树的叶子结点数目加1 Push(S,p-rchild); /将结点将结点p的右子树入栈的右子树入栈 /if /whilereturn count; /函数返回叶子结点的数目函数返回叶子结点的数目/CountLeaf6.3 遍历二叉树436.3.2 遍历二叉树递归与非递归算法(8)先序遍历的非递归算法先序遍历的非递归算法(借助堆栈实现借助堆栈实现)void PreOrderTraverse (BiTree bt)if (!bt) return;InitSt

24、ack(S); push(S, bt); /树根的指针进栈树根的指针进栈while (!EmptyStack(S)pop(S, p);while(p) /沿着左链一路向下沿着左链一路向下 visit(p-data); /访问访问 if(p-rchild) push(S,p-rchild); /右孩子进栈右孩子进栈 p=p-lchild; 6.3 遍历二叉树446.3 遍历二叉树 遍历二叉树 遍历二叉树的递归与非递归算法 表达式求值 二叉树的运算举例 层序遍历二叉树456.3.3 表达式求值表达式求值 6.3 遍历二叉树算术表达式中的二叉树表示二元算符右操作数左操作数一元算符右操作数Model

25、：a+b*(c-d)-e/fabcdef+*-/先序遍历得到前缀表达式：- + a * b c d / e f中序遍历得到中缀表达式：a + b * ( c d ) e / f后序遍历得到后缀表达式：a b c d - * + e f / - 466.3 遍历二叉树 遍历二叉树遍历二叉树 遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法 表达式求值表达式求值 二叉树的运算举例二叉树的运算举例 层序遍历二叉树层序遍历二叉树476.3.4 二叉树的运算举例(1)计算二叉树中的结点数计算二叉树中的结点数 Number() 思路：二叉树结点数思路：二叉树结点数1+左子树结点数左子树结点数+右子

26、树结点数右子树结点数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); 48计算二叉树中叶子结点的数目计算二叉树中叶子结点的数目 Leafs() 思路：叶子数左子树叶子数思路：叶子数左子树叶

27、子数+右子树叶子数右子树叶子数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,

28、n); 49例例 已知深度为已知深度为h的二叉树以一维数组的二叉树以一维数组BT(1:2h-1)作为其存储结构，请写一算法，求该二叉树作为其存储结构，请写一算法，求该二叉树中叶结点的个数。中叶结点的个数。6.3 遍历二叉树506.3 遍历二叉树int Leafs(BiTree bt,int h) /层序遍历二叉树，统计叶子结点的个数层序遍历二叉树，统计叶子结点的个数 len=2h-1; count=0;for(i=1;ilen) count+; /i结点没有孩子，结点没有孩子，i结点就是叶子结点结点就是叶子结点 else if(bt2*i+1=0&bt2*i=0) count+; /i结点的左

29、右孩子均为空，结点的左右孩子均为空，i结点就是叶子结点结点就是叶子结点return count;516.3.4 二叉树的运算举例(3) 计算二叉树的深度计算二叉树的深度 Depth() 思路：思路： 深度深度 = max(左子树深度，右子树深度左子树深度，右子树深度) + 16.3 遍历二叉树int Depth(BiTree bt) if(!bt) return 0; hl=Depth(bt-lchild); /计算计算bt的左子树深度的左子树深度 hr=Depth(bt-rchild); /计算计算bt的右子树深度的右子树深度 return (hlhr ? (h1+1):(hr+1) 526

30、.3 遍历二叉树 遍历二叉树遍历二叉树 遍历二叉树的递归与非递归算法遍历二叉树的递归与非递归算法 表达式求值表达式求值 二叉树的运算举例二叉树的运算举例 层序遍历二叉树层序遍历二叉树536.3.5 层序遍历二叉树(1) 自上而下自上而下、自左向右自左向右地遍历二叉树，地遍历二叉树，先被访问结点的孩子先被访问结点的孩子先被访问先被访问。遍历思想为：。遍历思想为：空树空树, 结束。结束。初始化一个空队列初始化一个空队列Q, 树根入队树根入队;队头队头e元素出队元素出队, 访问访问e;如果如果e有左孩子有左孩子, 则左孩子入队则左孩子入队;如果如果e有右孩子有右孩子, 则右孩子入队则右孩子入队;如果

31、队列不空转如果队列不空转3; 否则结束否则结束6.3 遍历二叉树546.3.5 层序遍历二叉树(2) 算法算法 LevelTraverse() void LevelTraverse(BiTree bt) /按层次遍历二叉树算法按层次遍历二叉树算法 if( !bt ) return ; /空树空树 InitQueue(Q); /初始化空队列初始化空队列Q EnQueue(Q, bt); /根入队根入队 while( !EmptyQueue(Q) ) DeQueue(Q, p); /队头队头p出队出队 visit(p-data); /访问访问p if(p-lchild) EnQueue(Q，p-l

32、child); /p的左孩子入队的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入队的右孩子入队 6.3 遍历二叉树556.4 6.4 线索二叉树线索二叉树(1)(1)二叉树的遍历序列是线性序列。在二叉树上找某个结点在某种遍历序二叉树的遍历序列是线性序列。在二叉树上找某个结点在某种遍历序列中的直接前驱或直接后继，只能在对二叉树遍历时动态求得。列中的直接前驱或直接后继，只能在对二叉树遍历时动态求得。如何在遍历过程中保留下结点的前驱和后继的信息呢？最直接的办法如何在遍历过程中保留下结点的前驱和后继的信息呢？最直接的办法也许就是给每个结点增加两个指针。这

33、样做会使得结构的存储密度大也许就是给每个结点增加两个指针。这样做会使得结构的存储密度大大降低。大降低。做如下规定：做如下规定： 若结点有左子树，则其若结点有左子树，则其lchild域指向其左孩子，否则指向其前驱；若域指向其左孩子，否则指向其前驱；若结点有右子树，则其结点有右子树，则其rchild域指向其右孩子，否则指向其后继。域指向其右孩子，否则指向其后继。 其中：其中：6.4 线索二叉树lchildLTagdataRTagrchildLtag = 0 lchild域指向结点的左孩子域指向结点的左孩子 1 lchild域指向结点的前驱域指向结点的前驱Rtag = 0 lchild域指向结点的右

34、孩子域指向结点的右孩子 1 lchild域指向结点的后继域指向结点的后继566.4 6.4 线索二叉树线索二叉树(2)(2)二叉树的二叉线索存储表示二叉树的二叉线索存储表示：6.4 线索二叉树typedef enum PointerTagLink, Thread;typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; /左右标志左右标志BiThrNode, * BiThrTree;中序线索二叉树：13274651327465NULLNULL中序线索二叉树

35、中序线索二叉树576.4 线索二叉树(3)二叉树的二叉线索存储：6.4 线索二叉树1327465NULLNULL中序线索二叉树1 23 5 6 4 7 中序遍历序列中序遍历序列的起始点的起始点中序遍历序列中序遍历序列的终端点的终端点带头结点的中序线索二叉树带头结点的中序线索二叉树?586.4 线索二叉树(4) 线索化，就是在已知二叉链的前提下，填写每个结点左线索线索化，就是在已知二叉链的前提下，填写每个结点左线索LTag域和右线索域和右线索RTag域。域。 若要建立中若要建立中(先、后）序线索，则在中先、后）序线索，则在中(先、后）序遍历过程中先、后）序遍历过程中完成线索化操作。完成线索化操作

36、。 通过中序遍历建立中序线索化链表的算法在教材通过中序遍历建立中序线索化链表的算法在教材P.134,135中。中。 遍历线索二叉树遍历线索二叉树 在线索二叉树中，由于可以直接找到每个结点的后继或前驱，在线索二叉树中，由于可以直接找到每个结点的后继或前驱，所以遍历可以用非递归的方法实现，而且不必借助栈所以遍历可以用非递归的方法实现，而且不必借助栈.(算法算法 P.134)6.4 线索二叉树59 以双向线索链表为二叉树的存储结构时的以双向线索链表为二叉树的存储结构时的中序遍历算法中序遍历算法（6.5）：）：Status InorderTraverse_Thr(BiThree T, Status (

37、*Visit)(TElemType e) /T为头结点指针为头结点指针,中序遍历带头结点的线索二叉树中序遍历带头结点的线索二叉树Tp=T-lchild; /p指向根结点指向根结点while(p!=T) /空树或遍历结束时，空树或遍历结束时，p=T while(p-LTag=link) p=p-lchild; /沿左指针找中序序列第一个结点沿左指针找中序序列第一个结点 if(!Visit(p-data) return ERROR; /访问左子树为空的结点访问左子树为空的结点 while(p-RTag=Thread&p-rchild!=T) p=p-rchild; Visit(p-data); /

38、访问后继结点访问后继结点 p=p-rchild; /若若p有右孩子，则有右孩子，则p指向其右孩子结点，进入指向其右孩子结点，进入while/whilereturn OK;/InorderTraverse_Thr6.4 线索二叉树60 中序遍历建立中序线索化二叉链表的算法（中序遍历建立中序线索化二叉链表的算法（6.6）：）：Status InorderThreading(BiThrTree& Thrt,BiThrTree T)/中序遍历二叉树中序遍历二叉树T，并将其中序线索化，并将其中序线索化，Thrt指向头结点指向头结点 if（！（！（Thrt=new BiThrNode)） exit(OVE

39、RFLOW); Thrt-LTag=Link; Thrt-RTag=Thread; /建立头结点建立头结点 Thrt-rchild=Thrt; /初始时，右指针回指初始时，右指针回指 if(!T) Thrt-lchild=Thrt; /若二叉树为空，则左指针回指若二叉树为空，则左指针回指 else Thrt-lchild=T; pre=Thrt; InThreading(T); /调用函数，中序遍历过程中中序线索化二叉树调用函数，中序遍历过程中中序线索化二叉树T pre-rchild=Thrt;pre-RTag=Thread; /（调用函数后，（调用函数后，pre指向最指向最后一个结点）最后一

40、个结点线索化后一个结点）最后一个结点线索化 Thrt-rchild=pre; /elsereturn OK; /InorderThreading 6.4 线索二叉树61 递归中序线索化二叉树的算法（递归中序线索化二叉树的算法（6.7）：）：void InThreading(BiThrTree& p) if(p) InThread(p-lchild); /左子树线索化左子树线索化 if(!p-lchild) /前驱线索前驱线索 p-LTag=Thread;p-lchild=pre; /if if(!pre-rchild) /后继线索后继线索 pre-RTag=Thread;pre-rchild=

41、p; /if pre=p; /p指向当前结点，指向当前结点，pre指向中序序列中指向中序序列中p的前驱的前驱,开始时开始时 /pre=Thrt, p=T InThreading(p-rchild); /右子树线索化右子树线索化/InThreading/递归函数最底层首先找到中序序列的第一个结点递归函数最底层首先找到中序序列的第一个结点p，对其前驱线索，对其前驱线索，对对pre(此时为头结点指针此时为头结点指针Thrt）进行后继线索，再继续）进行后继线索，再继续6.4 线索二叉树626.5 树和森林 树的存储结构 森林与二叉树的转换 树和森林的遍历636.5.1 树的存储结构(1)双亲表示法6.

42、5 树和森林RAGKFHEDCB1A02B03C00R-14D15E16F37G68H69K6#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int r,n; /根位置和结点数目根位置和结点数目 Ptree;646.5.1 树的存储结构(2)孩子表示法6.5 树和森林RAGKFHEDCBtypedef struct CTNode int child; struct CTNode *next; *Ch

43、ildPtr;typedef struct TElemType data; ChildPtr firstchild;CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; int r,n; /根位置和结点数目根位置和结点数目 CTree;1B 2C03D 0A4R5E 6F7G 8H 9K 53621098-17656.5.1 树的存储结构(1)孩子-兄弟表示法6.5 树和森林RAGKFHEDCBtypedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling;CSN

44、ode, CSTree;firstchilddatanextsiblingKHGFCEBDAR树的孩子兄弟表示可以将树转化为二叉树树的孩子兄弟表示可以将树转化为二叉树666.5 树和森林 树的存储结构 森林与二叉树之间的转换 树和森林的遍历676.5.2 森林和二叉树之间的转换(1)树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以唯一地转换成一棵右子树为空的二叉树。6.5 树和森林ABDECABDEC森林转化为二叉树： 把森林中的每一棵树转换成二叉树； 将所有二叉树的树根用线相连； 以第一棵二叉树的树根为圆心，顺时针转45度。ABDEC686.5.2 森林和二叉树之间的转换(2)6.5

45、树和森林ABDCEFGHJIABDCEFGHJIABDCEFGHJI696.5 树和森林 树的存储结构 森林与二叉树之间的转换 树和森林的遍历706.5.3 树和森林的遍历(1) 先序遍历树先序遍历树：若树不空，则：若树不空，则1. 访问根；访问根；2. 从左至右先序遍历根的各个子树。从左至右先序遍历根的各个子树。6.5 树和森林RAGKFHEDCB后序遍历树后序遍历树：若树不空，则：若树不空，则1. 从左至右后序遍历根的各个子树。从左至右后序遍历根的各个子树。 2. 访问根。访问根。RAGKFHEDCB先根序列：先根序列：RADEBCFGHKRADEBCFGHK后根序列：后根序列：DEABG

46、HKFCRDEABGHKFCR先序序列：先序序列：RADEBCFGHKRADEBCFGHK中序序列：中序序列：DEABGHKFCRDEABGHKFCR后序序列：后序序列：EDKHGFCBAREDKHGFCBAR等价716.5.3 树和森林的遍历(2)先先序遍历树，等价于序遍历树，等价于先先序遍历由这棵树转换而成的二叉树序遍历由这棵树转换而成的二叉树；后后序遍历树，等价于序遍历树，等价于中中序遍历由这棵树转换而成的二叉树序遍历由这棵树转换而成的二叉树；6.5 树和森林先序遍历森林先序遍历森林：若森林不空，则：若森林不空，则1. 访问第一棵树的根结点；访问第一棵树的根结点；2. 先序遍历第一棵树根

47、结点的子树森林；先序遍历第一棵树根结点的子树森林；3. 先序遍历森林中去掉第一棵树后剩下的树构成的森林先序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林中序遍历森林：若森林不空，则：若森林不空，则1. 中序遍历第一棵树根结点的子树森林；中序遍历第一棵树根结点的子树森林；2. 访问第一棵树的根结点；访问第一棵树的根结点； 3. 中序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林中去掉第一棵树后剩下的树构成的森林726.5.3 树和森林的遍历(3)6.5 树和森林ABDCEFGHJIABDCEFGHJI等价先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG先序序列：ABC

48、DEFGHIJ中序序列：BCDAFEHJIG后序序列：DCBFJIHGEA736.6 赫夫曼树及其应用 最优二叉树（赫夫曼树） 赫夫曼树的构造 赫夫曼编码74补充-树的应用：等价类问题（简介） 等价关系和等价类的定义等价关系和等价类的定义 等价类的划分算法等价类的划分算法75补充-树的应用：等价类问题（简介） 等价关系的定义：等价关系的定义：设R为定义在集合S上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。76补充-树的应用：等价类问题（简介）对称的。从对称的。从T的序偶表示式中可以看出的序偶表示式中可以看出T是传递的，逐个检查序偶，如是传递的，逐个检查序偶，如T, T,有有T;

49、同理，同理， T, T,有有T。故。故T是是R上的等价关系。同样地，从关系矩阵亦可验证上的等价关系。同样地，从关系矩阵亦可验证T是等价关系。是等价关系。77补充-树的应用：等价类问题（简介）78补充-树的应用：等价类问题（简介）等价类的定义：等价类的定义： 设设X为集合为集合S上的上的等价关系等价关系，对任何，对任何xS，由由 xR = y| ys xRy 给出的集合给出的集合xR S 称为由称为由x S生成的一个生成的一个R等价类。等价类。若若R是集合是集合S上的一个等价关系，则由这个等上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以价关系可产生这个集合的唯一划分。即可以按

50、按R将将S划分为若干不相交的子集划分为若干不相交的子集S1,S2,.,它它们的并即为们的并即为S，则这些子集，则这些子集Si便称为便称为S的的R等等价类。价类。79补充-树的应用：等价类问题（简介）等价问题等价问题是现实世界中广泛存在的一是现实世界中广泛存在的一种关系，许多应用问题可以归结为种关系，许多应用问题可以归结为按按给定的等价关系给定的等价关系划分划分某集合为某集合为等价类等价类，通常称这类问题为通常称这类问题为等价问题等价问题。80补充-树的应用：等价类问题（简介）81补充-树的应用：等价类问题（简介）82补充-树的应用：等价类问题（简介） 等价关系和等价类的定义等价关系和等价类的定

51、义 等价类的划分算法等价类的划分算法83补充-树的应用：等价类问题（简介） 划分等价类的算法划分等价类的算法（P140):假设集合假设集合S有有n个元素，个元素，m个形如个形如(x,y)(x,yS）的等价偶）的等价偶对确定了等价关系对确定了等价关系R，现求，现求S的划分。确定等价类的算的划分。确定等价类的算法如下：法如下：（1）令）令S中每个元素各自形成一个只含单个成员的子集，中每个元素各自形成一个只含单个成员的子集，记着记着S1,S2,.,Sn。（2）重复读入）重复读入m个偶对，对每个偶对（个偶对，对每个偶对（x,y),判定判定x和和y所所属子集。不失一般性，假设属子集。不失一般性，假设xS

52、i,ySj,若若SiSj,则将则将Si并并入入Sj,并置并置Si为空（或将为空（或将Sj并入并入Si,并置并置Sj为空为空)。则当。则当m个个偶对都被处理过后，偶对都被处理过后，S1,S2,.,Sn中所有非空子集即为中所有非空子集即为S的的R等价类。等价类。84补充-树的应用：等价类问题（简介）等价类的划分算法，需要对集合进行的操作有等价类的划分算法，需要对集合进行的操作有3个：个：（1）是构造只含单个成员的集合；）是构造只含单个成员的集合；（2）是判定某个单元素所在的子集；）是判定某个单元素所在的子集；（3）归并两个互不相交的集合为一个集合。）归并两个互不相交的集合为一个集合。由此，我们需要

53、一个包含这由此，我们需要一个包含这3种操作的抽象数据类型种操作的抽象数据类型MFSet。ADT MFSet 数据对象：若设数据对象：若设S是是MFSet型的集合，则它由型的集合，则它由n(n0)个子集个子集Si(i=1,2,.,n)构成，每个子集的成员都是子界构成，每个子集的成员都是子界-maxnumber.maxnumber内的整数；内的整数；85补充-树的应用：等价类问题（简介）数据关系数据关系：S1S2. Sn=S Si S(i=1,2,.,n)基本操作基本操作： Initial(&S,n,x1,x2,.,xn); /初始化操作。初始化操作。 操作结果：构造一个由操作结果：构造一个由n个

54、子集（每个子集只含单个成个子集（每个子集只含单个成员员xi)构成的集合构成的集合S。 Find(S,x); /S 是已存在的集合，是已存在的集合，x是是S中某个子集的成中某个子集的成员。查找函员。查找函 /数，确定数，确定S中中x所属子集所属子集Si Merge(&S,i,j); /Si和和Sj是是S中的连个互不相交的非空集中的连个互不相交的非空集合。归并操作，将合。归并操作，将Si和和Sj中的一个并入另一个中。中的一个并入另一个中。ADT MFSet;86补充-树的应用：等价类问题（简介）ADT MFSet用什么实现？该抽象数据类型以用什么实现？该抽象数据类型以集合集合为基础，为基础，需要实

55、现需要实现3种基本操作，我们可利用种基本操作，我们可利用树型结构表示树型结构表示MFSet。如何表示呢？如何表示呢？约定：约定：以森林以森林F=(T1,T2,.,Tn)表示表示MFSet型的集合型的集合S,森林森林中的每一棵树中的每一棵树Ti(i=1,2,.,n)表示表示S中的一个元素中的一个元素子子集集Si(Si S,i=1,2,.,n),树中每个结点表示子集中的一树中每个结点表示子集中的一个成员个成员x,为操作方便，令每个结点中含有一个指向其双为操作方便，令每个结点中含有一个指向其双亲的指针，并约定根结点的成员兼作子集的名称。亲的指针，并约定根结点的成员兼作子集的名称。87补充-树的应用：

56、等价类问题（简介）如：子集如：子集S1=1,3,6,9和和S2=(2,8,10)可以用树型结构分别可以用树型结构分别表示如下：表示如下：1369(a)2810(b)88补充-树的应用：等价类问题（简介）由于各子集的成员均不相同，这种树型结构易于实现查找由于各子集的成员均不相同，这种树型结构易于实现查找和合并操作。和合并操作。1369(a)2810(b)合并1369(c)281089补充-树的应用：等价类问题（简介）为便于操作的实现，我们采用双亲表示法作为树的存储结为便于操作的实现，我们采用双亲表示法作为树的存储结构。构。typedef PTree MFSet; /MFSet采用树的双亲存储表示

57、采用树的双亲存储表示90补充-树的应用：等价类问题（简介）查找操作的实现（算法查找操作的实现（算法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为树的深度。为树的深度。91补充-树的应用：等价类问题（简介）

58、集合合并操作的实现（算法集合合并操作的实现（算法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) 。92补充-树的应用：等价类问题（简介）集合合并操作的实现（算法

59、集合合并操作的实现（算法6.9）所形成的）所形成的树的深度与树的深度与树的形成过程有关树的形成过程有关。一个极端的例子。一个极端的例子P142-图图6.19树的深度影响了查找操作的复杂度树的深度影响了查找操作的复杂度。为了使生成的树的深度下降，为了使生成的树的深度下降，改进改进的方法：的方法：在在“并并”操作之前，先判断子集中所含成员的数目，操作之前，先判断子集中所含成员的数目，然后然后将成员少的子集根结点指向含成员多的子集的将成员少的子集根结点指向含成员多的子集的根根。为此，相应的存储结构修改为：令为此，相应的存储结构修改为：令根结点的根结点的parent存存储子集中所含成员数目的储子集中所

60、含成员数目的负值负值。93补充-树的应用：等价类问题（简介）修改后的合并算法如下修改后的合并算法如下(算法算法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) /Si所含结点（成员）个数少于所含结点（成员）个数少于Sj所含成员个数所含成员个数 S.nodesj.parent+= S.nodesi.parent ; S.nodesi

61、.parent=j; /将将Si并入并入Sj中去中去/if94补充-树的应用：等价类问题（简介） else/将将Sj并入并入Si中去中去 S.nodesi.parent+= S.nodesj.parent ; S.nodesj.parent=i; /else return OK; /mix_mfset可以证明，按算法可以证明，按算法6.10进行进行“并并”操作得到的集合树，操作得到的集合树，其深度不超过其深度不超过 log2n+1 ，n为集合为集合S中所有子集中所有子集所含成员的总和。所含成员的总和。95例例6-1 假设集合假设集合S=x|1x n是正整数是正整数,R是是S上的一个等价关系。上

62、的一个等价关系。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-1s1s2s3s4s5s6s7s8s9sn96分别处理各个等价偶对分别处理各个等价偶对(1,2),(3,4),(5,6),(7,8):.21-221-234-2处理偶对处理偶对(1,3)(合并合并s1和和S3)=21-434s1s1s39n56-2s578-2s7s9sn.9n56-2s578-2s7s9sn.97处理偶对处理偶对(5,7)(合并合并s5和和s7)=21-434s19ns9sn.5

63、6-4s57898处理偶对处理偶对(1,5)(合并合并s1和和s5)=9ns9sn.21-834s15678随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，随着子集的合并，树的深度也越来越大，为了进一步确定元素所在集合的时间，还可以进一步将还可以进一步将算法算法6.8改进改进=算法算法6.11。当所查元素。当所查元素i不在树的第二层时，在算不在树的第二层时，在算法中增加一个法中增加一个“压缩路径压缩路径”的功能，即将所有从根到元素的功能，即将所有从根到元素i路径上的元素都变成路径上的元素都变成树根的孩子。树根的孩子。996.6.1 最优二叉树（赫夫曼树）(1)路径路径：从

64、一个结点到另一个结点所经过的分支。：从一个结点到另一个结点所经过的分支。路径长度路径长度L：路径上分支的数目。：路径上分支的数目。树的路径长度树的路径长度：从树根到每一个结点的路径产度之和。：从树根到每一个结点的路径产度之和。树的带权路径长度树的带权路径长度：树中所有的叶子结点的带权路径长度之和，通常：树中所有的叶子结点的带权路径长度之和，通常记作：记作：6.6 赫夫曼树及其应用1nkkkWPLw LAB CD7524CDAB7524C7524ADBWPL=7WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36WPL=7WPL=7* *3+53+5* *3+2

65、3+2* *1+41+4* *2=462=46WPL=7WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=351006.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. 哈夫曼树形态可能不唯一1016.6 赫夫曼树及其应用 最优二叉树（赫夫曼树） 赫夫曼树的构造 赫夫曼编码1026.6.2 赫夫曼树的构造(1

66、) 1952年，年，Huffman提出了一个构造最优二叉树的一个精巧算法，被人们称为提出了一个构造最优二叉树的一个精巧算法，被人们称为Huffman算法算法 。 算法的思想：算法的思想： 将权值为将权值为w1, w2, ., wn的的n个叶子构成一个具有个叶子构成一个具有n棵树的森林棵树的森林F； 从森林从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和；合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和； 重复重复2，直到，直到F中只剩下一棵树为止，这棵树就是所求的中只剩下一棵树为止，这棵树就是所求的Huffman树。树。6.6 赫夫曼树及其应用A7B5C2D46A7B5C2D4611A7B5C2D461118A7B5C2D41036.6.2 赫夫曼树的构造(2)构造构造n个叶子的哈夫曼树需要经过个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。次合并，每次合并都要增加一个新结点。所以所以n个叶