二叉樹的中序遍歷演算法
1. 用遞歸演算法先序中序後序遍歷二叉樹
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);
}
}
(1)二叉樹的中序遍歷演算法擴展閱讀：
注意事項
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的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。
2. 二叉樹遍歷
......1
..../....\
..2.......3
./....../...\
4......5.....6
........\
.........7
根結點為1,則左為42,右5736,再看先根序列24 3576;
左邊42在先根序列中以2為先,則1的下一層為2,再看中根序列42,所以4在2的右邊;
右邊5736在先根序列中以3為先,則3的左邊是57,右邊是6;
在先根序列中5先於7,在中根序列中7在5的右邊;
據此可作上圖
再由上圖寫出後根序列:4275631
答案為:B
3. 二叉樹中序遍歷的非遞歸演算法
推薦這篇文章，把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
4. 二叉樹的遍歷
遍歷概念
所謂遍歷(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∮∮
5. 二叉樹中序遍歷遞歸演算法
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍歷二叉樹
這段程序我全有，具體如下：
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree //定義二叉樹
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//
BiNode * new()//為新結點開辟空間
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)//創建新有子樹
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)//創建新結點
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)//輸出
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍歷
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍歷
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}