《树和二叉树下部梁》由会员分享，可在线阅读，更多相关《树和二叉树下部梁（100页珍藏版）》请在金锄头文库上搜索。
1、第第7章树和二叉树章树和二叉树主讲：梁宝兰主讲：梁宝兰教学要求：教学要求：1、理解和掌握：树的定义、术语；树的各种表示方、理解和掌握：树的定义、术语；树的各种表示方式和存储结构；二叉树的定义、性质及其存储方法；式和存储结构；二叉树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的三种遍历算法，能够灵活运用二叉树的遍二叉树的三种遍历算法，能够灵活运用二叉树的遍历方法解决相关的应用问题；哈夫曼树的概念及哈历方法解决相关的应用问题；哈夫曼树的概念及哈夫曼编码。夫曼编码。2、了解：二叉树的分步遍历；二叉树的线索化方法；、了解：
2、二叉树的分步遍历；二叉树的线索化方法；树与二叉树的转换；树的遍历。树与二叉树的转换；树的遍历。第第7章树和二叉树章树和二叉树2内容提要内容提要树的逻辑结构树的逻辑结构树的存储结构树的存储结构二叉树的逻辑结构二叉树的逻辑结构二叉树的存储结构及实现二叉树的存储结构及实现哈夫曼树哈夫曼树树、森林与二叉树的转换树、森林与二叉树的转换本章的主要内容是本章的主要内容是37.3 7.3 以结点类为基础的二叉树设计以结点类为基础的二叉树设计二叉树类定义：二叉树类定义：首先设计二叉树结点类首先设计二叉树结点类然后在二叉树结点类的基础上，再设计二叉树类然后在二叉树结点类的基础上，再设计二叉树类4class Nod
3、e friend class BTree;private: ElemType data;/数据元素值数据元素值 Node *lChild;/左子树指针左子树指针 Node *rChild;/右子树指针右子树指针public: Node() lChild = NULL; rChild = NULL; Node( ElemType item, Node *left = NULL,Node *right = NULL ) data = item; lChild = left; rChild = right; Node();/二叉树的结点类的定义二叉树的结点类的定义5class BTree priva
4、te: Node* root;public: BTree(); /构造函数构造函数 void Create(int No,char data,int n); /创建二叉树创建二叉树 void PreOrder(Node* r, void Visit(Node*); /先序遍历先序遍历 void InOrder(Node* r, void Visit(Node*); /中序遍历中序遍历 void PostOrder( Node* r, void Visit(Node*); /后序遍历后序遍历 void BTree:LevelOrder(Node* r, void Visit(Node*) Nod
5、e* getRoot(); /获取根结点指针获取根结点指针;/二叉树类的定义二叉树类的定义6构造函数：创建一个空二叉树构造函数：创建一个空二叉树获取二叉树根结点指针获取二叉树根结点指针BTree:BTree()root=NULL;Node*BTree:getRoot()returnroot;7为了后面遍历二叉树方便，先介绍建立二叉链表的为了后面遍历二叉树方便，先介绍建立二叉链表的算法。算法。方法方法1：利用二叉树中结点对应与满二叉树中：利用二叉树中结点对应与满二叉树中的层序编号进行构造：的层序编号进行构造：BACD012552100 1 2 3NoDCBA0 1 2 3data二叉链表的建立二
6、叉链表的建立8AB C D s012345652100 1 2 3NoDCBA0 1 2 3data9voidBTree:Create(intNo,chardata,intn)Node*sMaxSize;/二叉树结点指针数组二叉树结点指针数组Node*q;inti,j;for(i=0;ilChild=q;elsesj-rChild=q;二叉树类二叉树类(基本基本)10方法方法2：利用二叉树的合并，从叶子结点开始：利用二叉树的合并，从叶子结点开始构建二叉树构建二叉树二叉链表的建立二叉链表的建立AB C D 11/二叉树的合并二叉树的合并void MakeTree(const T& element
7、, BinaryTree& left, BinaryTree& right) root = new Node(element,left.root, right.root);left.root = right.root = 0;void main()BinaryTree a, b, c, d, null; /构造构造5棵空二叉树棵空二叉树d.MakeTree(D, null, null);c.MakeTree(C, d, null);b.MakeTree(B, null, null);a.MakeTree(A, b, c);12二叉树的遍历方式：二叉树的遍历方式：DLR、DRL、LDR、LRD、
8、RDL、RLD如果限定先左后右，则二叉树遍历方式有四种：如果限定先左后右，则二叉树遍历方式有四种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树7.3.2二叉树的遍历二叉树的遍历137.3.2 7.3.2 二叉树的遍历二叉树的遍历二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅
9、被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化抽象操作，可以是对结点进行的各种抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。处理，这里简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历14前序（根）遍历前序（根）遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序遍历遍历根根结点的右子树。结点的右子树。前序遍历序列：前序遍历序列：A B D G C E FABCDEFG7.3.2二叉树的遍历二叉
10、树的遍历15前序（根）遍历过程：前序（根）遍历过程：ABCDEFG7.3.2二叉树的遍历二叉树的遍历ABF根 左子树右子树DGCE16若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。中序遍历序列：中序遍历序列：D G B A E C F中序（根）遍中序（根）遍中序（根）遍中序（根）遍历历历历7.3.2二叉树的遍历二叉树的遍历ABCDEFG17若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序
11、遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；后序遍历序列：后序遍历序列：G D B E F C A后序（根）遍历后序（根）遍历后序（根）遍历后序（根）遍历7.3.2二叉树的遍历二叉树的遍历ABCDEFG18二二叉叉树树的的层层次次遍遍历历是是指指从从二二叉叉树树的的第第0层层（即即根根结结点点）开开始始，从从上上至至下下逐逐层层遍遍历历，在在同同一一层层中中，则则按按从从左左到到右右的顺序对结点逐个访问。的顺序对结点逐个访问。层序遍历序列：层序遍历序列：A B C D E F G7.3.2二叉树的遍历二叉树的遍历ABCDEFG层序遍历层序遍历层序遍历层序遍历19-/+*ab
12、cdef二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：-+a*b-cd/ef中序遍历结果：中序遍历结果：a+b*c-d-e/f后序遍历结果：后序遍历结果：abcd-*+ef/-层序遍历结果：层序遍历结果：-+/a*efb-cd7.3.2二叉树的遍历二叉树的遍历20若已知一棵二叉树的前序（或中序，或后序，或若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为例：已知前序序列为ABC，则与之对应的二叉树为：，则与之对应的二叉树为：ABC7.3.2二叉树的遍历二叉树的遍历ABCACBACB21
13、例：已知前序遍历序列为例：已知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为CBA，则下列二叉树都满足条件。，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？唯一确定这棵二叉树呢？7.3.2二叉树的遍历二叉树的遍历22若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？唯一确定这棵二叉树呢？例：已知一棵二叉树的前序遍历序列和中序遍历序例：已知一棵二叉树的前序遍历序列和中序遍历序列分别为列分别为ABCDEFGHI和和BCAEDGHFI，如何构造
14、如何构造该二叉树呢该二叉树呢? ?7.3.2二叉树的遍历二叉树的遍历怎样确定？怎样确定？23前序：前序：ABCDEFGHI中序：中序：BCAEDGHFI前序：前序：BC中序：中序：BCBCDEFGHIA前序：前序：DEFGHI中序：中序：EDGHFIABCDEFGHI7.3.2二叉树的遍历二叉树的遍历24前序：前序：FGHI中序：中序：GHFI前序：前序：DEFGHI中序：中序：EDGHFIABCDEFGHIABCDEFIGH7.3.2二叉树的遍历二叉树的遍历25练习练习1、现有一棵二叉、现有一棵二叉树的仿真指针表树的仿真指针表如下所示，请写如下所示，请写出该二叉树的先出该二叉树的先序，中序，
15、后序序，中序，后序,层序遍历的序列。层序遍历的序列。data lchild rchild0A121B3-12C453D-1-14E-165F7-16G-1-17H898I-1-19J-1-126练习练习2、现有一棵二叉树的先序遍历和中序遍历的、现有一棵二叉树的先序遍历和中序遍历的序列分别为：序列分别为： 先序：先序：A,B,C,D,F,E,G,H 中序：中序：B,D,F,C,G,E,H,A 请以图示表示方式画出该二叉树。请以图示表示方式画出该二叉树。27/二叉树先序遍历递归算法二叉树先序遍历递归算法voidPreOrder(Node*r)if(r!=NULL)coutdatalChild);/
16、遍历左子树遍历左子树PreOrder(r-rChild);/遍历右子树遍历右子树7.3.2二叉树的遍历二叉树的遍历28/二叉树先序遍历二叉树先序遍历递归算法递归算法 void BTree:PreOrder(Node* r,void Visit(Node*) if(r!=NULL) Visit(r); PreOrder(r-lChild,Visit); PreOrder(r-rChild,Visit); 7.3.2二叉树的遍历二叉树的遍历怎样消去递归？怎样消去递归？29BACEDGFroot前序遍历序列：前序遍历序列：A的左右子树均不空，的左右子树均不空，访问访问A后应该访问左后应该访问左子树的
17、所有节点，然子树的所有节点，然后再访问右子树的所后再访问右子树的所有节点。有节点。访问完访问完A的左子树后，的左子树后，怎样知道怎样知道A的右子树的右子树在哪里？在哪里？7.3.2二叉树的遍历二叉树的遍历/二叉树先序遍历的二叉树先序遍历的非递归过程非递归过程30BACEDGFroot前序遍历序列：前序遍历序列： Aroot: C31BACEDGFrootroot: B前序遍历序列：前序遍历序列： A Broot: Eroot: C32BACEDGFrootroot: Eroot: C前序遍历序列：前序遍历序列： A B D D的右子树为空，的右子树为空，不需要进栈，左不需要进栈，左子树为空，弹
18、栈子树为空，弹栈访问下一个元素访问下一个元素33E EBACDGFrootroot: C前序遍历序列：前序遍历序列： A B D EE的右子树为的右子树为空，不需要进空，不需要进栈栈34CBACEDGFrootroot: C前序遍历序列：前序遍历序列： A B D EGG的右子树为空，的右子树为空，不需要进栈，左不需要进栈，左子树为空，弹栈子树为空，弹栈访问下一个元素访问下一个元素35CBACEDGFrootroot: F前序遍历序列：前序遍历序列： A B D EG CC的右子树不的右子树不空，进栈；空，进栈；36FBACEDGFroot前序遍历序列：前序遍历序列： A B D EG CFC
19、的左子树空，的左子树空，弹栈访问下一弹栈访问下一个元素个元素37FBACEDGFroot前序遍历序列：前序遍历序列： A B D EG CFF的左子树为空，的左子树为空，且栈为空，遍且栈为空，遍历完毕！历完毕！38BACEDGFroot前序遍历序列：前序遍历序列： A B D EG CF397.3.2二叉树的遍历二叉树的遍历/二叉树先序遍历的二叉树先序遍历的非递归算法非递归算法算法思想：算法思想：1.指针指向树的根结点指针指向树的根结点2.指针不为空，访问指针指向的结点，转指针不为空，访问指针指向的结点，转3；否则转；否则转5；3.若有右孩子，则把右孩子结点压栈；若有右孩子，则把右孩子结点压栈
20、；4.若有左孩子，则指针指向左孩子，转若有左孩子，则指针指向左孩子，转2；否则，若栈非空，则指针指向弹栈结点；否则，若栈非空，则指针指向弹栈结点；栈空则指针指向空；栈空则指针指向空；5.结束结束40/二叉树先序遍历的非递归算法二叉树先序遍历的非递归算法 stack mystack;while(r!=NULL)Visit(r); if(r-rChild !=NULL)mystack.push(r-rChild );if(r-lChild !=NULL)r=r-lChild;else if(mystack.empty() =0) r=mystack.top(); mystack.pop (); e
21、lse r=NULL; 41中序遍历（中序遍历（LDR）递归算法为：递归算法为：若二叉树为空则算法结束；否则：若二叉树为空则算法结束；否则：（1）中序遍历根结点的左子树；）中序遍历根结点的左子树；（2）访问根结点；）访问根结点；（3）中序遍历根结点的右子树。）中序遍历根结点的右子树。7.3.2二叉树的遍历二叉树的遍历42/二叉树中序遍历二叉树中序遍历 递归算法递归算法 void BTree:InOrder(Node* r) if(r!=NULL) InOrder(r-lChild); coutdatarChild); 43/二叉树中序遍历二叉树中序遍历 递归算法递归算法 void BTree:
22、InOrder(Node* r,void Visit(Node*) if(r!=NULL) InOrder(r-lChild,Visit); Visit(r); InOrder(r-rChild,Visit); 44中序遍历非递归算法中序遍历非递归算法算法思想为：算法思想为：从从二二叉叉树树根根结结点点开开始始，沿沿左左子子树树一一直直走走到到末末端端（左左孩孩子子为为空空）为为止止，在在走走的的过过程程中中，把把依依次次遇遇到到的的结结点点进进栈栈，待待左左子子树树为为空空时时，从从栈栈中中退退出出结结点点并并访访问问，然然后后再再转转向向它它的的右右子子树树。如如此此重重复复，直直到到栈栈
23、空或指针为空止。空或指针为空止。7.3.2二叉树的遍历二叉树的遍历45/中序遍历非递归算法中序遍历非递归算法voidBTree:InOrder1(Node*r,vodVisit(Node*)Node*p,*s100;/s为一个栈，为一个栈，top为栈顶指针为栈顶指针inttop=0;p=r;while(p!=NULL)|(top0)while(p!=NULL)s+top=p;p=p-lchild;p=stop-;Visit(p);p=p-rchild;46后序遍历（后序遍历（LRD）递归算法为：递归算法为：若二叉树为空则算法结束；否则：若二叉树为空则算法结束；否则：（1）后序遍历根结点的左子树
24、；）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；）后序遍历根结点的右子树；（3）访问根结点。）访问根结点。7.3.2二叉树的遍历二叉树的遍历47/二叉树后序遍历递归算法二叉树后序遍历递归算法 void BTree:PostOrder(Node* r) if(r!=NULL) PostOrder(r-lChild); PostOrder(r-rChild); coutdatalChild,Visit); PostOrder(rt-rChild,Visit); Visit(r); 49后序遍历非递归算法后序遍历非递归算法算法思想为：算法思想为：搜搜索索指指针针指指向向某某一一个个结结点点
25、时时，先先要要遍遍历历左左子子树树，此此结结点点应应先先进进栈栈保保存存，遍遍历历完完它它的的左左子子树树后后，再再次次回回到到该该结结点点，该该结结点点再再次次进进栈栈（遍遍历历其其右右子子树树），右子树遍历完后，再次退栈时，访问该结点。右子树遍历完后，再次退栈时，访问该结点。为为了了区区分分同同一一结结点点的的两两次次进进栈栈，引引入入一一个个栈栈次次数数的的标标志志，一一个个元元素素第第一一次次进进栈栈标标志志为为0，第第二二次次进进标标志志为为1，并并将将标标志志存存入入另另一一个个栈栈中中，当当从从标标志志栈栈中中退退出的元素为出的元素为1时，访问结点。时，访问结点。7.3.2二叉树
26、的遍历二叉树的遍历50voidBTree:PostOrder1(Node*r,voidVisit(Node*)Node*p,*s1100;/s1栈存放树中结点栈存放树中结点ints2100,top=0,b;/s2栈存放进栈标志栈存放进栈标志p=r;dowhile(p!=NULL)s1top=p;s2top+=0;/第一次进栈标志为第一次进栈标志为0p=p-lchild;if(top0)b=s2-top;p=s1top;if(b=0)s1top=p;s2top+=1;/第二次进栈标志为第二次进栈标志为0p=p-rchild;elseVisit(p);p=NULL;while(top0);51 层
27、序遍历算法层序遍历算法层序遍历算法思想：在所有未被访问结点的集合中，层序遍历算法思想：在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。以借助队列实现
28、二叉树的层序遍历。7.3.2二叉树的遍历二叉树的遍历52 层序遍历算法层序遍历算法（1 1）初始化设置一个队列（结点指针类型）；）初始化设置一个队列（结点指针类型）；（2 2）把根结点指针入队列；）把根结点指针入队列；（3 3）当队列非空时，循环执行步骤（）当队列非空时，循环执行步骤（3.a3.a）到步骤到步骤（3.c3.c）；）；（3.a3.a）出队列取得一个结点指针，访问该结点；出队列取得一个结点指针，访问该结点；（3.b3.b）若该结点的左子树非空，则将该结点的左子若该结点的左子树非空，则将该结点的左子树指针入队列；树指针入队列；（3.c3.c）若该结点的右子树非空，则将该结点的右子若该
29、结点的右子树非空，则将该结点的右子树指针入队列；树指针入队列；（4 4）结束。）结束。7.3.2二叉树的遍历二叉树的遍历53/层序遍历层序遍历 void BTree:LevelOrder(void Visit(Node*) Node* qMaxSize; Node* t; int front=0,rear=0; if(root!=NULL) q+rear = root; while (front!=rear) front+; t = qfront; Visit(t); if(t-lChild!=NULL) q+rear = t-lChild; if(t-rChild!=NULL) q+rear
30、 = t-rChild; 54二叉树遍历的应用二叉树遍历的应用(1)二叉树的撤消操作二叉树的撤消操作 在释放某个结点的存储空间前必须先释放该在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作函数实现如下：序遍历的具体应用。撤消操作函数实现如下：7.3.2二叉树的遍历二叉树的遍历55void BTree:Destroy(Node *r) if(r =NULL) return; else if(r-lChild != NULL) De
31、stroy(r-lChild); if(r-rChild != NULL) Destroy(r-rChild); cout data rChild第第level+1层结点数据域值的横向显示层结点数据域值的横向显示Print(r-rChild , level+1); if(level != 0) /走过走过6*(level-1)个空格个空格for(int i = 0; i 6*(level-1); i+) cout ;cout -;cout data lChild第第level+1层结点数据域值的横向显示层结点数据域值的横向显示Print(r-lChild, level+1); 58应用举例应用
32、举例 例例7-1 编写一个程序，首先建立如图编写一个程序，首先建立如图7-10(a)所示的不带头结点的二叉链存储结构的二叉所示的不带头结点的二叉链存储结构的二叉树，然后打印该二叉树并分别输出按照前序树，然后打印该二叉树并分别输出按照前序遍历二叉树次序、中序遍历二叉树次序和后遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序访问各结点的序列信息，序遍历二叉树次序访问各结点的序列信息，最后再测试查找函数和撤消函数的正确性。最后再测试查找函数和撤消函数的正确性。二叉树类二叉树类(提高提高)59*7.6 线索二叉树线索二叉树对二叉链存储结构的二叉树分析可知，在有对二叉链存储结构的二叉树分析可知，在
33、有n个结个结点的二叉树中必定存在点的二叉树中必定存在n+1个空链域。个空链域。二叉树本身是非线性结构，但通过某种遍历方法二叉树本身是非线性结构，但通过某种遍历方法遍历得到的结点序列却是线性的。遍历得到的结点序列却是线性的。当按某种规则遍历二叉树时，保存遍历时得到的当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。方法是建立线索二叉树。下面讨论建立线索二叉树的方法：下面讨论建立线索二叉树的方法：60当某结点的左指针为空时，令该指针指向按某种方法遍历二当某结点的左指针为空时，令该指针指向按某种方法遍历
34、二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。结点。问题：如何区分左指针指向的结点到底是左孩子结点还是前问题：如何区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。驱结点，右指针指向的结点到底是右孩子结点还是后继结点。解决方法：在结点中增加两个线索标志位来区分这两种情况。解决方法：在结点中增加两个线索标志位来区分这两种情况。线索标志位定义如下：线索标志位定义如下：61每个结点的
35、结构就如下所示：每个结点的结构就如下所示：LChildLThreaddataRThreadRChild 结点中指向前驱结点和后继结点的指针称为线索。结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。进行的线索化。 62ADGECFB63AB C D E F G 640 A 00 B 10 C 01 D 01 E
36、 11 F 11 G 101中序线索化中序线索化65中序线索二叉树中中序线索二叉树中查找结点的后继和前驱查找结点的后继和前驱:如何在中序线索二叉树中找结点的后继：如何在中序线索二叉树中找结点的后继：RThread=1时，时，Rchild所指的结点即为后继；所指的结点即为后继；RThread=0时时，其其后后继继为为遍遍历历其其右右子子树树时时的的第第一个结点（最左下结点）。一个结点（最左下结点）。如何在中序线索二叉树中找结点的前驱：如何在中序线索二叉树中找结点的前驱：LThread=1时，时，Lchild所指的结点即为前驱；所指的结点即为前驱；LThread=0时时，其其前前驱驱为为遍遍历历其
37、其左左子子树树时时的的最最后一个结点（最右下结点）。后一个结点（最右下结点）。667.7 哈夫曼哈夫曼(Huffman)树树一、哈夫曼树的基本概念一、哈夫曼树的基本概念从从A结点到结点到B结点所经过的分支序列叫做从结点所经过的分支序列叫做从A结点结点到到B结点的路径；结点的路径；从从A结点到结点到B结点所经过的分支个数叫做从结点所经过的分支个数叫做从A结点结点到到B结点的路径长度；结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。长度之和称作该二叉树的路径长度。67 设二叉树有设二叉树有n个带权值的叶结点，定义从
38、二叉树的个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度结点权值的乘积之和称作该二叉树的带权路径长度（WPL），），即：即： 其中，其中，wi为第为第i i个叶结点的权值，个叶结点的权值，li为从根结点到为从根结点到第第i个叶结点的路径长度。个叶结点的路径长度。 7.7 哈夫曼哈夫曼(Huffman)树树68哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带权结点，带权路径路径长度最小的二叉树长度最小的二叉树。例：给定例：给定4个叶子结点，其权值分别
39、为个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的可以构造出形状不同的多个二叉树。多个二叉树。WPL=32WPL=41WPL=302347234774237.7 哈夫曼哈夫曼(Huffman)树树69WPL=32WPL=41WPL=302347234774237.7 哈夫曼哈夫曼(Huffman)树树哈夫曼树的特点：哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。叶子结点越远离根结点。2.只有度为只有度为0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结（分支结点）的结点，不存在度为点，不存在度
40、为1的结点。（反证法）的结点。（反证法）707.7 哈夫曼哈夫曼(Huffman)树树哈夫曼算法基本思想：哈夫曼算法基本思想：初始化初始化：由给定的：由给定的n个权值个权值w1，w2，wn构造构造n棵只有一个根结点的二叉树，从而得到一个二叉树棵只有一个根结点的二叉树，从而得到一个二叉树集合集合FT1，T2，Tn；选取与合并选取与合并：在：在F中选取根结点的权值中选取根结点的权值最小最小的两棵的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；权值之
41、和；删除与加入删除与加入：在：在F中删除作为左、右子树的两棵二中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到叉树，并将新建立的二叉树加入到F中；中；重复重复、两步，当集合两步，当集合F中只剩下一棵二叉树时，中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。这棵二叉树便是哈夫曼树。 讲解图讲解图7-1571第第1步：初始化步：初始化W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程3524第第2步：选取与合并步：选取与合并325第第3步：删除与加入步：删除与加入543257.7 哈夫曼哈夫曼(Huffman)树树72W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2
42、步步54325549重复第重复第3步步5549327.7 哈夫曼哈夫曼(Huffman)树树73W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程重复第重复第2步步重复第重复第3步步554932554932147.7 哈夫曼哈夫曼(Huffman)树树74课堂练习课堂练习 现有权值集合现有权值集合W=3, 5, 6, 7, 9, 12, 18，请，请构造相应的哈夫曼树。构造相应的哈夫曼树。757.7 哈夫曼哈夫曼(Huffman)树树怎样的编码方式，使得电文最短？怎样的编码方式，使得电文最短？哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码编码：编码：将传送的文字转换为二进制字符将传送的文字转
43、换为二进制字符0和和1组成的组成的二进制串的过程为编码。二进制串的过程为编码。前前缀缀编编码码：一一组组编编码码中中任任一一编编码码都都不不是是其其它它任任何何一一个编码的前缀个编码的前缀；保证了在解码时不会有多种可能。；保证了在解码时不会有多种可能。767.7 哈夫曼哈夫曼(Huffman)树树哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码假设要传送的电文为假设要传送的电文为ABACCDA，电文中只有，电文中只有A,B,C,D四种字符，则有以下编码方案：四种字符，则有以下编码方案：字符字符ABCD编码编码100011011编码编码2011010111编码编码1，则电文为：，则电文为：00010
44、010101100，总长度为，总长度为14。编码编码2，则电文为：，则电文为：0110010101110，总长度为，总长度为13。777.7 哈夫曼哈夫曼(Huffman)树树哈夫曼编码：哈夫曼编码：设需要编码的字符集合为设需要编码的字符集合为d1,d2,dn，各个字符在电文中出现的次数集合为，各个字符在电文中出现的次数集合为w1,w2,wn，以以d1,d2,dn作为叶结点，以作为叶结点，以w1,w2,wn作为各叶结点作为各叶结点的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支为的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支为0，右分支为，右分支为1，则从根结点到每个叶结点所经过的分支对，则从根
45、结点到每个叶结点所经过的分支对应的应的0和和1组成的序列便为该结点对应字符的编码。组成的序列便为该结点对应字符的编码。代码总长度最短的不等长编码称之为哈夫曼编码。代码总长度最短的不等长编码称之为哈夫曼编码。哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码78例：一组字符例：一组字符例：一组字符例：一组字符A, B, C, D, E, F, GA, B, C, D, E, F, G出现的频率分别出现的频率分别出现的频率分别出现的频率分别是是是是9, 11, 5, 7, 8, 2, 39, 11, 5, 7, 8, 2, 3，设计最经济的编码方案。，设计最经济的编码方案。，设计最经济的编码方案。，设计
46、最经济的编码方案。0000001111119523510191126871545ABDCEFG编码方案：编码方案：A：00B：10C：010D：110E：111F：0110G：0111怎样对电文进怎样对电文进行编码和译码？行编码和译码？79利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理N个叶子叶子结点的哈夫曼树会有个叶子叶子结点的哈夫曼树会有2N-1个结点，个结点，初始化方仿真指针顺序表初始化方仿真指针顺序表下标下标data weight lChild rChild parentflag0A1-1-1-101B3-1-1-102C
47、5-1-1-103D 7-1-1-1040-1-1-1050-1-1-1060-1-1-10叶叶子子结结点点分分支支结结点点80利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最小的两个flag为为0的结点合并的结点合并下标下标data weight lChild rChild parentflag0A1-1-1-101B3-1-1-102C 5-1-1-103D 7-1-1-1040-1-1-1050-1-1-1060-1-1-10叶叶子子结结点点分分支支结结点点81利用二叉树仿真指针顺序表构造哈夫曼利
48、用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最小的两个flag为为0的结点合并的结点合并下标下标data weight lChild rChild parentflag0A1-1-1411B3-1-1412C 5-1-1-103D 7-1-1-104401-1050-1-1-1060-1-1-10叶叶子子结结点点分分支支结结点点82利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最小的两个flag为为0的结点合并的结点合并下标下标data weig
49、ht lChild rChild parentflag0A1-1-1411B3-1-1412C 5-1-1-103D 7-1-1-104401-1050-1-1-1060-1-1-10叶叶子子结结点点分分支支结结点点83利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最小的两个flag为为0的结点合并的结点合并下标下标data weight lChild rChild parentflag0A1-1-1411B3-1-1412C 5-1-1513D 7-1-1-104401515942-1060-1-1-
50、10叶叶子子结结点点分分支支结结点点84利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最小的两个flag为为0的结点合并的结点合并下标下标data weight lChild rChild parentflag0A1-1-1411B3-1-1412C 5-1-1513D 7-1-1-104401515942-1060-1-1-10叶叶子子结结点点分分支支结结点点85利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理挑选出权值最小的两个挑选出权值最
51、小的两个flag为为0的结点合并的结点合并下标下标data weight lChild rChild parentflag0A1-1-1411B3-1-1412C 5-1-1513D 7-1-16144015159426161635-10叶叶子子结结点点分分支支结结点点86利用二叉树仿真指针顺序表构造哈夫曼利用二叉树仿真指针顺序表构造哈夫曼树进行哈夫曼编码原理树进行哈夫曼编码原理哈夫曼编码，对每个叶子结点进行向上溯源，编码哈夫曼编码，对每个叶子结点进行向上溯源，编码在数组中右对齐。在数组中右对齐。四位编码数组四位编码数组bitstartweight data10011A10113B1125C
52、037D 87实验预告实验预告利用教材哈夫曼编码的实现程序，实现对给利用教材哈夫曼编码的实现程序，实现对给定的电文进行编码和译码。定的电文进行编码和译码。【进阶进阶】对英文文档文件进行编码和译码。对英文文档文件进行编码和译码。88* 树与二叉树的转换树与二叉树的转换一、树转换为二叉树一、树转换为二叉树 （1）树中所有相同双亲结点的兄弟结点之间加一条连线。）树中所有相同双亲结点的兄弟结点之间加一条连线。（2）对树中不是双亲结点第一个孩子的结点，只保留新添）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲加的该结点与左兄弟结点之间的连线，删去该结点与
53、双亲结点之间的连线。结点之间的连线。（3）整理所有保留的和添加的连线，使每个结点的第一个）整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。结点连线位于右孩子指针位置。89A AB BC CD DE EF FG GA AB BC CD DE EF FG GA AB BC CD DE EF FG GA AB BE EF FC CD DG G( (a a) )( (b b) )( (c c) )( (d d) )树转换为二叉树的过程树转换为二叉树的过程（a a）树）树; ;（
54、b b）相临兄弟加连线相临兄弟加连线; ;（c c）删除双亲与非删除双亲与非第一个孩子连线第一个孩子连线; ;（d d）二叉树二叉树 90二、二叉树还原为树二、二叉树还原为树（1）若某结点是其双亲结点的左孩子，则把该结点的）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子右孩子、右孩子的右孩子都与该结点的双亲结都与该结点的双亲结点用线连起来。点用线连起来。（2）删除原二叉树中所有双亲结点与右孩子结点的连）删除原二叉树中所有双亲结点与右孩子结点的连线。线。（3）整理所有保留的和添加的连线，使每个结点的所）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。有孩子
55、结点位于相同层次高度。91二叉树还原为树的过程二叉树还原为树的过程（a a）二叉树二叉树; ;（b b）双亲与非第一个孩子加连线双亲与非第一个孩子加连线; ;（c c）删除结点与右孩子连线删除结点与右孩子连线; ;（d d）树树ABEFCDGABEFCDGABEFCDGABCDEFG(a)(b)(c)(d)92树的遍历树的遍历 树的遍历操作是指按某种方式访问树中的每一个结点树的遍历操作是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历算法主要有先根遍且每一个结点只被访问一次。树的遍历算法主要有先根遍历算法和后根遍历算法两种。历算法和后根遍历算法两种。 一、先根遍历一、先根遍历
56、 树的先根遍历递归算法为：树的先根遍历递归算法为： （1）访问根结点；）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。）按照从左到右的次序先根遍历根结点的每一棵子树。93上图中所示树，先根遍历得到的结点序列为：上图中所示树，先根遍历得到的结点序列为：A B E J F C G K L D H IA B E J F C G K L D H I注注意意：树树的的先先根根遍遍历历序序列列一一定定和和该该树树转转换换的的二二叉叉树的先序遍历序列相同。树的先序遍历序列相同。ABCDEFIHGJKL942.2.后根遍历后根遍历树的后根遍历递归算法为：树的后根遍历递归算法为：（1 1）按
57、按照照从从左左到到右右的的次次序序后后根根遍遍历历根根结结点点的的每每一一棵棵子树；子树；（2 2）访问根结点。）访问根结点。上页图中所示树，后根遍历得到的结点序列为：上页图中所示树，后根遍历得到的结点序列为：J E F B K L G C H I D AJ E F B K L G C H I D A注意：树的后根遍历序列一定和该树转换的二叉树的注意：树的后根遍历序列一定和该树转换的二叉树的中序遍历序列相同。中序遍历序列相同。 95本章小结本章小结 本章主要介绍了树的定义、术语；树的各种表示本章主要介绍了树的定义、术语；树的各种表示方式和存储结构；二叉树的定义、性质及其存储方式和存储结构；二叉
58、树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的三种遍历算法类型定义；二叉树的三种遍历算法(递归与非递归递归与非递归)及其用二叉树的遍历方法解决相关的应用问题；及其用二叉树的遍历方法解决相关的应用问题；哈夫曼树的概念及哈夫曼编码。同时也简单地介哈夫曼树的概念及哈夫曼编码。同时也简单地介绍了二叉树的分步遍历；二叉树的线索化方法；绍了二叉树的分步遍历；二叉树的线索化方法；树与二叉树的转换；树的遍历。树与二叉树的转换；树的遍历。96作作 业业P197第第3、4、10、13、14、15、16、20、21、22题题97实实 验验P198第第24题。题。98进进 阶阶二叉树后序遍历的非递归算法的实现。二叉树后序遍历的非递归算法的实现。理解二叉树的分步遍历。理解二叉树的分步遍历。理解线索二叉树的实现及其应用。理解线索二叉树的实现及其应用。99课外阅读课外阅读1、树的孩子兄弟表示方法及其应用。、树的孩子兄弟表示方法及其应用。2、指令系统中常用的编码方法及、指令系统中常用的编码方法及Huffman编码的应用。编码的应用。100
