李萍

摘要：遞歸是程序設(shè)計(jì)中簡(jiǎn)化復(fù)雜問題的一種有力工具，可以將一個(gè)大的問題分解成同種類型小問題的迭代。該文介紹了遞歸的核心與特點(diǎn)，并以二叉樹的遍歷實(shí)現(xiàn)了遞歸的過程。

關(guān)鍵詞：遞歸；二叉樹遍歷；迭代

中圖分類號(hào)：TP18；TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）27-0039-02

Application of Recursion on Traversing the Binary Tree

LI Ping

（Department of Mathematics and Information Technology， Yuncheng University， Yuncheng 044000， China）

Abstract：Recursion is a powerful tool for simplifying comples problems in program design. It can decompose a large problem into some problems of the same type.The article introduces the core and feature of recursion and implements the recursive process by traversing the binary tree.

Key words： Recursion； the traversion of binary tree； iterate

1 遞歸算法的描述

在一個(gè)函數(shù)的定義中直接或間接調(diào)用自身就稱為函數(shù)的遞歸，該算法的本質(zhì)體現(xiàn)了“以此類推”“用同樣的步驟重復(fù)”這樣的思想，可以用簡(jiǎn)單的程序來解決某些復(fù)雜的計(jì)算問題，但是運(yùn)算量較大。以下為n的階乘經(jīng)典的遞歸算法描述遞歸程序的核心。

2 二叉樹遍歷算法

一棵非空二叉樹是由樹根和分別稱為左右子樹的二叉樹構(gòu)成，由二叉樹的定義可知存在遞歸的思想。所以在編寫與二叉樹相關(guān)的算法時(shí)，要謹(jǐn)記遞歸。例：求二叉樹結(jié)點(diǎn)的個(gè)數(shù)。

Int num（BTtree T）

{int leftnum，rightnum；

if（T==NULL） return 0；//遞減到空樹，不能再減二叉樹的結(jié)點(diǎn)個(gè)數(shù)為0個(gè)

Else

Leftnum=num（T→lchild）；//遞減，以同樣的方式求左子樹結(jié)點(diǎn)個(gè)數(shù)

Rightnum=num（T→rchild）；//遞減，以同樣的方式求右子樹結(jié)點(diǎn)個(gè)數(shù)

Return leftnum+rightnum+1；}返回左右子樹結(jié)點(diǎn)個(gè)數(shù)+根結(jié)點(diǎn)的1

遞歸求二叉樹結(jié)點(diǎn)個(gè)數(shù)的遞歸函數(shù)調(diào)用過程如圖1所示：

3 二叉樹先序遍歷非遞歸算法

非遞歸遍歷的基本思想如下：

（1） 根結(jié)點(diǎn)進(jìn)棧

（2） 結(jié)點(diǎn)出棧，被訪問

（3） 結(jié)點(diǎn)的右，左孩子（非空）進(jìn)棧

（4） 反復(fù)執(zhí)行2，3步，至棧為空

算法描述如下：

void NLR（BiTree T）

{initstac（s）；// 初始化一個(gè)棧

BiTNode *p； p=T；

if（T==NULL） print（“it is NULL”）；

else {

push（s，p）；

while（！Stackempty（s））

{p=&pop;（s）；

printf（“%d”，p→data）；

if（p→rchild！=NULL） push（s，p→rchild）；

if（p→lchild！=NULL） push（s，p→lchild）；}}

}

4 總結(jié)

遞歸求解問題的方式簡(jiǎn)化了程序設(shè)計(jì)，結(jié)構(gòu)清晰，易于理解。但是每執(zhí)行一次遞歸函數(shù)需要額外增加存儲(chǔ)空間。在不考慮空間的前提下應(yīng)用于二叉樹遍歷，掌握遞歸的核心，提高程序的可讀性。

參考文獻(xiàn)：

[1] 黃艷峰，陳偉.遞歸問題的Java實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2017（7）：27-28.

[2] 張建波.一種將遞歸過程轉(zhuǎn)換為非遞歸過程的方法研究[J].計(jì)算機(jī)教育，2017（8）：20-21.

[3] 朱朝霞.遞歸對(duì)自頂向下語(yǔ)法分析的影響[J].電腦知識(shí)與技術(shù)，2018（2）：146-147.

[4] 周法國(guó).基于遞歸的程序設(shè)計(jì)淺析[J].天津科技，2017（6）：20-21.

[5] 王軍.基于一道二叉樹習(xí)題的教學(xué)案例辨析[J].福建電腦，2017（5）：8-10.

[6] 卓明敏，卓文.非遞歸后序遍歷二叉樹二址棧法[J].福建電腦，2017（10）：3-5.

[通聯(lián)編輯：代影]