先來(lái)了解一下二叉樹(shù)的基本定義與性質(zhì):

三臺(tái)網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司于2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。

二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分???。

二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根（root）的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)節(jié)點(diǎn)?。

首先來(lái)看看二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)

typedef struct Tree{

?char data;

struct Tree* LChild;

struct Tree* RChild;

}Tree,*LpTree;

接下來(lái)看看代碼

一：遞歸算法

代碼如下

#include#includetypedef struct Tree{

??? ?char data;

??? struct Tree* LChild;

??? struct Tree* RChild;

}Tree,*LpTree;

LpTree createNode(){

??? char data;

??? LpTree T;

??? scanf("%c",&data);

??? if(data=='*'){

???????? return NULL;

??? }

??? else{

???????? T=(LpTree)malloc(sizeof(Tree));

???????? T->data=data;

???????? T->LChild=createNode();

???????? T->RChild=createNode();

???????? return T;

??? }

}

//打印節(jié)點(diǎn)中的元素

void printCurNodeData(LpTree curData){

??? printf("%c\t",curData->data);



}

//遞歸法遍歷 先序遍歷

void xianXuBianLi(LpTree L){

??? if(L!=NULL){

??? printCurNodeData(L);

??? xianXuBianLi(L->LChild);

??? xianXuBianLi(L->RChild);

??? }

}

//遞歸法遍歷 中序遍歷

void zhongXuBianLi(LpTree L){

??? if(L!=NULL){

??? zhongXuBianLi(L->LChild);

??? printCurNodeData(L);

??? zhongXuBianLi(L->RChild);

??? }

}

//遞歸法遍歷 后序遍歷

void houXuBianLi(LpTree L){

??? if(L!=NULL){

??? houXuBianLi(L->LChild);

??? houXuBianLi(L->RChild);

??? printCurNodeData(L);

??? }

}

int main()

{

??? LpTree T;

??? T=createNode();

??? printf("先序遍歷:");

??? xianXuBianLi(T);

??? printf("\n中序遍歷:");

??? zhongXuBianLi(T);

??? printf("\n后序遍歷:");

??? houXuBianLi(T);

??? return 0;

}

遞歸遍歷算法結(jié)果如圖所示：

輸入ABC**DE*G**F***（其中*表示空子樹(shù)）若有不同需求，可將代碼中的*替換為其他

二：非遞歸算法

代碼如下

#include#includetypedef struct Tree{

??? ?char data;

??? struct Tree* LChild;

??? struct Tree* RChild;

}Tree,*LpTree;

LpTree createNode(){

??? char data;

??? LpTree T;

??? scanf("%c",&data);

??? if(data=='*'){

???????? return NULL;

??? }

??? else{

???????? T=(LpTree)malloc(sizeof(Tree));

???????? T->data=data;

???????? T->LChild=createNode();

???????? T->RChild=createNode();

???????? return T;

??? }

}

//非遞歸先序遍歷

void xianXuBianLi(LpTree L){

??? if(L!=NULL){

??? ??? //準(zhǔn)備棧

???????? struct Tree* stack[10];//存儲(chǔ)每次打印節(jié)點(diǎn)的位置

???????? int stackTop=-1;//棧頂標(biāo)記

???????? LpTree pMove=L;

???????? while(stackTop!=-1||pMove){

???????????? while(pMove){

???????????? //把路徑入棧+打印走過(guò)的節(jié)點(diǎn)

???????????? printf("%c\t",pMove->data);

???????????? stack[++stackTop]=pMove;

???????????? pMove=pMove->LChild;

???????? }

???????? if(stackTop!=-1){

???????????? pMove=stack[stackTop];//獲取棧頂元素

???????????? stackTop--;

???????????? pMove=pMove->RChild;

???????? }

??? }

??? }

??? else{

???????? return;

??? ??? }

}

//非遞歸中序遍歷

void zhongXuBianLi(LpTree L){

??? if(L!=NULL){

??? ??? //準(zhǔn)備棧

???????? struct Tree* stack[10];//存儲(chǔ)每次打印節(jié)點(diǎn)的位置

???????? int stackTop=-1;//棧頂標(biāo)記

???????? LpTree pMove=L;

???????? while(stackTop!=-1||pMove){

???????????? while(pMove){

???????????? stack[++stackTop]=pMove;

???????????? pMove=pMove->LChild;

???????????? }

???????????? //出棧

???????????? if(stackTop!=-1){

????????????????? pMove=stack[stackTop--];

????????????????? printf("%c\t",pMove->data);

????????????????? pMove=pMove->RChild;

???????????? }

??? }

??? }

??? else{

???????? return;

??? ??? }

}

//非遞歸后序遍歷

void houXuBianLi(LpTree L){

??? if(L!=NULL){

??? ??? //準(zhǔn)備棧

???????? struct Tree* stack[10];//存儲(chǔ)每次打印節(jié)點(diǎn)的位置

???????? int stackTop=-1;//棧頂標(biāo)記

???????? LpTree pMove=L;

???????? LpTree plastVisit=NULL;

???????? while(pMove){

???????????? stack[++stackTop]=pMove;

???????????? pMove=pMove->LChild;

???????? }

???????????? //出棧

???????? while(stackTop!=-1){

???????? pMove=stack[stackTop--];

???????? if(pMove->RChild==NULL||pMove->RChild==plastVisit)

???????? {

???????????? printf("%c\t",pMove->data);

???????????? plastVisit=pMove;

???????? }

???????? else

???????? {

???????????? //右邊未被訪問(wèn)

???????????? stack[++stackTop]=pMove;

???????????? pMove=pMove->RChild;

???????????? while(pMove){

????????????????? stack[++stackTop]=pMove;

????????????????? pMove=pMove->LChild;

??? ???????? }

???????? }

???????? }

??? }

??? else{

???????? return;

??? ??? }

}

int main()

{

??? LpTree T;

??? T=createNode();

??? printf("先序遍歷:");

??? xianXuBianLi(T);

??? printf("\n中序遍歷:");

??? zhongXuBianLi(T);

??? printf("\n后序遍歷:");

??? houXuBianLi(T);

??? return 0;

}

非遞歸遍歷算法結(jié)果如圖所示：

輸入ABC**DE*G**F***（其中*表示空子樹(shù)）若有不同需求，可將代碼中的*替換為其他

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遞歸遍歷算法與非遞歸遍歷算法-創(chuàng)新互聯(lián)
標(biāo)題來(lái)源：http://weahome.cn/article/deciho.html