後序遍歷遞歸演算法

① 二叉樹遍歷的遞歸演算法（C程序，先序中序或後序）

那個 答案我用了不行 啊,報錯後改了運行沒結果

② 後序遍歷（ 用遞歸和非遞歸的方法一起都要）

我們的數據結構實驗也是這題，需要我把我的實驗報告給你參考下么！
我這里就只發這部分的代碼。
Status PreOrderTraverse(BiTree T)
{
//先序遍歷二叉樹T的遞歸演算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍歷二叉樹T的非遞歸演算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍歷二叉樹T的遞歸演算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍歷二叉樹T的非遞歸演算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//後序遍歷二叉樹T的遞歸演算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//後序遍歷二叉樹T的遞歸演算法
unsigned sign;//記錄結點從棧中彈出的次數
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到結點T時壓入其指針
push(1);//置標志為1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走過T的左子樹
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子樹都已走過
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
另外,團IDC網上有許多產品團購,便宜有口碑

③ 二叉樹的遍歷

遍歷概念

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

④ 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
}

⑤ 後序遍歷是什麼

對於題圖為後序遍歷為：DECBA。

後序遍歷（LRD）是二叉樹遍歷的一種，也叫做後根遍歷、後序周遊，可記做左右根。後序遍歷有遞歸演算法和非遞核塌陸歸演算法兩種。

後序遍歷首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、衫弊右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。即：

若二叉樹為空則結束返回，

否則：

（1）後序遍歷左子樹

（2）後序遍歷右子樹（3）訪問根結點

如右圖所示二改頃叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

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

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的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。