第06章 树和二叉树

第六章树和二叉树数据结构:线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)第六章树和二叉树§6.1树的定义树是n个数据元素的有限集(记为T)，对任意一棵树T有：⒈存在唯一一个称为根的数据元素；⒉当n＞1时，其它数据元素可分为m(m＞0)个互不相交的有限集T1,T2,…,Tm，其中每个集合Ti(i=1,2,…,m)本身又是一棵树，并称树

Ti是根的子树.第六章树和二叉树树的表示法1.分支图表示法2.嵌套集合表示法ABCDABCD3.广义表表示法(A(B(D),C))第六章树和二叉树树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))

含义:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.第六章树和二叉树§6.2树的基本运算

⒈初始化操作INITIATE(T)：创建一棵空树。⒉求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。⒊求双亲函数PARENT(T,x)：在树T中求x的双亲。⒋求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。⒌求兄弟函数：在T中求x的左兄弟LSIBLING(T,x)；在树T中求x的右兄弟RSIBLING(T,x)。第六章树和二叉树

⒍建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。⒎插入子树操作INS-CHILD(y,i,x)：将x作为y的第i根子树。⒏删除子树操作DEL-CHILD(x,i)：删除x的第i棵子树。⒐遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。⒑置空树操作CLEAR(T)：将树T置为空树。第六章树和二叉树§6.3二叉树概念及性质一.二叉树概念二叉树是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树，它的特点是：⑴每个结点最多只有两棵子树，即不存结点度大于2的结点；⑵子树有左右之分，不能颠倒。6.3二叉树二.二叉树性质性质1.

在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2.深度为k的二叉树至多有2k-1个结点(k≥)。（深度一定，二叉树的最大结点数也确定）性质3.二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+16.3二叉树满二叉树:深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大（2）度为1的结点n1=0

结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654K=3n=23-1=7满二叉树

6.3二叉树完全二叉树:深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。452136.3二叉树完全二叉树的特点:（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1＜n≤2k-1（3）满二叉树一定是完全二叉树，反之不成立。452136.3二叉树LH2=0RH2=11324653241LH1=3RH1=1LH1-RH1=2

非完全二叉树非完全二叉树LH2-RH2=0-1=-16.3二叉树性质4.结点数为n的完全二叉树，其深度为└log2n┘+16.3二叉树性质5.在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则(i>1)，结点i的双亲为结点└i/2┘。⑵2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。6.3二叉树

完全二叉树DCGFEBA三、二叉树的存储结构⒈顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。

bt[3]的双亲为└3/2┘=1，即在bt[1]中；

其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG00006.3二叉树

这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。D二叉树CGFEBA1234567891011ABCDE0000FG0000一般二叉树也按完全二叉树形式存储,没结点处用0表示。6.3二叉树例如，深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。1k6.3二叉树⒉链式存储结构设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表三叉链表线索链表用空链域存放指向前驱或后继的线索

6.3二叉树二叉链表的结点结构lchilddatarchildD

二叉树CEBAACBDE∧∧∧∧∧∧二叉链表6.3二叉树

三叉链表的结点结构lchilddataparentrchildD

二叉树CEBAACBDE∧∧∧∧∧∧∧三叉链表6.3二叉树性质6.含有n个结点的二叉链表中，有n+1个空链域。6.4遍历二叉树和线索二叉树一、遍历二叉树

遍历二叉树是指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。

访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。

遍历的次序：若设二叉树根为D，左子树为L，右子树为R，并限定先左后右，则有以下三种遍历次序：LDR中序遍历；LRD后序遍历；DLR先序遍历6.4遍历二叉树和线索二叉树1.中序遍历二叉树算法思想:

若二叉树非空，则：1）中序遍历左子树2）访问根结点3）中序遍历右子树算法描述:PROCinorder(bt：bitreptr)；{bt为BT根结点指针}IFbt<>NILTHEN[inorder(bt↑．lchild);visit(bt↑．data)；inorder(bt↑．rchild);]ENDP;{inorder}6.4遍历二叉树和线索二叉树2.后序遍历二叉树算法思想:

若二叉树非空，则：1）后序遍历左子树2）后序遍历右子树3）访问根结点算法描述:PROCpostorder(bt：bitreptr)；{bt为BT根结点指针}IFbt<>NILTHEN[postorder(bt↑．lchild);postorder(bt↑．rchild);visit(bt↑．data)；]ENDP;{postorder}6.4遍历二叉树和线索二叉树3.先序遍历二叉树算法思想:

若二叉树非空，则：1）访问根结点2)先序遍历左子树3）先序遍历右子树算法描述:PROCpreorder(bt：bitreptr)；{bt为BT根结点指针}IFbt<>NILTHEN[visit(bt↑．data)；

preorder(bt↑．lchild);preorder(bt↑．rchild);]ENDP;{preorder}6.4遍历二叉树和线索二叉树例：表达式a+b×(c-d)-e/facdef／－b×＋－+遍历结果:中序:a+b×c－d－e/f后序:abcd－×+ef/－先序:－+a×b－cd/ef6.4遍历二叉树和线索二叉树三种遍历过程示意图例acb×－ab*c-ba*-cab*c-－×abc

虚线表示执行过程:向下表示更深层的递归调用;向上表示递归调用返回;沿虚线记下各类符号,便得到遍历的结果.6.4遍历二叉树和线索二叉树PROCinorder(bt:bitreptr)；{中序遍历非递归算法,s为存储二叉树结点指针栈}

INISTACK(s)；push(s,bt)；

WHILENOTEMPTY(s)DO

[

WHILEGETTOP(s)<>NILDO

PUSH(s,GETTOP(s)↑.lchild)；

p:=POP(s)；

IFNOTEMPTY(s)THEN[visit(GETTOP(s)↑.data)；p:=POP(s)；PUSH(s,p↑.rchild)]]ENDP；{inorder}

根结点先进栈，左结点紧跟根后面进栈,右结点在根出栈后入栈每个结点都要进一次和出一次栈，并且总是访问栈顶元素，因此，算法正确，时间复杂度为O(n)。6.4遍历二叉树和线索二叉树二、线索二叉树

⒈问题的提出：通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在结点和前驱和后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，能否通过结点的两个链域查找出任一结点的前驱和后继?6.4遍历二叉树和线索二叉树2.分析：

n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个空链域，n-1个指针域；因此,必须用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。6.4遍历二叉树和线索二叉树3.线索二叉树：⑴结点结构在二叉链表中增加ltag和rtag两个标志域lchildltagdatartagrchild

若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）；

若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）；6.4遍历二叉树和线索二叉树

称这种结点结构为线索链表；其中指示前驱和后继的链域称为线索；加上线索的二叉树称为线索二叉树；对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树；按后序遍历得到的线索二叉树称为后序线索二叉树；6.4遍历二叉树和线索二叉树（2）整体结构增设一个头结点，令其lchild指向二叉树的根结点，ltag=0、rtag=1；

并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。acb×－010－

01c10×

01b11a16.4遍历二叉树和线索二叉树4.遍历线索二叉树：

有了线索二叉树，就容易遍历二叉树了．只要（１）先找要遍历的第一个结点；（２）然后依次找结点的后继；（３）重复（２）直到其后继为头结点．所有问题归为如何在线索二叉树中找结点的后继？6.4遍历二叉树和线索二叉树1）遍历中序线索二叉树（1）中序线索二叉树中，找结点的后继算法算法思想:

对任意结点p，若rtag=1，则rchild指向该结点的后继；若rtag=0，则rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s（ltag=1）,则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点；6.4遍历二叉树和线索二叉树中序线索二叉树中，找结点的后继算法FUNCin_next(p,thrt:thlinktp):thlinktp；{在以thrt为头指针的中序线索二叉树上,查找指针p所指结点的后继}

s:=p↑.rchild；

IFp↑.rtag=0THENWHILEs↑.ltag=0DO

s:=s↑.lchild；RETURN(s)ENDIF；{in_next}p1sp010s6.4遍历二叉树和线索二叉树（2）遍历中序线索二叉树算法PROCthrt_inorder(thrt:thlinktp)；{遍历以thrt为头指针的中序线索二叉树}

p:=thrt↑.lchild；

WHILEp↑.lchild<>thrtDOp:=p↑.lchild;{定位要遍历的第一个结点.}

WHILEp<>thrtDO[visit(p↑.data)；p:=in_next(p,thrt)]ENDP；{thrt_inorder}

p↑.ltag=0

6.4遍历二叉树和线索二叉树2）遍历后序线索二叉树（1）后序线索二叉树中，找结点的后继算法算法思想:

对任意结点p，

若p为二叉树的根，则无后继;若p是双亲的右孩子、或是独生左孩子，则后继为双亲；若p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点(叶结点)；spspsps6.4遍历二叉树和线索二叉树后序线索二叉树中，找结点的后继算法FUNCpost_next(p,thrt:thlinktp):thlinktp；{在以thrt为头指针的后序线索二叉树上,查找指针p所指结点的后继}

s:=parent（thrt，p）；{在thrt上查找p的双亲}

IFs=thrtTHENRETURN(thrt)；

IFs↑.rchild=pORs↑.rtag=1

THENRETURN(s)；WHILEs↑.rtag=0DO

[s:=s↑.rchild；

WHILEs↑.ltag=0DOs:=s↑.lchild；]RETURN(s)ENDIF；{post_next}6.4遍历二叉树和线索二叉树（2）遍历后序线索二叉树算法PROCthrt_postorder(thrt:thlinktp)；{遍历以thrt为头指针的后序线索二叉树}

IFthrt<>thrt↑.lchildTHEN[p:=thrt↑.lchild；search:=true；

WHILEsearchDO[WHILE

p↑.ltag=0

DO

p:=p↑.lchild；

IF

p↑.rtag=0

THEN

p:=p↑.rchild

ELSE

search:=false；]

WHILEp<>thrtDO[visit(p↑.data)；p:=post_next(p,thrt)]]ENDP；{thrt_postorder}6.4遍历二叉树和线索二叉树3）遍历先序线索二叉树（1）先序线索二叉树中，找结点的后继算法算法思想:

对任意结点p:

若p有左孩子，则后继为左孩子;若p无左孩子,有右孩子，则后继为右孩子；若p无左孩子,也无右孩子，则后继为右线索；6.4遍历二叉树和线索二叉树先序线索二叉树中，找结点的后继算法FUNCpre_next(p,thrt:thlinktp):thlinktp；{在以thrt为头指针的先序线索二叉树上,查找指针p所指结点的后继}IFp↑.ltag=0THENRETURN(p↑.lchild)；ELSERETURN(p↑.rchild)ENDIF;{pre_next}6.4遍历二叉树和线索二叉树（2）遍历先序线索二叉树算法PROCthrt_preorder(thrt:thlinktp)；{遍历以thrt为头指针的先序线索二叉树}

p:=thrt↑.lchild；WHILEp<>thrtDO[visit(p↑.data)；p:=pre_next(p,thrt)]ENDP;{thrt_preorder}

6.５树和森林一．树的存储结构１．双亲表示法用一组地址连续的存储单元来存放树的结点，每个结点有两个域：

data域-----存放结点的信息；

parent域-----存放该结点双亲结点的位置．４３２６５１１２３４５６０１１２２２

data

parent特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。

6.５树和森林２．孩子表示法每个结点的孩子用单链表存储，称为孩子链表。

n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。

n个孩子链表的头指针用一个向量表示。如图：头指针向量孩子链表１２３４５６６５４３２∧∧∧∧∧∧特点：与１相反，求孩子易，求双亲难。

6.５树和森林３．双亲孩子表示法．在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。如图：头指针向量孩子链表０１１２２２１２３４５６６５４３２∧∧∧∧∧∧

6.５树和森林４．孩子兄弟表示法．用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。如图：

∧∧∧∧１２３４５６∧∧∧双亲只管长子长子连接兄弟

6.５树和森林二、森林、树与二叉树的对应关系１、树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。

ＤＢＡＥＣ∧∧ＢＣ∧Ｅ∧Ａ∧Ｄ∧ＤＥＣｂＡＢ∧ＡＣ∧Ｄ∧Ｅ∧∧∧（２）顺时针转４５度（１）孩子兄弟法树解释：B是A的第一个孩子，C、E是B的兄弟，D是C的第一个孩子。解释：Ｂ是Ａ的左孩子，Ｃ是Ｂ的右孩子。

6.５树和森林树变为二叉树的方法（１）在兄弟之间加一连线；（２）对每一个结点，只保留它与第一个孩子的连线，去掉与其他孩子的连线；（３）以树根为轴心，将整棵树顺时针旋转45度。

特点：根无右子树

6.５树和森林2.森林与二叉树的对应关系（1）森林转换为二叉树的方法将森林F={T1，T2...

Tm}的各棵树分别转成二叉树BT1，BT2...

BTm

将BTi+1作为BTi根结点的右子树（i=1,2,...,m-1）,得到一棵BT。

6.５树和森林如图：F={T1，T2，T3}DBCABT1FEBT2BCFEJHADIGT1T3T2BT3HJIGJIFEBDAHGC6.５树和森林(2)二叉树转换森林的方法将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；重复上面直到某结点的右子树为空。JIHGFEBCDAT1BCDAFET2T3JIHG

6.6哈夫曼树及其应用哈夫曼树（Huffman）树是一类带权路径长度最短的树一、Huffman树（最优二叉树）1、概念两结点间的路径：从一结点到另一结点所经过的结点序列路径长度：路径上的分支树树的路径长度：从根到每一结点的路径长度之和2763415例⑴-⑵-⑸为结点1到5之间的路径，其路径长度为2，树的路径长度=l12+l13+

l14+l15+

l16+l17

=1+1+2+2+2+2=10

6.6哈夫曼树及其应用

完全二叉树是路径长度最短的二叉树。考虑带权时：设树中有m个叶结点，每个叶结点带一个权值wｉ且根到叶结点i的路径长度为Li(ｉ=1，2，．．m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。

Ｍ

即：ＷＰＬ＝∑ＷｋＬｋ

Ｋ＝１

6.6哈夫曼树及其应用

例：使WPL最小的二叉树成为最优二叉树(Huffman树)完全二叉树dcab7524

cdba2475WPLa=2*7+2*5+2*2+2*4WPLb=7*3+5*3+2*1+4*2=36=46

6.6哈夫曼树及其应用

Huffman树WPLc=7*1+5*2+2*3+4*3=35bdca7524（1）完全二叉树并不一定是Huffman树；（2）HT是权值越大的越靠近根结点；（3）HT不唯一，但WPL一定相等。

6.6哈夫曼树及其应用2．构造Huffman树算法(1)以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树Ti仅有一个权值为Wi的根结点；(2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值=Wi）(3)从F中删除这两棵二叉树，同时将新二叉树加入到F中;(4)重复(2)．(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。

6.6哈夫曼树及其应用abcd7524例:

F={}abF={}cd

756

24F={