课件5树和二叉树

5树和二叉树1.掌握二叉树的基本概念、性质和存储结构2.掌握二叉树的前、中、后序遍历方法3.了解线索化二叉树的思想4.了解：霍夫曼树的实现方法、构造霍夫曼编码的方法5.掌握：森林与二叉树的转换，树的遍历方法教学目标5.1树的定义和基本术语树是n个结点的有限集T1T2T3

根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。基本术语——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟堂兄弟祖先子孙基本术语——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数层次1234基本术语5.2二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。二叉树基本特点：结点的度小于等于2有序树（子树有序，不能颠倒）二叉树的五种不同形态具有3个结点的二叉树可能有几种不同形态？

练习性质1:在二叉树的第i层上至多有2i-1个结点二叉树的性质提问：第i层上至少有

个结点？性质2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少有

个结点？1k性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）特殊形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。满二叉树和完全二叉树的区别一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（）。练习2500性质4:具有n个结点的完全二叉树的深度必为[log2n]＋1k层nk-1层性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。二叉树的顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。abcde0000fg012345678910abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树二叉树的顺序存储DATAPARENTLCHILDRCHILD二叉树的链式存储ABCDEFGABCDEFG^^^^^^^^二叉链表分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。空指针数目＝2n－(n-1)=n+1在n个结点的二叉链表中，有

个空指针域练习ABCDEFG^^^^^^^^n+1三叉链表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchild5.3二叉树的遍历遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。DLRDLRLDRLRDDRLRDLRLD遍历规则先左后右先序遍历：中序遍历：后序遍历：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。重要结论练习已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG

和

DECBHGFA，请画出这棵二叉树。①由后序遍历特征，根结点必在后序序列尾部（A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（BDCE），其右部必全部是右子树子孙（FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。中序遍历：BDCEAFHG

后序遍历：DECBHGFA（BDCE）（FHG）ABF

（DCE）

（HG）CDEGHABBFF5.4二叉树的二叉链表实现结点定义StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//结束

else{cout<<T->data;

PreOrderTraverse(T->lchild);

//递归左子树

PreOrderTraverse(T->rchild);

//递归右子树

}}

先序遍历递归算法结束条件递归过程递归算法=递归结束条件+递归过程StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC创建二叉树获取结点数获取高度查找结点获取双亲结点如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历遍历算法的非递归实现分析使用一个栈s存放路径。开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空，则访问根结点；然后p进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况若从左子树返回，说明左子树遍历结束，应该将指针指向其双亲结点的右孩子进行遍历，即指向栈顶结点的右子树若从右子树返回，说明已将以其双亲结点为根的子树遍历结束，则应该将指针指向其双亲结点的右兄弟进行遍历，即指向栈顶结点的右子树3、当指针为空且栈为空时，遍历结束先序遍历算法的非递归算法ADBCE栈s访问序列p不空时

Visit(p);Push(S,p);

p=p->lc;

p空时

Pop(S,p)p=p->rc;AABBCCDDEE先序遍历算法的非递归算法示例使用栈存放经过的路径，开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空；p进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况若从左子树返回，说明左子树遍历结束，应该将指针指向其双亲结点，访问双亲结点，并对双亲结点的右孩子进行遍历，即访问栈顶结点后指向栈顶结点的右子树若从右子树返回，说明已将以其双亲结点为根的子树遍历结束，则应该将指针指向其未访问过的祖先结点进行访问，并指向其结点的右子树，即访问栈顶结点后指向栈顶结点的右子树3、当指针为空且栈为空时，遍历结束中序序遍历算法的非递归算法ADBCEp不空时

Push(S,p);

p=p->lc;

p空时

Pop(S,p)

Visit(p);

p=p->rc;栈s访问序列AABBCCDDEE中序序遍历算法的非递归算法示例使用栈存放经过的结点及结点标志，开始时栈为空，p指向树根结点T1、如果指向根结点的指针p非空，先将标志tag＝0；再将p及tag进栈；p指向它的左孩子2、如果指向根结点的指针p为空，有两种情况若tag＝0，则改变tag＝1；再把tag和弹出的结点重新入栈；然后将指针指向该结点的右子树若tag＝1，则访问弹出的结点，并将弹出的结点指针置空3、当指针为空且栈为空时，遍历结束后序序遍历算法的非递归算法ADBCE栈s访问序列A0B0B1C0C1D0D1E0E1p不为空

SNode.tag=0;Push(S,SNode);SNode.p=SNode.p->lc;p为空且tag＝0Pop(S,SNode);SNode.tag=1;Push(S,SNode);SNode.p=SNode.p->rc;p为空且tag＝1Pop(S,SNode);Visit(SNode.p);SNode.p=NULL;CEDBA1A后序序遍历算法的非递归算法示例AFEDCBG时间效率:O(n)

//每个结点只访问一次空间效率:O(n)

//栈占用的最大辅助空间非递归遍历算法的分析二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。思考线索化二叉树在n个结点的二叉链表中，有n+1个空指针域ABCDEFG^^^^^^^^普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树例如中序遍历结果：BDCEAFHG，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！可能是根、或最左（右）叶子5.5线索二叉树1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)

。为了避免混淆，增加两个标志域lchildLTagdataRTagrchild线索化二叉树LTag:若LTag=0,lchild域指向左孩子；

若LTag=1,lchild域指向其前驱。RTag:若RTag=0,rchild域指向右孩子；

若RTag=1,rchild域指向其后继。

lchildLTagdataRTagrchild线索化二叉树ABCDEABDCET先序序列：ABCDE00001111^11

lchildLTagdataRTagrchild先序线索二叉树LTag=0,lchild域指向左孩子

LTag=1,lchild域指向其前驱RTag=0,rchild域指向右孩子

RTag=1,rchild域指向其后继

ABCDEABDCET中序序列：BCAED00001111^11^

lchildLTagdataRTagrchild中序线索二叉树

lchildLTagdataRTagrchildABCDEABDCET后序序列：CBEDA0000111111^后序线索二叉树线索：指向结点前驱和后继的指针线索链表：加上线索二叉链表线索二叉树：加上线索的二叉树（图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程线索化二叉树的几个术语ABCGEIDHFroot悬空？悬空？该二叉树中序遍历结果为:

H,D,I,B,E,A,F,C,G画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0--root0画出与二叉树对应的中序线索二叉树

2825405560330854因为中序遍历序列是：5540256028083354对应线索树应当按此规律连线，即在原二叉树中添加虚线。NILNIL练习5.5霍夫曼树及其应用路径路径长度带权路径长度:树的带权路径长度：WPL=wklkk=1nAFEDCBG:由一结点到另一结点间的分支所构成:路径上的分支数目结点到根的路径长度与结点上权的乘积2235dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*2+5*2+2*2+4*2=36权值分别为7，5，2，4，构造有4个叶子结点的二叉树霍夫曼树：带权路径长度最小的树根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树。在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即霍夫曼树。霍夫曼树的构造过程a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4霍夫曼树的构造过程在远程通讯中，要将待传字符转换成二进制的字符串，怎样编码才能使它们组成的报文在网络中传得最快？ABACCDA000110010101100000011010霍夫曼树应用实例－－霍夫曼编码出现次数较多的字符采用尽可能短的编码关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀－前缀编码

0000AAAAABABB重码ABACCDA000011010霍夫曼树应用实例－－霍夫曼编码ACBD000111采用二叉树设计前缀编码左分支用“0”右分支用“1”A—0B—110C—10D—111

0110010101110ABACCDA分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。0110010101110ACBD000111ABACCDA特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码霍夫曼编码的译码过程假设通信的电文仅由8个字母组成，字符在电文中出现的频率分别为（7、19、2、6、32、3、21、10），试为这8个字母设计Huffman编码集合F7、19、2、6、32、3、21、10

523集合F7、19、6、32、21、10

、517710116603228401921100集合F7、19、32、21、10、11集合F19、32、21、11、17集合F19、32、21、28集合F32、28、40集合F40、60集合F1000001101100110101101111101111霍夫曼编码是不等长编码霍夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀霍夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则霍夫曼编码树的结点总数为2n-1发送过程：根据由霍夫曼树得到的编码表送出字符数据接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束霍夫曼编码的几点结论5.6树和森林若树非空，则先访问树的根结点，然后依次先根遍历根的每棵子树RABDCFGEIHR（ADE）（B）（CFGHI）树的先根遍历RADEBCFGHI5.6树和森林树的先根遍历若树非空，则先依次后根遍历根的每棵子树，然后访问树的根结点RABDCFGEIH（ADE）（B）（CFGHI）R树的后根遍历（DEA）（B）（（FGHI）C）R（DEA）（B）（GHIFC）R树的后根遍历若树非空，则从树的根结点起按层从左到右依次访问各结点RABDCFGEIHR（ABC）（DEF）（GHI）树的层次遍历RABCDEFGHI树的层次遍历练习：写出下面这棵树的先根、后根和层次遍历ABJDCFGEIHABDCFGEIH若森林非空，则可以按照下述规则遍历：a、访问森林中第一棵树的根结点b、先序遍历第一棵树中根结点的子树森林c、先序遍历除去第一棵树之后剩余的树构成的森林森林的先序遍历A（DE）（BCFGHI）ADEBCFGHI森林的先序遍历ABDCFGEIH若森林非空，则可以按照下述规则遍历：a、中序遍历第一棵树中根结点的子树森林b、访问森林中第一棵树的根结点c、中序遍历除去第一棵树之后剩余的树构成的森林森林的中序遍历（DE

）A（BCFGHI）DEA（B（FGHIC））DEABGHIFC森林的中序遍历ABDCFGEIH若森林非空，则可以按照下述规则遍历：a、对第一棵树从根结点起按层从左到右依次访问结点b、按层访问森林中除去第一棵树之后剩余的树构成的森林森林的层次遍历ADEBCFGHI森林的层次遍历练习：写出下面森林的先序、后序和层次遍历BJDCFGEIHRABDCFGEIHRABDCFGEIH（1）加线：在各兄弟间加一连线（2）去线：对任何结点，除了其最左子树之外，去掉该结点与其他子树之间的连线（3）调整二叉树的层次树和二叉树的转换（1）将森林中的每一棵树转换成二叉树（2）将每棵二叉树按左孩子右兄弟的规则连接成一棵二叉树ABDCFGEIHABDCFGEIH森林与二叉树的转换ABJDCFGEIH练习：写出下面这两棵树转换为二叉树和森林ECDBFAGHJIABDCFGEIHABDCFGEIH森林的先序遍历：ADEBCFGHI森林的中序遍历：DEABGHIFC二叉树的先序遍历：ADEBCFGHI二叉树的中序遍历：DEABGHIFC森林与二叉树间的遍历关系RABDCFGEIHRABDCFGEIH树的先根遍历：RADEBCFGHI树的后根遍历：DEABGHIFCR二叉树的先序遍