数据结构之树型结构.docxVIP

高等学校精品课程

（第2版）

李云清杨庆红揭安全

人民邮电出版社

江西省高等学校精品课程

揭安全

E_mail:jieanquan@163.com

江西师范大学计算机信息工程学院

5递归与递归程序设计

在一个函数的定义中出现了对自己本身的调用 ,称之为直接递归；或者一个函数p的定义中包含了对函数q的调用，而q的实现过程又调用了p，即函数调用形成了一个环状调用链,这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。

退出

试编写一个函数，在第一行打印输出1个1，在第二行打印输出2个2，……在第n行打印输出n个n。例如，当n=5时，调用该函数的输出结果为：

1

22

333

4444

55555

该问题的算法为:

print(intn){inti;

if(n!=0)

{print(n-1);

for(i=1;i=n;i++)

printf(%d,n);printf(\n);

}}

退出

分析print(0)

分析

print(1)print(2)→for(i=1;i=1;i++printf(“%d”,1)

print(1)

print(2)

for(i=1;i=2;i++)printf(“%d”,2)递归print(4)print(3)Printf(“\n”);

for(i=1;i=2;i++)printf(“%d”,2)

递归

print(4)

print(3)

5!=0Printf(“\n”);→for(i=1;i=3;i++)

5!=0

printf(“%d”,3)

Printf(“\n”);

Printf(“\n”);

Print(5)for(i=1;i=4;i++)printf(“%d”,4)printf(“\n”);

Print(5)

for(i=1;i=5;i++)printf(“%d”,5)

printf(“\n”);

结束

退出

结论

n根据所求解问题的性质，将原问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。

n子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。

退出

第6章树型结构

树的基本概念

树类的定义

树的存储结构

树的遍历

树的线性表示

退出

6.1树的基本概念

树是由n(n≥0)个结点构成的有限集合，n=0的树称为空树；当n≠0时，树中的结点应该满足以下

两个条件：

(1)有且仅有一个特定的结点称之为根；

(2)其余结点分成m(m≥0)个互不相交的有限集合

T1,T2,……Tm，其中每一个集合又都是一棵树，称T1,T2,……Tm为根结点的子树。

退出

A

A

BCD

EFGHI

图6.1JK

有向树：

1)有确定的根；

2)树根和子树根之间为有向关系

1

234

5678910

11121314

1

365

3

65

2

24

78910

11

11121314

退出

和线性结构的比较

线性结构

第一个数据元素(无前驱)

最后一个数据元素(无后继)

其它数据元素

(一个前驱、一个后继))

树结构

根结点(无前驱)

多个叶子结点(无后继)

树中其它结点

(一个前驱、多个后继

退出

基本术语

结点:数据元素+若干指向子树的分支结点的度:分支的个数

树的度:树中所有结点的度的最大值叶子结点:度为零的结点（终点结点）

分支结点:度大于零的结点（非终端结点）

从根到结点的路径：

孩子结点、双亲结点、兄弟结点、祖先、子孙

结点的层次:假设根结点的层次为1,

第l层的结点的子树根结点的层次为l+1

退出

树A的高为4，度为3

第1层

第2层

第4层E

KL

叶子的度为0

A

BC

FG

叶子

根D的度为3

根

D

HIJ

M

子树(a)树形表示法

子树

退出

树的深度：树中叶子结点所在的最大层次森

林：是m（m≥0）棵互不相交的树的集合

任何一棵非空树