二叉樹的遞歸遍歷演算法

❶ 什麼叫遍歷演算法(最好有例子)

遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。

遍歷演算法概念延伸：

圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。

舉例：

遍歷二叉樹搜索路線：

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。

遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。

❷ 二叉樹遍歷的演算法實現

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。 根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問根結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之中（間）。
③ LRN：後序遍歷(PostorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。 1．先（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
2．中（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
3．後（根）序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。 用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild）；
③ printf(%c，T->data）； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder 計算中序遍歷擁有比較簡單直觀的投影法，如圖
⑴在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次（或第三次）經過結點時進行的，則是中序遍歷（或後序遍歷）。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
⑵上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前驅結點和一個後繼結點。為了區別於樹形結構中前驅（即雙親）結點和後繼（即孩子）結點的概念，對上述三種線性序列，要在某結點的前驅和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前驅結點是D，前序後繼結點是E；中序前驅結點是E，中序後繼結點是F；後序前驅結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前驅結點是A，後繼結點是E和F。
二叉鏈表基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
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就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼（遞歸演算法）： #include<iostream>#include<cstdio>#include<cmath>#include<iomanip>#include<cstdlib>#include<ctime>#include<algorithm>#include<cstring>#include<string>#include<vector>#include<list>#include<stack>#include<queue>#include<map>#include<set>usingnamespacestd;typedefintT;classbst{structNode{Tdata;Node*L;Node*R;Node(constT&d,Node*lp=NULL,Node*rp=NULL):data(d),L(lp),R(rp){}};Node*root;intnum;public:bst():root(NULL),num(0){}voidclear(Node*t){if(t==NULL)return;clear(t->L);clear(t->R);deletet;}~bst(){clear(root);}voidclear(){clear(root);num=0;root=NULL;}boolempty(){returnroot==NULL;}intsize(){returnnum;}TgetRoot(){if(empty())throwemptytree;returnroot->data;}voidtravel(Node*tree){if(tree==NULL)return;travel(tree->L);cout<<tree->data<<'';travel(tree->R);}voidtravel(){travel(root);cout<<endl;}intheight(Node*tree){if(tree==NULL)return0;intlh=height(tree->L);intrh=height(tree->R);return1+(lh>rh?lh:rh);}intheight(){returnheight(root);}voidinsert(Node*&tree,constT&d){if(tree==NULL)tree=newNode(d);elseif(ddata)insert(tree->L,d);elseinsert(tree->R,d);}voidinsert(constT&d){insert(root,d);num++;}Node*&find(Node*&tree,constT&d){if(tree==NULL)returntree;if(tree->data==d)returntree;if(ddata)returnfind(tree->L,d);elsereturnfind(tree->R,d);}boolfind(constT&d){returnfind(root,d)!=NULL;}boolerase(constT&d){Node*&pt=find(root,d);if(pt==NULL)returnfalse;combine(pt->L,pt->R);Node*p=pt;pt=pt->R;deletep;num--;returntrue;}voidcombine(Node*lc,Node*&rc){if(lc==NULL)return;if(rc==NULL)rc=lc;elsecombine(lc,rc->L);}boolupdate(constT&od,constT&nd){Node*p=find(root,od);if(p==NULL)returnfalse;erase(od);insert(nd);returntrue;}};intmain(){bstb;cout<<inputsomeintegers:;for(;;){intn;cin>>n;b.insert(n);if(cin.peek()==' ')break;}for(;;){cout<<inputdatapair:;intod,nd;cin>>od>>nd;if(od==-1&&nd==-1）break;b.update(od,nd);}}

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

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

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

二叉樹的結點結構是:
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
你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字

❺ 二叉樹的遍歷

遍歷概念

所謂遍歷(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∮∮

❻ 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

棗蘆 printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(6)二叉樹的遞歸遍歷演算法擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵凳滑帶二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若讓襲LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。