第五树和二叉树

第五树和二叉树线性结构和非线性结构。树形结构是以分支关系定义的层次结构，在现实世界中广泛存在，在计算机领域中也有广泛应用。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。25.1树与树林5.1.1树的定义

5.1.2基本术语

5.1.3树林

5.1.4树的基本运算

5.1.5树的周游

5.1.6树林的周游35.1.1树的定义树(Tree)的例子：一个家族。A有子女B,C；B和C分别有子女D,E,F和G,H;E有子女I,J。

T=(N,R),其中

N={A,B,C,D,E,F,G,H,I,J}R={A,B,A,C,B,D,B,E,B,F,C,G,C,H,E,I,E,J}4树的表示方法：(c)凹入表（a）树形表示ABCDEFIJGH5(A(B(D)(E(I)(J))(C(G)(H)))(d)嵌套括号表示法CDEIJFGHAB(b)文氏图6

树(Tree)：是包括n(n>=0)个结点的有限集T。当T非空时，满足：（1）有且仅有一个特别标出的称为根的结点；（2）除根结点外，其余结点可分为m（m>=0）个互不相交非空的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树，称为根的子树

(Subtree)。树的递归定义：空树：不包括任何结点的树。7树结构的特点：（1）树的根的结点没前驱结点，除了根结点之外的所有结点都有且只有一个前驱结点；（2）树的结点可以有零个或多个后继结点。树结构描述的是层次关系。85.1.2基本术语

(a)树t (b)树t'

图5.2树t和树t'9

父结点，子结点，边

若结点y是结点x的一棵子树的根，则x称作y的父结点（或父母）；y称作x的子结点（或子女）；有序对<x，y>称作从x到y的边。例如树t中，C是E的父结点，E是C的子结点，<C，E>是从C到E的边（它对应着图中的有向线段CE）。

兄弟结点具有同一父母的结点彼此称作兄弟。树t中B，C，D互为兄弟，F，G互为兄弟，等等。注意，E和F并不是兄弟。

10

祖先，子孙若结点y在以结点x为根的一个子树（或树）中，且y≠x，则称x是y的祖先，y是x的子孙。例如树t中，A是其它各结点的祖先；C是E，H，I，J的祖先。

路径，路径长度如果x是y的一个祖先，又有x＝x0，x1，…，xn＝y，满足xi（i＝0，1，…，n-1）为xi+1的父结点，则称x0，x1，…，xn为从x到y的一条路径。n称为这条路径的长度。路径中相邻的两个结点可以表示成一条边。例如树t中A，C，E，I，J是从A到J的一条路径，其长度为4。11

结点的层数规定根的层数为0，其余结点的层数等于其父母结点的层数加1。例如t中，0层的结点是A，1层的结点有B，C，D，4层的结点是J。

树的深度或高度树中结点的最大层数称为树的深度或树的高度。例如树t中，树的深度为4。12

结点的度数、树的度数结点的子女个数叫作结点的度数。树中度数最大的结点的度数叫作树的度数。例如t中A，C，E，J的度数分别为3，1，2，0；t的度数为3

树叶、分支结点度数为0的结点称作树叶或终端结点；度数大于0的结点称作分支结点或非终端结点。例如树t中B，F，G，H，J都是树叶，其余结点都是分支结点。13

无序树、有序树对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。例如在图5.2中，按无序树的概念t和t'是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树。

结点的次序在有序树中可以从左到右地规定结点的次序。按从左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点，或直接称为长子，而把长子右边的结点称为次子。例如在t中结点B是结点A的长子，结点C是结点A的次子，是结点B的兄弟。

14树林：是m（m>=0）棵互不相交的树所组成的集合。就逻辑结构而言，任何一棵树是一个二元组Tree=(root,F),

其中root称为树的根结点，F是m（m0）棵子树构成的树林，F=(T1,T2,…,Tm),其中Ti=(ri,Fi)称作根root的第i棵子树；当m0时，在树根和其子树林之间存在下列关系:RF={<root,ri>|i=1,2,…,m,m>0}5.1.3树林155.1.4树的基本运算创建一棵空树

TreecreateTree(Nodep,Treet1,Treet2,…,Treeti)i=1,2,3,…判断某棵树是否为空

intisNull(Treet)求树中的根结点，若为空树，则返回一特殊值

Noderoot(Treet)

求某个指定结点的父结点，当指定结点为根时，返回一特殊值

Nodeparent(Nodep)

16

求树中某个指定结点的最左子结点，当指定结点为树叶时，返回一特殊值

NodeleftChild(Nodep)

求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值

NoderightSibling(Nodep)

树的周游：即按某种方式访问树中的所有结点，并使每个结点恰好被访问一次。175.1.5树的周游1.周游的定义:按某一规律系统的访问树中的所有结点，并使每个结点恰好被访问一次。2.周游的方法：按深度方向和按宽度方向周游。（I）按深度方向（以右图为例）

a.先根次序

b.中根次序

c.后根次序18a.先根次序(1,2,3,5,8,9,6,10,4,7)

（1）访问根结点；（2）从左到右按先根次序周游根结点的每棵子树。b.中根次序(2,1,8,5,9,3,10,6,7,4)

（1）按中根次序周游根结点的最左子树；（2）访问根结点；（3）从左到右按中根次序周游根结点的其它各子树。c.后根次序(2,8,9,5,10,6,3,7,4,1)

（1）从左到右按后根次序周游根结点的每棵子树;

（2）访问根结点。19（II）按宽度方向周游先访问层数为0的结点，然后从左到右逐个访问层数为1的结点，依此类推，直到访问完树中的全部结点。层次序列（1，2，3，4，5，6，7，8，9，10）201.先根（A,B,C,K,D,E,H,F,J,G)2.后根(B,K,C,A,H,E,J,F,G,D)5.1.6树林的周游215.2树和树林的存储表示5.2.1树的存储表示

5.2.2树林的存储表示

5.2.3树和树林的其它表示法*225.2.1树的存储表示

树的父指针表示法树的子表表示法树的长子-兄弟表示法23structParTreeNode /*树中结点结构*/{ DataType info; /*结点中的元素*/ int parent;/*结点的父结点位置*/};structParTree{ structParTreeNodenodelist[MAXNUM]; /*存放树中的结点*/ intn;/*树中结点的个数*/};typedefstructParTree*PParTree;树的父指针表示法用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：24

优点：a)容易找到父结点及其所有的祖先；

b)能找到结点的子女和兄弟；缺点：a)没有表示出结点之间的左右次序；

b)找结点的子女和兄弟比较费事。改进方法：按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列，如下图：25 (a) (b)

图5.5一棵树的父指针表示26树的子表表示法

结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示。structEdgeNode /*子表中节点的结构*/{ int nodeposition; structEdgeNode *link;};structChiTreeNode/*结点表中节点的结构*/{ DataType info; structEdgeNode *children;};27子表表示的树结构定义如下：structChiTree /*树结构*/{structChiTreeNodenodelist[MAXNUM];int root; /*根结点的位置*/int n;/*结点的个数*/}typedefstructChiTree*PChiTree;

求某个结点的最左子女运算很容易实现，找到结点的全部子女也很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是：合并若干个子树构成一个新树时（createTree_chitree操作）也要考虑多个结点表的合并问题，由于这些结点表通常用顺序方式表示，所以合并起来比较麻烦。2817

23

46

89

5图5.6树的子表表示法29

在树的每个结点中，除信息域外，增加指向其最左子女和右兄弟的指针。structCSNode; /*树中结点结构*/typedefstructCSNode*PCSNode;/*结点的指针类型*/structCSNode /*结点结构定义*/{ DataTypeinfo; /*结点中的元素*/ PCSNodelchild; /*结点的最左子女的指针*/ PCSNodersibling; /*结点的右兄弟的指针*/};typedefstructCSNode*CSTree; /*树类型定义*/树的长子-兄弟表示法30

tab

dce

h

i

j

f

g图5.7树的长子兄弟表法315.2.2树林的存储表示

父指针表示法子表表示法长子-兄弟表示法32树林的父结点表示方法3312

3

59

8

6

7树林的子表表示法34

tA

BDCE

H

J

K

F

G树林的长子兄弟表示法355.3二叉树5.3.1二叉树的基本概念

5.3.2二叉树的性质

5.3.3二叉树的基本运算

5.3.4二叉树的周游

5.3.5树、树林与二叉树的转换36二叉树：它是结点的有限集合，这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树”和“右子树”的二叉树组成。它的每一个结点至多有两棵子树，并且子树有左右之分，不能随意颠倒。5.3.1二叉树的基本概念37二叉树的基本形态：左子树右子树右子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点和左子树（4）有根结点和右子树（5）有根结点和左，右子树38

二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

（3）和（4）是两棵不同的二叉树，但作为树，它们是相同的。在二叉树中可定义类似树中的概念。39

满二叉树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作“满二叉树”。完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。40满二叉树完全二叉树41扩充二叉树：把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶）增加两个分支。42在扩充的二叉树里，新增加的外部结点的个数比原来的内部结点个数多1。

“外部路径长度”E：在扩充的二叉树里从根到每个外部结点的路径长度之和。“内部路径长度”I：在扩充的二叉树里从根到每个内部结点的路径长度之和。

E=I+2n

其中，n是内部结点的个数。43证明：当n=1时，I=0,E=2,此等式成立。设有n个内部结点的扩充二叉树，下式成立。

En=In+2n(1)

对于n+1个内部结点的扩充二叉树，去掉一个作为原来二叉树路径长度为K的内部结点，内部路径长度变为：In=In+1-K(2)

外部路径长度变为：En=En+1-2(K+1)+K=En+1-K-2

即：En+1=

En+K+2En+1=(In+2n)+K+2=(In+1-K)+2n+K+2=In+1+2(n+1)

代入（1）代入（2）44abceef45性质1.在非空二叉树的第i层上至多有2i个结点（i0）。归纳：i=0,结点数=1=20.

假设对于j(0ji),结点数至多有2j.

对于i=j+1,结点数至多为2*2j=2j+1.性质2.深度为k的二叉树至多有2k+1-1个结点（k0）。

KkM=mi2i

=2k+1-1i=0i=020+21+22+…+

2k5.3.2二叉树的性质46性质3.对任何一棵非空二叉树T，如果叶结点数为n0，度为2的结点数为n2，则n0=n2+1。

n0+n1+n2=所有

结点的度数和+1=n1+2*n2+1性质4.具有n个结点的完全二叉树的深度k为log2n.n=20+21+22+…+2k-1+mk=2k-1+mk

2k-1n2k+1-12k

n2k+1

klog2nk+1k=log2n47性质5.

如果对一棵有n个结点的完全二叉树按层次次序从1开始编号，则对任一结点i（1in)，有：

1）i=1，序号结点i是根；i>1,其双亲结点是i/2。

2）2in，序号为i的结点的左子女结点的序号为2i；

2i>n,序号为i的结点无左子女。

3）2i+1n，序号为i的结点的右子女结点的序号为2i+1;2i+1>n,序号为i的结点无右子女。48性质5的证明：对于（2）和（3）当i=1时，2i=2n，左子女结点的序号为2。2i+1=3n，右子女结点的序号为3。假设对于序号为j的结点，命题成立。对于i=j+1，其左子女结点的序号等于j的右子女结点的序号加1，即：2j+1+1=2(j+1)

其右子女结点的序号等于：2(j+1)+1根据（2）和（3），知的父结点为i/2.

完全二叉树的层次序列，反映了它的结构。49123jj+12j2j+12(j+1)2(j+1)+1505.3.3二叉树的基本运算创建一棵空二叉树；判断某棵二叉树是否为空；求二叉树的根结点，若为空，则返回一特殊值；求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值；求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，返回一特殊值；求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，返回一特殊值；二叉树的周游。515.3.4二叉树的周游二叉树的周游(TraversingBinaryTree)：

按某条搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。三种方式：先根次序(DLR)

对称序(LDR)

后根次序(LRD)DLR52ABDCEFIHG

图5.15二叉树先根次序ABDCEGFHI

后根次序DBGEHIFCA

对称序（中根次序）DBAEGCHFI53

对右图进行先根、后根和中根次序周游得到如下的结点序列：先根：-ab+cd

前缀表示后根：ab-cd+

后缀表示

(波兰表示法)

对称序：a-bc+d

中缀表示-+abcd图5.16表达式的二叉树表示54二叉树的周游算法递归算法先根次序中根次序后根次序二.非递归算法(用自定义的栈来代替系统的栈)先根次序中根次序后根次序1

2555.3.5树、树林与二叉树的转换

1.树、树林转换为二叉树执行步骤：（1）在所有相邻的兄弟结点之间连一条线；（2）对每个非终端结点，只保留它到其最左子女的连线，删去它与其它子女的连线；（3）以根结点为轴心，将整棵树进行旋转。树、树林二叉树56ABCKDEFGHJ图5.20树林转换为二叉树572.二叉树转换为树、树林执行步骤：（1）若某结点是其父母的左子女，则把该结点的右子女，右子女的右子女，……,都与该结点的父母用线连接起来；（2）去掉原二叉树中所有父母到右子女的连线。58ABDCEKHFJG图5.22二叉树转换为树林595.4二叉树的存储表示

5.4.1顺序表示

5.4.2链接表示

5.4.3二叉树的生成

5.4.4线索二叉树*60

用一组地址连续的存储单元按层次次序依次存储完全二叉树的结点。完全二叉树的层次序列反映了它的层次结构。5.4.1顺序表示ABCGFEDHIJABCDEFGHIJ

下标012345678961

对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。图514一般二叉树及其顺序表示62采用顺序表示，类型声明如下：

structSeqBTree/*顺序树类型定义*/{ DataType nodelist[MAXNODE]; int n; /*改造成完全二叉树后， 结点的个数*/}；typedefstructSeqBTree*PSeqBTree;635.4.2链接表示

二叉树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。64structBinTreeNode; /*二叉树中结点*/typedefstructBinTreeNode *PBinTreeNode;

/*结点的指针类型*/structBinTreeNode { DataTypeinfo; /*数据域*/ PBinTreeNodellink; /*指向左子女*/ PBinTreeNoderlink; /*指向右子女*/};typedefstructBinTreeNode*BinTree;typedefBinTree*PBinTree;65ABDCEFIHGtAB^C^EF^I^^H^^G^^D^

图5.15二叉树的二叉链表表示66tA

B

DC

E

FI

HG

图5.15三叉链表表示675.4.3二叉树的生成

周游是二叉树各种操作的基础，可以在周游过程中进行各种操作，如可以在周游过程中生成结点，从而建立一棵二叉树。例：读入字符序列：

ABD@@@CE@G@@FH@@I@@建立图5.13所示的二叉树，其中，@表示空结点。

算法5.5按先根序列创建二叉树68tAB^C^EF^I^^H^^G^^D^

图5.15二叉树的二叉链表表示5.4.4线索二叉树*

69保存遍历过程中得到的信息以供某些操作使用（1〕增加两个指针（2〕利用结构中的空链域，并设立标志。线索：指向结点前驱或后继的指针。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。按对称序线索化二叉树:按对称序周游二叉树，周游到那个结点对那个结点加线索。按对称序周游对称序穿线树:沿线索周游。70structThrTreeNode;typedefstructThrTreeNode *PThrTreeNode;structThrTreeNode/*结点类型*/{ DataTypeinfo; PThrTreeNodellink,rlink; intltag,rtag;};typedefstructThrTreeNode*ThrTree,/*树类型*/typedefThrTree*PThrTree;/*类型的指针类型*/71StructSeqStack

/*栈元素的类型为PThrTreeNode*/

{PThrTreeNodes[MAXNODE];int