先序遍歷遞歸演算法
㈠ 先序遍歷二叉樹的遞歸演算法怎樣理解（嚴蔚敏主編）
先序調用的時候，遞歸函數，先序函數會一直遞歸，直到t->next為空，即t為葉節點，需要注意的是當t->next 為空時，函數的實參沒有傳過去，所以t指向葉結點的父節點，更要注意的是，先序調用的遞歸函數還沒執行完，在先序調用的最里層，要執行這個函數的最後一個語句，即先序訪問右子樹。
在了解遞歸函數時，要注意函數是一層一層執行的，把沒有調用的函數看作哦是第一層，第一次調用的時候，，勢必會第二次遇到調用函數，變成第二層，，，，
㈡ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
㈢ 用遞歸演算法先序中序後序遍歷二叉樹
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);
}
}
(3)先序遍歷遞歸演算法擴展閱讀：
注意事項
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的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。
㈣ 二叉鏈表存儲二叉樹的先序遍歷演算法
二叉鏈表存儲二叉樹的先序遍歷演算法，通常採用遞歸的演算法實現。首先訪問二叉樹的根節點，然後遞歸遍歷它的左子樹，最後，遞歸遍歷他的右子樹。
㈤ 先序遍歷二叉樹的遞歸演算法怎樣理解
二叉樹的結點結構是:x0dx0a1、根結點（存放結點數據）x0dx0a2、左子樹指針x0dx0a3、右子樹指計x0dx0a對二叉樹的遍歷就是訪問各個結點中根結點里存放的數據。例如：x0dx0a 如果結點A有左結點B，右結點C，記作A(B,C)，不同結點我用"\"隔開。那麼有這樣一個(BitTree)二叉樹表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己畫出來，不然我後面白講了。x0dx0a 要想把所有的數據都訪問到則必需按照一定的原則，即當前結點的下一個結點是哪個結點。x0dx0a 無論是先、中還是後序演算法都是先將左結點視為下一個結點，當左結點不存在（即為空時）才將右結點視作下一個結點，如果右結點也不存在就返回當前結點的上層結點再向右訪問，如此類推。x0dx0a 於是對二叉樹的遍歷問題就被抽象成三個基本步驟:x0dx0a1、訪問根結點。x0dx0a2、訪問該點的所有左子樹。x0dx0a3、訪問該點的所有右子樹。x0dx0a 先序遍歷的策略是按123的步驟執行，中序是按213來，後序則是231,它們之間的不同只是「訪問根結點」在這三個步驟中的位置。x0dx0a 看著你剛畫好的那個清舉判BitTree跟著我的思路走。在先序遍歷演算法PriorOrder中,先將BitTree的頭結點A傳進來，按步驟123的處理。123是抽象實現，記住所表達的思想，下面是具體實現。為了避免混亂用中文數字記錄步驟。x0dx0a一、即是讀取結點A的數據內容A（此答悄時A為當前函數處理結點)，將A的右結點C放入棧S中，S中的內容為S（C）[注意這一步是演算法的一個輔助，並不是先向右訪問,下同]，將左結點B傳給PriorOrder處理。此時讀取了Ax0dx0a二、讀取B的內容B（此時B為當前結點），將B的右結點E放入S中，S中的內容為S(C,E),將B的左結點D傳給PriorOrder處理。此時讀取了ABx0dx0a三、D為當前結點，D的右為空沒有東西放入S，S中的內容仍為S(C,E)，D的左也為空，沒有訪問可訪問的。此時就從S中取出E(因為棧是先進後出的所以取的就是E，此時S中的內容為S(C),正好是上一層沒訪問過的右子樹)，將E傳給PriorOrder處理。此時讀取了AB Dx0dx0a四、E為當前結點，對於結點E類似的有S(C,G),讀取了ABDE,將F傳入PriorOrderx0dx0a五、F為當前結點，右為空，左也為空，讀取了ABDEF,從棧中取出G傳給PriorOrder處理,S的內容為S(C);x0dx0a六、類似的讀取了ABDEFG,從S中取出了C，傳給答改PriorOrder處理。此時S（）。x0dx0a七、當前結點為C，從將C的右結點放入S，S中內容為S(H),C的左為空，從S取出H，將H傳給PriorOrder處理。此時S為S().於是就讀取了ABDEFGCx0dx0a八，類似的讀取了ABDEFGCHx0dx0a九，最後ABDEFGCHFx0dx0a 你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字
㈥ 關於二叉樹先序遍歷的遞歸演算法問題
你把遞歸理解錯了，遞歸調用我用下面這種方法表示
Preorder->Preorder->Preorder->Preorder->Preorder->Preorder->Preorder
每一個Preoder都是去訪問一個節點的左子樹，當最後的葉子沒有左節點時，是最有一次調用棚告Preorder返回了，繼續倒數第老頌二次調用Preorder的代碼。如下
void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍歷二叉樹
if (T) {
visit(T->data); // 訪問結點
Preorder(T->lchild, visit); // 最後一次侍和鄭沒有左子樹了，返回到這里
Preorder(T->rchild, visit);// 繼續訪問右子樹
}
}
㈦ 在用遞歸演算法先序遍歷二叉樹時，當右子樹為空時，程序怎樣返回雙親節點去訪問雙親節點的右子樹，謝謝。
給你寫個比帶逗升較完整的代碼樣本：
typedefstructtreenode_s{
intdata;
structtreenode_s*left,*right;
}treenode_t;
typedefint(*treenode_cb_t)(treenode_t*node,void*arg);
/**
*遞歸先序遍歷二叉樹
*
*@paramroot樹的根節點指針
*@paramf指扒自定義的、用於訪問某節點的回調函數，且滿足條件：
*-返回負數表示失敗，否則表示成功。
*@paramarg無類型的指針，用於從外部傳遞任意參數給回調函數
蠢老*
*@return成功則返回成功遍歷的節點個數n；失敗則返回-1-n。
*/
intpreorder_traverse(treenode_t*root,treenode_cb_tf,void*arg){
intvisited=0;
intr;
if(!root)
return0;
if(f(root,arg)<0)
return-1;
visited++;
r=preorder_traverse(root->left,f,arg);
if(r<0)
returnr-visited;
visited+=r;
r=preorder_traverse(root->right,f,arg);
if(r<0)
returnr-visited;
visited+=r;
returnvisited;
}
//samplecode
intnode_print(treenode_t*node,void*arg){
int*index=(int*)arg;
print("%4d:%d
",*index,node->data);
++*index;
return0;
}
inttree_print(treenode_t*root){
intindex=0;
intr=preorder_traverse(root,node_print,&index);
returnr;
}
㈧ c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
㈨ 二叉樹遍歷的遞歸演算法（C程序，先序中序或後序）
那個 答案我用了不行 啊,報錯後改了運行沒結果
㈩ 誰來幫我看看這個遍歷二叉樹的遞歸演算法！先序輸入先序遍歷
兩個問題
第一：如果建侍仿明樹的時候樹是在MAIN函數里老告聲明的話，建樹大仔那個函數一定要有返回值，否則根據函數的特性，樹是空的，線序遍歷
第二：樹的初始化左，右孩子必須賦值為NULL，否則的話遍歷就會出現死循環