基于遍歷搜索二叉樹中最長路徑的算法研究

摘 要:在對二叉樹存儲結構進行分析的基礎上，介紹二叉樹遍歷算法的一種應用，即基于求解二叉樹深度算法設計實現的搜索二叉樹中最長路徑的算法。這里詳細介紹了搜索二叉樹中最長路徑問題的分析解決思路，在對可能的預期結果進行分析的基礎上，給出了算法的設計方案，同時給出了具體的C語言算法描述。

關鍵詞:二叉樹; 二叉樹遍歷; 完全二叉樹; 二叉樹的最長路徑; 二叉樹深度

中圖分類號:TP311.12文獻標識碼:A

文章編號:1004-373X(2010)08-0054-02

Algorithm of Searching Longest Path in Binary Tree Based on Traverse

WANG Min， ZJAO Xiao-lei

(Weinan Teachers University， Weinan714000， China)

Abstract:By analyzing the storage structure of binary tree， a kind ofapplication of binary tree traversal algorithm， that is，the algorithm ofsearching the longest path in binary tree， which is realized by solving the depth of binary tree， is introduced. The solution ideas of searching the longest path in binary tree are proposed in detail. The design scheme of the algorithm is given by analysing the expected results. The algorithm description in C language is presented.

Keywords:binary tree; binary tree traverse; complete binary tree; longest path in binary tree; depth of binary tree

0 引 言

二叉樹的邏輯結構為樹型結構，結點間是一對多的層次關系。所謂二叉樹的遍歷是指按一定規律對二叉樹中每個結點進行訪問且僅訪問一次[1-2]。“訪問”的含義很廣，可以是對結點作各種處理，如輸出結點的信息等[2，3]。二叉樹的遍歷是二叉樹中所有其他運算的基礎。

本文介紹了二叉樹遍歷在搜索二叉樹中最長路徑算法中的應用，重點分析算法的設計過程，并給出算法的C語言描述。

1 二叉樹的存儲結構

首先考慮二叉樹的存儲結構。接近完全二叉樹形態的二叉樹采用靜態向量的存儲方式比較好，此時結點的父子關系可根據完全二叉樹的性質5\\(對一棵有n個結點的完全二叉樹的結點按層序從1開始編號，則對任一序號大于1的結點i，其雙親結點序號為\\，若其左孩子序號小于n，則為2i，若其右孩子序號小于n，則為2i+1)定位對應的下標結點，其存儲結構可用C語言定義如下\\:

#define MAX 1000

typedef struct{

DataType data[MAX];

int datanum;

} SeqTree;

其中:data成員用于存儲結點的元素值;datanum成員用于記錄樹中結點的總個數。

對于非完全二叉樹，一般采用二叉鏈表方式存儲，其存儲結構如圖1所示。

圖1 二叉鏈表結點結構

可用C語言定義如下\\:

typedef struct node{

DataType data;

struct node *Lchild，*Rchild;

} Node， *BTree;

其中:data成員用于存儲結點的元素值;Lchild和Rchild成員分別為指向該結點中左右孩子結點的指針。下面介紹采用二叉鏈表存儲結構的算法。

2 搜索二叉樹中的最長路徑

所謂二叉樹中的最長路徑，一定是從根結點(位于第1層)到達樹中所在層次最大(也即樹的深度h層)的某個結點的一條路徑，于是，搜索該最長路徑的算法可以通過求解二叉樹的深度得以解決。

2.1 二叉樹的遍歷算法

對二叉樹進行遍歷的方式分前序、中序、后序和層序，前三種均是以訪問二叉樹中根結點(root)的次序作為命名的依據，第四種是從二叉樹的根開始逐層遍歷。這里主要介紹并利用后序遍歷算法，其遞歸算法設計思想如下:

(1) 若二叉樹為空，則遍歷過程結束;

(2) 否則;

① 后序遍歷根結點的左子樹;

② 后序遍歷根結點的右子樹;

③ 訪問根結點，算法結束[1，3-4，6-9]。

2.2 后序遍歷求解二叉樹的深度

求解二叉樹深度的遞歸算法思想可以描述為:

(1) 若二叉樹為空，則深度為0;

(2) 否則其深度應為根結點中左右子樹深度的最大值加1[1，10]。

在求解二叉樹深度的過程中，要對二叉樹進行遍歷。可以利用二叉樹中后序遍歷算法的設計思想實現這一過程。基于二叉鏈表存儲結構(BTree)的C語言算法描述如下:

int PostTreeDepth(BTree root)

{ int hl，hr，max;

if(root)

{hl=PostTreeDepth(root->Lchild);

hr=PostTreeDepth(root->Rchild);

max=hl>hr?hl:hr;

return (max+1); }

else

return 0;

}

2.3 搜索二叉樹中的最長路徑

搜索二叉樹中的最長路徑時，需要考慮以下因素:

首先，當二叉樹的最深層有兩個以上結點時，其最長路徑不止一條，此時只需要給出最先找到的一條即可。

其次，對于所求得的最長路徑應該如何記錄，這取決于問題的需求:

(1) 最簡單的需求是輸出該最長路徑。此時只需要在遍歷時輸出結點的值即可。

(2) 若問題的解決需要記錄該路徑，則需考慮如何對求得的路徑進行存儲，可采用以下幾種方案:

方案一:另外申請一個順序表結點空間用于存儲該路徑。

此時順序表中結點的結構可設計為如圖2所示。

圖2 路徑中的結點結構

圖2中data域用于存儲結點的元素值;tag域用于標記后繼結點是該結點的左孩子(設tag為0)，還是右孩子(設tag為1)。遍歷過程中，每確定路徑中一個結點，即將結點值填入順序表對應的位置，并設置其前驅結點的tag域。

方案二:另外申請二叉鏈表的結點空間，構成僅含一條單支的二叉樹。

此時路徑中結點的存儲結構與前述二叉鏈表存儲結構(BTree)相同。在二叉樹中，每確定路徑中一個結點后，需要進行以下步驟的操作:

① 為該結點申請新的結點空間;

② 將結點值填入新結點的data域，并設置新結點的Lchild和Rchild，指針為NULL;

③ 根據新結點是路徑中前驅結點的左孩子或右孩子，將新結點插入前驅結點中Lchild或Rchild指針的后面。

方案三:利用原二叉樹的二叉鏈表作出標記進行記錄。

這種方案需要對原二叉樹的二叉鏈表結構進行調整，在每個結點上增加一個tag域，用于標記該結點是否屬于搜索到的最長路徑。例如，若結點屬于最長路徑，則將該結點的tag域置1，否則為0。

下面僅以輸出所求得的最長路徑為例，給出搜索最長路徑的算法，該算法的遞歸設計思路如下:

(1) 若二叉樹為空，輸出空序列，算法結束;

(2) 否則，輸出根結點元素值，并求根結點的左右子樹深度，繼續執行第(3)步;

(3) 根據第(2)步求得的左右子樹深度，選擇深度大的一棵子樹，從其根結點開始求最長路徑。

假設樹中結點的元素值為字符型，即前述抽象數據類型DataType為char類型，則該遞歸算法中基于二叉鏈表存儲結構(BTree)上的C語言描述如下:

void SearchLongestPath(BTree root)

{ int hl，hr;//分別表示根結點左右子樹的深度

if(!root)

printf(\"%c\"，′/0′);//樹空則輸出空串

else {

printf(\"%c\"，root->data);//輸出根結點元素值

hl=PostTreeDepth(root->Lchild);

hr=PostTreeDepth(root->Rchild);

//調用求樹的深度的算法求根結點左右子樹深度

root=hl>=hr?root->Lchild:root->Rchild;

SearchLongestPath(root); }

}

3 結 語

二叉樹的遍歷是搜索最長路徑算法的基礎。

在搜索二叉樹的最長路徑過程中，依次訪問從根結點開始到達樹的最大層次的某個結點，算法的執行時間同樹的深度密切相關。求解二叉樹深度的過程涉及對二叉樹的后序遍歷，從而算法的遞歸調用次數同樹中結點的個數相關。

文中列出的所有算法的C語言程序均已通過上機測試。

參考文獻

[1]耿國華. 數據結構C語言描述[M]. 西安: 西安電子科技大學出版社， 2006.

[2]嚴海洲， 閆志遠. 二叉樹的遍歷及其應用實例[J]. 電腦知識與技術， 2003(5): 43-46.

[3]嚴蔚敏， 吳偉民. 數據結構[M]. 北京: 清華大學出版社，2000.

[4]朱站立， 劉天時. 數據結構使用C語言[M]. 2版. 西安: 西安交通大學出版社，1999.

[5]朱濤. 基于遍歷二叉樹的方法判斷完全二叉樹[J]. 紅河學院學報， 2005(6): 47-48.

[6]陳朋. 后序遍歷二叉樹的遞歸和非遞歸算法[J]. 安慶師范學院學報: 自然科學版， 2005， 11(2): 106-107.

[7]劉洋. 一種統一的二叉樹結構遍歷算法及其實現[J]. 贛南師范學院學報， 2004(3): 10-13.

[8]尹德輝， 孟林， 李忠. 二叉樹后序遍歷的非遞歸化算法討論[J]. 西南民族大學學報: 自然科學版， 2003， 29(5): 537-538.

[9]徐鳳生， 李立群， 馬夕榮. 二叉樹遍歷的通用非遞歸算法[J]. 福建電腦， 2006(6): 121， 41.

[10]徐孝凱. 數據結構簡明教程[M]. 北京: 清華大學出版社， 1995.