遞歸思想在二叉樹遍歷中的應(yīng)用

李萍

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

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

中圖分類號：TP18；TP301.6 文獻標(biāo)識碼：A 文章編號：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 遞歸算法的描述

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

2 二叉樹遍歷算法

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

Int num（BTtree T）

{int leftnum，rightnum；

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

Else

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

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

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

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

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

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

（1） 根結(jié)點進棧

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

（3） 結(jié)點的右，左孩子（非空）進棧

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

算法描述如下：

void NLR（BiTree T）

{initstac（s）；// 初始化一個棧

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é)

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

參考文獻：

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

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

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

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

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

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

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