二叉樹的遍歷遞歸演算法

⑴ 二叉樹的遍歷

遍歷概念

所謂遍歷(Traversal)是指沿著某條搜索路線 依次對樹中每個結點均做一次且僅做一次訪問 訪問結點所做的操作依賴於具體的應用問題 遍歷是二叉樹上最重要的運算之一 是二叉樹上進行其它運算之基礎

遍歷方案

．遍歷方案 從二叉樹的遞歸定義可知 一棵非空的二叉樹由根結點及左 右子樹這三個基本部分組成 因此 在任一給定結點上 可以按某種次序執行三個操作 （ ）訪問結點本身(N) （ ）遍歷該結點的左子樹(L) （ ）遍歷該結點的右子樹(R) 以上三種操作有六種執行次序 NLR LNR LRN NRL RNL RLN 注意 前三種次序與後三種次序對稱 故只討論先左後右的前三種次序

．三種遍歷的命名 根據訪問結點操作發生位置命名 ① NLR 前序遍歷(PreorderTraversal亦稱(先序遍歷))——訪問結點的操作發生在遍歷其左右子樹之前 ② LNR 中序遍歷(InorderTraversal)——訪問結點的操作發生在遍歷其左右子樹之中(間) ③ LRN 後序遍歷(PostorderTraversal)——訪問結點的操作發生在遍歷其左右子樹之後 注意 由於被訪問的結點必是某子樹的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解釋為根 根的左子樹和根的右子樹 NLR LNR和LRN分別又稱為先根遍歷 中根遍歷和後根遍歷

遍歷演算法

．中序遍歷的遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( )遍歷左子樹 ( )訪問根結點 ( )遍歷右子樹

．先序遍歷的遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( ) 訪問根結點 ( ) 遍歷左子樹 ( ) 遍歷右子樹

．後序遍歷得遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( )遍歷左子樹 ( )遍歷右子樹 ( )訪問根結點

．中序遍歷的演算法實現 用二叉鏈表做為存儲結構 中序遍歷演算法可描述為 void InOrder(BinTree T) { //演算法里①~⑥是為了說明執行過程加入的標號 ① if(T) { // 如果二叉樹非空 ② InOrder(T >lchild) ③ printf( ％c T >data) // 訪問結點 ④ InOrder(T >rchild); ⑤ } ⑥ } // InOrder

遍歷序列

．遍歷二叉樹的執行蹤跡 三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示） 具體線路為 從根結點出發 逆時針沿著二叉樹外緣移動 對每個結點均途徑三次 最後回到根結點 ．遍歷序列 （ ） 中序序列 中序遍歷二叉樹時 對結點的訪問次序為中序序列【例】中序遍歷上圖所示的二叉樹時 得到的中序序列為 D B A E C F （ ） 先序序列 先序遍歷二叉樹時 對結點的訪問次序為先序序列【例】先序遍歷上圖所示的二叉樹時 得到的先序序列為 蔽拿衡 A B D C E F （ ） 後序序列 後宏做序遍歷二叉樹時 對結點的訪問次序為後序序列【例】後序遍歷上圖所示的二叉樹時 得到的後序序列為 D B E F C A 注意 （ ） 在搜索路線中 若訪問結點均是第一次經過結點時進行的 則是前序遍歷 若訪問結點均是在第二次(或第三次)經過結點時進行敏羨的 則是中序遍歷(或後序遍歷) 只要將搜索路線上所有在第一次 第二次和第三次經過的結點分別列表 即可分別得到該二叉樹的前序序列 中序序列和後序序列 （ ） 上述三種序列都是線性序列 有且僅有一個開始結點和一個終端結點 其餘結點都有且僅有一個前趨結點和一個後繼結點 為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念 對上述三種線性序列 要在某結點的前趨和後繼之前冠以其遍歷次序名稱 【例】上圖所示的二叉樹中結點C 其前序前趨結點是D 前序後繼結點是E 中序前趨結點是E 中序後繼結點是F 後序前趨結點是F 後序後繼結點是A 但是就該樹的邏輯結構而言 C的前趨結點是A 後繼結點是E和F

二叉鏈表的構造

． 基本思想 基於先序遍歷的構造 即以二叉樹的先序序列為輸入構造 注意 先序序列中必須加入虛結點以示空指針的位置 【例】建立上圖所示二叉樹 其輸入的先序序列是 ABD∮∮CE∮∮F∮∮

⑵ 先序遍歷二叉樹的遞歸演算法怎樣理解（嚴蔚敏主編）

先序調用的時候，遞歸函數，先序函數會一直遞歸，直到t->next為空，即t為葉節點，需要注意的是當t->next 為空時，函數的實參沒有傳過去，所以t指向葉結點的父節點，更要注意的是，先序調用的遞歸函數還沒執行完，在先序調用的最里層，要執行這個函數的最後一個語句，即先序訪問右子樹。
在了解遞歸函數時，要注意函數是一層一層執行的，把沒有調用的函數看作哦是第一層，第一次調用的時候，，勢必會第二次遇到調用函數，變成第二層，，，，

⑶ 遍歷二叉樹

遍歷方案：
1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍歷序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
A
/ \
B C
/ / \
D E F
圖
（1） 中序序列（inorder traversal）
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列（postorder traversal）
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
（4）層次遍歷（level traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右訪問每一個結點，從而實現對每一個結點的遍歷
注意：
（1）在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2）上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鏈表的構造
1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】
設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼(遞歸演算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]

⑷ 先序遍歷二叉樹的遞歸演算法怎樣理解

二叉樹的結點結構是:
1、根結點（存放結點數據）
2、左子樹指針
3、右子樹指計
對二叉樹的遍歷就是訪問各個結點中根結點里存放的數據。例如：
如果結點A有左結點B，右結點C，記作A(B,C)，不同結點我用"\"隔開。那麼有這樣一個(BitTree)二叉樹表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己畫出來，不然我後面白講了。
要想把所有的數據都訪問到則必需按照一定的原則，即當前結點的下一個結點是哪個結點。
無論是先、中還是後序演算法都是先將左結點視為下一個結點，當左結點不存在（即為空時）才將右結點視作下一個結點，如果右結點也不存在就返回當前結點的上層結點再向右訪問，如此類推。
於是對二叉樹的遍歷問題就被抽象成三個基本步驟:
1、訪問根結點。
2、訪問該點的所有左子樹。
3、訪問該點的所有右子樹。
先序遍歷的策略是按123的步驟執行，中序是按213來，後序則是231,它們之間的不同只是「訪問根結點」在這三個步驟中的位置。
看著你剛畫好的那個BitTree跟著我的思路走。在先序遍歷演算法PriorOrder中,先將BitTree的頭結點A傳進來，按步驟123的處理。123是抽象實現，記住所表達的思想，下面是具體實現。為了避免混亂用中文數字記錄步驟。
一、即是讀取結點A的數據內容A（此時A為當前函數處理結點)，將A的右結點C放入棧S中，S中的內容為S（C）[注意這一步是演算法的一個輔助，並不是先向右訪問,下同]，將左結點B傳給PriorOrder處理。此時讀取了A
二、讀取B的內容B（此時B為當前結點），將B的右結點E放入S中，S中的內容為S(C,E),將B的左結點D傳給PriorOrder處理。此時讀取了AB
三、D為當前結點，D的右為空沒有東西放入S，S中的內容仍為S(C,E)，D的左也為空，沒有訪問可訪問的。此時就從S中取出E(因為棧是先進後出的所以取的就是E，此時S中的內容為S(C),正好是上一層沒訪問過的右子樹)，將E傳給PriorOrder處理。此時讀取了AB D
四、E為當前結點，對於結點E類似的有S(C,G),讀取了ABDE,將F傳入PriorOrder
五、F為當前結點，右為空，左也為空，讀取了ABDEF,從棧中取出G傳給PriorOrder處理,S的內容為S(C);
六、類似的讀取了ABDEFG,從S中取出了C，傳給PriorOrder處理。此時S（）。
七、當前結點為C，從將C的右結點放入S，S中內容為S(H),C的左為空，從S取出H，將H傳給PriorOrder處理。此時S為S().於是就讀取了ABDEFGC
八，類似的讀取了ABDEFGCH
九，最後ABDEFGCHF
你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字