信息学奥赛辅导资料 (2)

例3-2 利用算法exp_reducde对算术表达式3*（7-2）求值，操作过程如下所示。

????? 递归过程及其实现

栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通

过一系列的过程语句间接地调用自己的过程，称做递归过程。

例如， PROCEDURE A; BEGIN · · · A; · · · END; 过程A中的语句A直接调用了过程A本身，这叫做直接递归调用。又如： PROCEDURE B; PROCEDURE C; BEGIN BEGIN · · · · · · C; C; · · · · · · END; END; 在过程B中调用了过程C,而过程C又调用了过程B.这两个过程都通过另一个过程调用了它们自己, 这就叫做间接调用。

递归是程序设计中一个强有力的工具。

? 其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数 Fact(n)=1

若n = 1 Fact(n)= n·Fact(n-1) 若n >1 2阶Fibonacci数列 Fib(n)=0 若 n=0 Fib(n)=1 若n=1 Fib(n)=Fib(n-1)+Fib(n-2) 其它情形 和Ackerman函数

Ack(m,n)=n+1 m=0 Ack(m,n)=Ack(m-1,1) n=0 Ack(m,n)=Ack(m-1,Ack(m,n-1)) 其它情形等;

? 其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性,

则它们的操作可递归地描述;

其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题,Hanio塔问题等.

树

5.1 树的结构定义和基本操作

树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中： (1) 有且仅有一个特定的称为根的结点;

(2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集

5

合 本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根 结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交的子树：

树是一种数据结构 : Tree=(D,R) 其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上 个二元关系的集合，即R={H}。H为如下描述二元关系：

? (1) 在D中存在发唯一的称为根的数据元素,它在关系H下无前驱;

? (2) 若D-{root}≠φ，则存在D-{root}的一个划分D1,D2,...Dm(m>0),对任意一对

j≠k (l<=j,k<=m)有Dj∩Dk=φ，且对任意的i(l<=i<=m)，唯一存在数据元素Xi∈Di，有 ∈H;

? (3) 对应于D-{root}的划分，H-{ ,..., }有唯一的一个划分H1,H2,...，Hm(m>0),

对任意一对j≠k(l<=j,K<=m)有，Hj∩Hk=φ，且对任意的i(l<=i<=m)Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

树结构中的一些基本术语：

? 结点的度：结点拥有的子树数。 ? 叶子（终端结点）：度为零的结点。

? 非终端结点（分支结点）：度不为零的结点。 ? 树的度：树内各结点的度的最大值。 树的基本操作：

(1) INITIATE(T) 初始化操作，置T为空树。 (2) ROOT(T)\\ROOT(X) 求根函数。求数T的根或求结点x所在的树的根结点。若T是空树或X不在任何一棵树上，则函数值为“空”。 (3) RARENT(T,x) 求双亲函数。求树T中结点x的双亲结点。若结点x是树T的根结点或结点x不在T中，则函数值为“空”。

(4) CHILD(T,x,i) 求孩子结点函数。求数T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。 (5) RIGHT_SINLING(T,x)求右兄弟函数。求树T中结点x右边的兄弟。若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函树值为“空”。

(6) CRT_TREE(x,F) 建树操作。生成一棵以X结点为根，以森F为子树森林的树。

(7) INS_CHILD(y,i,x) 插入子树操作。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的子树个数>i-1，则空操作。

(8) DEL_CHILD(x,i) 删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数>i，则空操作。

6

(9) TRAVERSE(T) 遍历操作。按某个次序依此访问树中各个结点，并使每个结点只被访问一次。

(10) CLEAR(T) 清除结构操作。将树T置为空树。

5.2.1 二叉树定义与基本操作

二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子

树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒. 二叉树是一种数据结构 : Binary_tree=(D,R)

其中：D是具有相同特性的数据元素的集合;若D等于空,则R等于空称为空的二叉树;若D等于空则R是D上某个二元关系H的集合，即R={H}，且 (1) D中存在唯一的称为根的元素r，它的关系H下无前驱; (2) 若D-{r}不等于空，则D-{r}={Dl,Dr}，且Dl交Dr等于空;

(3) 若Dl不等于空,则在Dl中存在唯一的元素xl,〈r,xl〉属于H，且存在Dl上的关系Hl属于H；若Dr不等于空,则在Dr中存在唯一的元素xr,〈r,xr〉>属于H, 且存Dr上的关系Hr属于H；H={r,xl,＜r,xr＞,Hl, Hr};

(4) (Dl, Hl)是一棵合本定义的二叉树，称为根r的左子树,(Dr,Hr)是一棵符合定 义的二叉树，称为根的右子树。 其中，图6.2 是各种形态的二叉树.

(1)为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树 二叉树的基本操作：

(1)INITIATE(BT） 初始化操作。置BT为空树。

(2)ROOT(BT)\\ROOT(x) 求根函数。求二叉树BT的根结点或求结点x所在二叉树的根结点。若BT是空树或x不在任何二叉树上，则函数值为“空”。

(3)PARENT(BT,x) 求双亲函数。求二叉树BT中结点x的双亲结点。若结点x是二叉树 BT的根结点或二叉树BT中无x结点，则函数值为“空”。

(4)LCHILD(BT,x)和RCHILD(BT,x) 求孩子结点函数。分别求二叉树BT中结点x的左孩子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。

(5)LSIBLING(BT,x)和RSIBING(BT,x) 求兄弟函数。分别求二叉树BT中结点x的左兄弟和右兄弟结点。若结点x是根结点或不在BT中或是其双亲的左/右子树根,则函树值为“空”。 (6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点x为根，二叉树LBT和RBT分别为左，右子树的二叉树。

(7)INS_LCHILD(BT,y,x)和INS_RCHILD(BT,x) 插入子树操作。将以结点x为根且右子 树为空的二叉树分别置为二叉树BT中结点y的左子树和右子树。若结点y有左子树/右子树，则插入后是结点x的右子树。

(8)DEL_LCHILD(BT,x)和DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树BT中以结点x为根的左子树或右子树。若x无左子树或右子树，则空操作。

7

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。

(10)CLEAR(BT) 清除结构操作。将二叉树BT置为空树。

5.2.2 二叉树的存储结构

一 顺序存储结构

连续的存储单元存储二叉树的数据元素。例如图6.4(b)的完全二叉树, 可以向量(一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为i的结点的数据元素存放在分量bt[i]中,如图6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树,而一般二叉树也按这种形式来存储,这将造成存 贮浪费。如和图6.4(c)的二叉树相应的存储结构图6.6(b)所示，图中以“0”表示不存在此结点.

二 链式存储结构

由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成,则表 示二叉树的链表中的结点至少包含三个域:数据域和左右指针域,如图(b)所示。有时,为了便于找到结点的双亲,则还可在结点结构中增加一个指向其双亲受的指针域，如图6.7(c)所示。

5.3 遍历二叉树

8

遍历二叉树(traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。

5.3.1 前序遍历

前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍

历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：

按前序遍历此二叉树的结果为：Hello!How are you?

proc preorder(bt:bitreprtr) if (bt<>null)[ print(bt^);

preorder(bt^.lchild); preorder(bt^.rchild);] end;

5.3.2 中序遍历

中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。

中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：

按中序遍历此二叉树的结果为：a*b-c

proc inorder(bt:bitreprtr) if (bt<>null)[

inorder(bt^.lchild); print(bt^);

9

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新IT计算机信息学奥赛辅导资料 (2)全文阅读和word下载服务。