树森林及其应用

☞8.1树和森林的基本概念

8.2树的存储

8.3树的基本算法

8.4树的应用——B-树第8章树和森林及其应用树的定义：

树是由n(n≥0)个节点组成的有限集合，其中：⑴当n＝0时为空树；⑵当n＞0时，有且仅有一个特定的节点，称为树的根，其余节点可分为m(m>0)个互不相交的子集，其中每一个子集本身又是一棵树，并且称为根的子树。可见，树的定义也是递归定义。树结构中常用的基本术语父结点：若一个节点有子树，则该结点为父结点。孩子结点：一个结点子树的根。兄弟结点：同一个结点的孩子。层次：根结点的层次为1，其余结点的层次是其父结点的层次加1。ABCDEFGH高度（深度）：树中结点的最大层次数。度：一个结点的孩子数目是这个结点的度。如：图中A的度为2,B度为3.叶子结点：度为0的结点。分支结点：度不为0的结点。树的度：树中结点的最大的度。上图中树的度为3。有序树/无序树：兄弟结点之间的排列是否有序。ABCDEFGH注意：虽然树结构的图形表示形式和二叉树的图形表示形式有相似之处，但两者从本质上说是不同的－－二叉树中每个结点的孩子都有左右之分：左孩子、右孩子；而树不是。例：三个结点所构成的树。ABCCAB结论：二叉树和树是两种不同的数据结构。森林：

森林是m(m≥0)棵互不相交的树的集合。即：森林是多棵树。EFADCBJIHG8.1树和森林的基本概念☞8.2树的存储

8.3树的基本运算

8.4树的应用——B-树第8章树和森林及其应用☞8.2.1双亲表示法

8.2.2孩子表示法

8.2.3孩子兄弟表示法8.2树的存储dataparent数据

双亲

实现：定义结构数组存放树的结点，每个结点含两个域

数据域：存放结点本身信息

双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难.

其结点的结构如下：

typedefstructnode{datatypedata;intparent;}Tnode;6012345789dataparent0号单元不用或存结点个数如何找孩子结点abcdfehgiacdefghib01223555109双亲表示法的形式说明如下：

＃defineMAX_NODE_NUM

100typedefstructTnode{datatypedata;intparent;}PTNode;一棵树可以定义为:typedefstruct{PTNode

nodes[MAX_NODE_NUM];intnodeNum;/*结点数*/}Parentree;6012345789dataparent8.2.1双亲表示法

☞

8.2.2孩子表示法

8.2.3孩子兄弟表示法8.2树的存储实现：

(1)把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表；n个结点共有n个孩子链表（叶子结点的孩子链表为空表）。

(2)n个结点的数据和n个孩子链表的头指针组成一个顺序表。6012345789acdefghibdatafc23∧45∧978∧6∧如何找双亲结点abcdfehgi∧∧∧∧∧这种存储结构的形式说明如下：

typesetstructChildnode

//孩子链表结点的定义

{

intChild;

//该孩子结点在线性表中的位置

structChildnode*next;

//指向下一个孩子结点的指针}Childnode;typedefstruct

//顺序表结点的结构定义

{datatypedata;

//结点的信息

Childnode*Firstchild;

//指向孩子链表的头指

}Datanode;树的定义:

typedefstruct{Datanodenodes［MAX］; //顺序表

introot,num;

//该树的根结点在线性表中的位置和该树的结点个数

}Childtree;abcdfehgi8.2.1双亲表示法

8.2.2孩子表示法

☞

8.2.3孩子兄弟表示法8.2树的存储实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。特点：(1)操作容易

(2)破坏了树的层次abcdfehgiabcdefghi∧∧∧∧∧∧∧∧∧∧孩子兄弟表示法的类型定义如下：

typedefstructCSnode{datatypedata;//结点信息

structCSnode*Firstchild,*Nextsibling;

//第一个孩子,下一个兄弟}CSnode;

这种存储结构便于实现树的各种操作。

例如：如果要访问结点x的第i个孩子，则只要先从FirstChild域找到第一个孩子结点，然后沿着这个孩子结点的Nextsibling域连续走i-1步,便可找到x的第i个孩子。如果在这种结构中为每个结点增设一个Parent域，则同样可以方便地实现查找双亲的操作。8.1树和森林的基本概念

8.2树的存储☞8.3树的基本运算

8.4树的应用——B-树第8章树和森林及其应用☞8.3.1树(森林)与二叉树的转换

8.3.2树(森林)的遍历8.3树的基本运算ACBED树ABCDE二叉树A∧

∧BC∧D∧

∧E∧A∧

∧BC∧D∧∧E∧

A∧

∧

BC∧D∧

E∧对应存储存储解释解释8.3.1树(森林)与二叉树的转换☞

一、树转换为二叉树

二、森林转换为二叉树三、二叉树转换为树或森林

将一棵树转换为二叉树的方法是：(1)

树中所有相邻兄弟之间加一条连线。AEDCBHGF(2)

对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。(3)

以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。下图是树转换为二叉树的结果示意图。AEDCBHGFAEDCBHGF8.3.1树(森林)与二叉树的转换

一、树转换为二叉树

☞二、森林转换为二叉树三、二叉树转换为树或森林

森林转换为二叉树的方法如下：

(1)将森林中的每棵树转换成相应的二叉树。

(2)将各二叉树的根结点连在一起。ADCBJIHGEFDCFJIEABDCFHGJI8.3.1树(森林)与二叉树的转换

一、树转换为二叉树

二、森林转换为二叉树☞三、二叉树转换为树或森林

二叉树转换为树或森林，具体方法如下：

(1)若某结点

x是其父结点y

的左孩子，则把该结点x

的右孩子、右孩子的右孩子……都与y

用线连起来。

(2)删掉原二叉树中所有父结点与右孩子结点的连线。

DCIEABFHGJEFADCBJIHGxyyx8.3.1树(森林)与二叉树的转换☞

8.3.2树(森林)的遍历8.3树的基本运算☞一、树的遍历二、森林的遍历8.3.2树(森林)的遍历遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法：

先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；

后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点；

按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点。ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO讨论：若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：decbaabdecabcdebdcea1.

树的先序遍历二法相同；2.

树的后序遍历相当于对应二叉树的中序遍历；3.

树没有中序遍历，因为子树无左右之分。结论：

一、树的遍历☞二、森林的遍历8.3.2树(森林)的遍历先序遍历：若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历：若森林为空，返回；中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。ABCDEFGHJI讨论：若采用“先转换，后遍历”方式，结果是否相同？例：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG结论：森林的先序和中序遍历在两种方式下的结果相同。结论：当以二叉链表做树的存储结构时，树的先根序列和后根序列可借用二叉树的先序遍历和中序遍历的算法实现之；对于森林也一样。8.1树和森林的基本概念

8.2树的存储

8.3树的基本算法☞8.4树的应用——B-树第8章树和森林及其应用☞8.4.1B－树的概念

8.4.2B－树的查找

8.4.3B－树的插入

8.4.4B－树的删除8.4树的应用——B－树

与二叉排序树类似，可以定义一种“m叉排序树”，通常称为m阶B-树。

一棵m阶B-树，或者是一棵空树，或者是满足如下性质的树：每个结点最多有m棵子树、m-1个关键字；结点结构如下：nA0K1A1K2A2…KnAn其中：

①n为关键字个数，k1,k2,..,kn为n个按递增顺序排列的键值(关键字)；②A0,Al,A2,...,An为(n+1)个指针,用于指向该结点的(n+l)棵子树,即子树个数为(n+l)。A0所指向子树中的所有关键字的值均小于kl,An所指向子树中的所有关键字的值均大于kn,Ai(1≤i≤n-1)所指向子树中的所有关键字的值均大于ki且小于ki+1;（2）根结点至少有两棵子树；

（3）除根结点之外的所有非叶子结点至少有棵子树；（4）所有叶子结点出现在同一层上，并且不含信息，通常称为失败结点。失败结点为虚结点，在B-树中并不存在，指向它们的指针为空指针。引入失败结点是为了便于分析B-树的查找性能。说明：

(1)对于非根结点的所有分支结点,n(关键字的个数)的取值范围为-1≤n≤m-1。

(2)对于根结点,n的取值范围为1≤

n≤m－1。例如：在一棵4阶B-树中(m＝4)，每个结点的关键字个数最少为4/2－1=1(子树数目最少为4/2=2)，最多为4－1＝3(子树数目最多为m＝4)。一棵7阶B-树(m＝7)，根结点至少有2棵子树(1个关键字)，其余每个结点至少有「7/2=4棵子树(3个关键字)；所有非叶子结点最多有m＝7棵子树。1501301951251552709023540atbcdfgeh例：四阶B-树37580858.4.1B－树的概念☞

8.4.2B－树的查找

8.4.3B－树的插入

8.4.4B－树的删除8.4树的应用——B－树查找方法

在B-树上进行查找的过程与二叉排序树的查找类似。

(1)根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。

(2)若有k=ki,则查找成功,根据相应的指针即可取得记录；否则,若k在ki和ki+1之间,取指针Ai所指的结点;(3)重复这个查找过程,直到在某结点中查找成功,或在某结点处出现Ai

为空,查找失败.例如，在下图所示B_树中查找关键字80和38。1501301951251552709023540atbcdfgeh3758085性能分析

在B-树上进行查找需比较的结点数最多为B-树的高度,B-树的高度与B-树的阶m和关键字总数N有关,下面就来讨论它们之间的关系。

(1)根据B-树的定义,B-树的第一层(即根结点)的子树数至少为2个，第二层结点的子树数至少为2*┌m/2┐个,第三层结点的子树数至少为2*(┌m/2┐)2个,以此类推,若B-树的高度为h，第h层结点的空指针数至少为2*(┌m/2┐)h-1。非叶子结点的子树数至少为：根结点的子树数至少为2个另一方面，B-树中每个结点中的指针数＝关键字数＋1则所有结点中的指针数＝总关键字数＋1×结点数即：总指针数C2＝关键字总数N+所有结点数C4而空指针数C1＝总指针数C2－非空指针数C3，并且，除根结点外，每个结点都由一个非空指针指向，即所有结点数C4=非空指针数C3+1

从而得到：C1＝C2－C3＝N+C4－C3

＝N+C3+1－C3＝N+1即B-树中空指针数＝关键字总数＋1这与二叉树中的空指针数与关键字总数的关系相同。(3)综上所述,可得到如下不等式:N+1≥2*(┌m/2┐)h-1即空指针数应大于等于它所具有的最小值，求解后得：

h≤1+log┌m/2┐(N+1)/2

又：根据B-树的定义,m阶B-树的第一层(即根结点)的子树数最多为m个，第二层结点的子树数最多为m*m=m2个,……，则第h层结点的空指针数最多为mh个。即N+1≤mhh≥logm(N+1)由以上分析可知，m阶B-树的高度h为：

logm(N+1)≤h≤1+log┌m/2┐(N+1)/28.4.1B－树的概念

8.4.2B－树的查找☞

8.4.3B－树的插入

8.4.4B－树的删除8.4树的应用——B－树

在B-树中插入一个关键字k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个关键字。且要使插入的结点中的关键字个数≤m－1,将涉及到结点的“分裂"问题。插入方法

☞首先经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。☞对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字值个数不超过(m-l),直接把键值插就行了;否则需要把结点分裂成两个。分裂的方法：

取一新结点,把原结点上的关键字和k按升序排序后,从中间位置(即┌m/2┐之处)把关键字(不包括中间位置的关键字)成两部分,

☞左部分所含关键字放在旧结点中,☞

右部分所含关键字放在新结点中,☞中间位置键值连同新结点的存储位置插入到父亲结点中。☞如果父结点的键值个数也超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。例：已知一棵3阶B-树如图所示，要求插入52、20、49。614c50f48a25b5386e37d5870g98h5052f48a25b5386e614c37d5870g98h插入52首先查找插入位置5025b61420c5052f37d48a5386e5870g98h插入20

结点C需要分裂为两个结点(k1~k[m/2]-1)、(k[m/2]+1~km)，k[m/2]插入到其双亲结点中。61414620c1425b620c’495052插入4948a5870g98he49f50538652f’5386e5052f505249508653494853a5870g98h5250861425b637d20c’8.4.1B－树的概念

8.4.2B－树的查找

8.4.3B－树的插入☞

8.4.4B－树的删除8.4树的应用——B－树

若在B–树上删除一个关键字，则首先应找到该关键字所在的结点:

☞

若该结点为最下层的非终端结点，且其中的关键字数目不少于，则删除完成，否则要进行“合并”操作。

☞

若所删关键字为非终端结点中的Ki，则以指针Ai

所指子树中的最小关键字Y替代Ki，然后在相应的结点中删去Y。

nA0K1A1K2A2…KnAn例：删除4848a50f50anA0K1A1K2A2…KnAn25b5386e614c37d5870g98h51

下面重点讨论删除最下层的非终端结点中的关键字的情形，有三种可能：被删关键字所在结点中的关键字数目不小于，则只需从该结点中删去关键字Ki和相应指针Ai。例：3阶B-树中删去1448a25b5386e6c37d50f5870g98h14(2)被删关键字所在结点中的关键字数目等于

-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于-1，则需将其兄弟结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。48a25b86e