算法与数据结构课件-DSC6

第六章.树和二叉树（Chapter6.TreeandBinaryTree)§6.1树的定义及基本操作

树型结构是一种非常重要的非线性数据结构，可广泛应用于描述家族关系或行政组织机构。

树是n(n≥0)个结点的有限集。在一棵非空树中，有且仅有唯一的根（root）结点，当n>1时，除根结点外其余结点可分为m(m>0)个互不相交的有限集，它们本身也是一棵树，称为根的子树（subtree）。ABCEFGD一棵树如右图所示：

树还可以用下面的形式化描述来表示：Tree=（D,R）其中：D={ai|ai∈D0,i=1,2,…,n,n≥0}R={H}H为如下描述的二元关系：1、在D中存在唯一的根元素root，它在关系H下无前驱；2、若D-{root}≠φ，则存在D-{root}的一个划分D1,...,

Dm(m>0)，对任意一对j≠k(1≤j,k≤m)有Dj∩Dk

=φ，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有<root,xi>∈H；3、对于D-{root}的划分，H-{<root,x1>,…,

<root,

xm>}有唯一的划分H1,

H2,...,

Hm(m>0)，对任意一对j≠k(1≤j,k≤m)有Hj∩Hk=φ，且对任意的i(1≤i≤m)，Hi是Di上的二元关系，且(Di,Hi)也是一棵符合本定义的树，称为root的子树。树的一些基本术语：结点的度（degree）结点所拥有的子树的数目。叶子结点（leaf--又称终端结点terminalnode）度为零的结点。度不为零的结点。孩子（

child--也称儿子son）结点的子树的根称为结点的孩子。分支结点（branchnode--又称非终端结点non-terminalnode

）双亲（

parent）结点是其孩子的双亲。祖先（

forefather）从树根到双亲的所有结点称为该结点的祖先。子孙（progeny）以结点为根的子树的所有结点称为该结点的子孙。兄弟（sibling）同一父母的所有孩子互称兄弟。层次（level）树根为第一层，其孩子为第二层，孙子为第三层，以此类推。有序树（orderedtree）结点各子树从左至右是有秩序的树称为有序树。无序树（unorderedtree）结点各子树没有秩序的树称为无序树。森林（forest）森林是m(m≥0)棵互不相交的树的集合。堂兄弟（cousin）双亲在同一层的结点互称堂兄弟。深度（depth）树中结点的最大层次称为树的深度。树的基本操作：InitiateRootTraverseChildCrt_TreeClearIns_ChildDel_ChildRight_SiblingParent§6.2二叉树二叉树（binarytree）是一棵度为二的树，其孩子有左右之分，也分别都是二叉树。二叉树的基本操作：InitiateRootParentL(R)childCrt_btClearIns_L(R)childDel_L(R)childTraverseL(R)sibling性质一、在二叉树的第i层上最多有2i-1

个结点（i≥1）。性质二、深度为k的二叉树最多有2k-1个结点（k≥1）。性质三、对任一二叉树，叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。性质四、具有n个结点的完全二叉树的深度为log2n+1。满二叉树（fullbinarytree）：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。二叉树的性质：完全二叉树（completebinarytree）：一棵深度为k的满二叉树的第k层的右边几个结点不存在则为完全二叉树。性质五、对一棵有n个结点的完全二叉树从上到下、从左到右进行连续编号，则对任一结点i(1≤i≤n)有：

1、i=1的结点是树根，i>1的结点的父母为i/2；

2、若左右孩子存在，则分别为2i和2i+1结点。二叉树的存储结构：ABDEFC1、顺序存储结构：A、按完全二叉树存储ABCDEF1234567ABDEFCB、用父母指针存储ABCDEF0-11-2-331234562、链式存储结构：用二叉链表存储A

B

C

DEF∧∧∧∧∧∧∧#definemaxlenuser_supplytypedefelemtypecomptree[maxlen];#definemaxlenuser_supplytypedefstruct{elemtypedata;intparent;}node;structnodebtree[maxlen];typedefstructnode{elemtypedata;structnode*lchild,*rchild;}node,*bitptr;作业13.

一棵满k叉树按层次顺序从1开始对全部结点编号，若所求结点存在，则：1、各层的结点数目是多少？2、编号为n的结点的父结点的编号是多少？3、结点n的第i个儿子的编号是多少？4、结点n有右兄弟的条件是什么？14.

已知一棵度为m的树中有ni

个度为i的结点，则该树中有多少个叶子结点。§6.3二叉树的遍历和线索二叉树遍历二叉树（traversingbinarytree）即按某种搜索顺序对二叉树中每个结点访问且仅访问一次。根据搜索路径的不同，二叉树的遍历分为八种：1、前序遍历（preordertraversal）DLR2、中序遍历（inordertraversal）

LDR3、后序遍历（postordertraversal）LRD4、逆前序遍历（inverse

preordertraversal）DRL5、逆中序遍历（inverse

inordertraversal）

RDL6、逆后序遍历（inverse

postordertraversal）RLD7、按层次遍历（level-by-leveltraversal）8、按层次逆遍历（inverselevel-by-leveltraversal）√√√√ABDEFC1、ABDCEF2、DBAECF3、DBEFCA4、ACFEBD5、FCEABD6、FECDBA7、ABCDEF8、ACBFEDvoidPreorder(structnode*t){if(t){visit(t);Preorder(t->lchild);Preorder(t->rchild);}}voidInorder(bitptrt){if(t){

Inorder(t->lchild);visit(t);

Inorder(t->rchild);}}voidPostorder(structnode*t){if(t){

Postorder(t->lchild);

Postorder(t->rchild);visit(t);}}voidPreorder(structnode*t){//前序遍历的非递归算法

Inistack(s);if(t)Push(s,t);while(!Empty(s){Pop(s,t);visit(t);if(t->rchild)Push(s,t->rchild);

if(t->lchild)Push(s,t->lchild);}}voidPostorder(structnode*t){//后序遍历的非递归算法

Inistack(s);while(t||!Empty(s)){while(t){Push(s,(t,‘L’));t=t->lchild;}tag=‘R’;while(!Empty(s)&&(tag==‘R’)){(t,tag)=Pop(s);if(tag=‘L’){Push(s,(t,‘R’));t=t->rchild;}else{visit(t);t=NULL;}}}}voidLevelorder(structnode*t){//按层次遍历的算法

Iniqueue(q);if(t)Enqueue(q,t);while(!Empty(q)){t=Dequeue(q);visit(t);if(t->lchild)Enqueue(q,t->lchild);if(t->rchild)Eequeue(q,t->rchild);}}能否用任意两种遍历的序列来生成一棵唯一的二叉树？*+aef+/b-cd前序：*+a/b-cd+ef中序：a+b/c-d*e+f表达式：

(a+b/(c-d))*(e+f)后序：abcd-/+ef+*中序遍历时括号怎么加上？能够用前序遍历和中序遍历或者用中序遍历和后序遍历唯一的确定一棵二叉树，但不能用前序遍历和后序遍历唯一的确定一棵树，为什么？中序遍历序列是LDR，可以用来分出左右孩子。而前序和后序遍历是DLR和LRD，不能分出左右孩子。二叉树遍历的应用：作业15.

已知在二叉链表表示的二叉树中，root为根结点，p↑和q↑为二叉树中两个结点，试编写算法求距离它们最近的共同祖先。16.

试给出算法求二叉链表表示的二叉树的直径（高度、最大层次数）以及长度等于直径的一条路经（从根到叶子的结点序列）。作业17.

试给出算法将二叉树表示的表达式按中序遍历输出并加上相应的扩号。线索二叉树（threadedbinarytree）

在二叉树的遍历序列中很容易就找到每个结点的前驱和后继，但要在二叉树中找这个结点的前驱和后继就很困难。如何解决这个问题呢？

方法之一是将二叉链表扩展为四叉链表，亦即加上指向前驱和后继的指针，但这将浪费许多空间。有没有更好的办法呢?

方法之二即是使用线索二叉树，该方法是由A.J.Perlis和C.Thornton二人提出的。一棵二叉链表表示的二叉树有n+1个空指针，可以利用这些空指针来存储结点的前驱和后继，这即是线索。为了区分到底是孩子指针还是线索，还需在每个结点内设置两个标志位ltag和rtag，标志位为0，表示是孩子指针；标志位为1，则表示是线索。其中lchild指向前驱，rchild指向后继。对二叉树以某种遍历使其变为线索二叉树的过程即称为线索化。下面是一棵二叉树的中序线索树：A

B

C

DEF∧∧∧∧∧∧∧000000000000A

B

C

DEF∧∧∧∧∧∧∧D∧∧10D∧

11B

∧00D∧

11B

01A

00B

01A

00E∧10A

00E11C

00E11C

00F∧01C

00F∧11∧∧F∧11∧将一棵二叉树线索化的步骤：1、设前驱指针为空，当前指针为树根；2、按某种顺序遍历二叉树：4、若前驱结点的右子树为空，则将标志位rtag置为1，并将当前指针赋值给rchild；5、将当前指针赋值给前驱指针；6、反复此过程，直至整棵二叉树遍历完为止；7、将前驱结点的标志位rtag置为1。也可以为线索二叉树设置一个头结点，则线索为空时均指向该头结点。3、若当前结点的左子树为空，则将标志位ltag置为1，并将前驱指针赋值给lchild；如何遍历一棵二叉线索树呢？

二叉线索树的遍历不需要递归，因为在二叉线索树中能够很方便地找到当前结点的后继结点。因此，对有n个结点的二叉线索树，可以在O(n)时间内遍历完该树。

线索二叉树优点是节省了空间，但插入和删除结点则非常麻烦，时间复杂度和线索化一棵二叉树相同。因此，在插入和删除结点时可先将线索二叉树还原为一般二叉树，待插入和删除结点完成后再对其线索化。§6.4树和森林树的存储结构：1、双亲表示法ABCEFGDABCDEFG011214412345672、孩子表示法可以用多重链表来表示，但由于各结点的度不一样，因此，用多重链表表示会有很多浪费空间。解决的方法是将各结点的所有孩子组成一个单链表即可。3、孩子兄弟表示法用二叉链表表示，因此又称为二叉树表示法。左链指向结点的第一个孩子，右链指向结点的兄弟。A∧B∧CD∧∧E∧∧F∧G∧ABCDEFG234576∧∧∧∧∧∧∧12345674、带右链的先根序表示法主体顺序按树的先根序遍历，右链指向兄弟。5、带左链的层次序列表示法按孩子兄弟表示法进行转换。ABECDFG04050701234567ABCDEFG25060001234567森林与二叉树的转换：孩子链兄弟链树的遍历：1、先根序遍历：与相应二叉树的前序遍历序列相同。2、后根序遍历：与相应二叉树的什么遍历序列相同？主体顺序按树的层次遍历，左链指向孩子。2、后根序遍历：与相应二叉树的中序遍历相同。第三次上机作业设二叉树结点值为大写字母，输入二叉树的前序遍历和中序遍历序列，生成此二叉树，输出该二叉树的后序遍历和按层次遍历序列。输入某结点值，在二叉树中查找该结点，若该结点存在，则输出从根到该结点的路径，否则给出不存在信息。§6.5霍夫曼树及其应用霍夫曼树（Huffmantree），也称最优树（optimaltree），是一种带权外路径长度（weightedpathlength）最短的树。路径长度是指树中两个结点间路径上所含有的分支数目。树的路径长度是指从树根到每一结点的路径长度之和。带权路径长度是指结点的路径长度与该结点的权之积。设各叶子结点的路径长度为lk，权为wk

，则该树的带权外路径长度为：

WPL=∑wklk

。k=1n则WPL最小的二叉树即为最优二叉树或霍夫曼树。树的带权外路径长度是树中所有叶子结点的带权路径长度之和。霍夫曼树的构造：1、把给定的n个权值集合的各结点均作为一棵树；2、从这n棵树中选取两个权值最小的结点组成新树；3、将这两个结点的权值之和作为新树树根的权值；4、将这两个结点从n棵树中删去，把新树树根加入；5、原来的n棵树减少为n-1棵树；6、重复步骤2--5，直到n=1即为所求。霍夫曼树中除叶子结点外，所有分支结点的度均为2，叶子结点（外部结点）可看成是由分支结点（内部结点）组成的树扩充出来的，因此，霍夫曼树是一棵扩充二叉树（extendedbinarytree）。例：已知字符A、B、C、D、E、F、G，使用频度分别为：0.25、0.1、0.15、0.06、0.3、0.05、0.09，试以此构造霍夫曼树。GB0.19A0.44FD0.11C0.26E0.5611、0.250.10.150.06