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

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

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

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

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

typedef struct Tree{

?char data;

struct Tree* LChild;

struct Tree* RChild;

}Tree,*LpTree;

接下來看看代碼

一：遞歸算法

代碼如下

#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é)點中的元素

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***（其中*表示空子樹）若有不同需求，可將代碼中的*替換為其他

二：非遞歸算法

代碼如下

#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){

??? ??? //準備棧

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

???????? int stackTop=-1;//棧頂標記

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

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

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

???????????? //把路徑入棧+打印走過的節(jié)點

???????????? 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){

??? ??? //準備棧

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

???????? int stackTop=-1;//棧頂標記

???????? 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){

??? ??? //準備棧

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

???????? int stackTop=-1;//棧頂標記

???????? 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

???????? {

???????????? //右邊未被訪問

???????????? 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***（其中*表示空子樹）若有不同需求，可將代碼中的*替換為其他

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

網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)二叉樹的遞歸遍歷算法與非遞歸遍歷算法-創(chuàng)新互聯(lián)
URL分享：http://jinyejixie.com/article40/deciho.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、建站公司、網(wǎng)站維護、動態(tài)網(wǎng)站、網(wǎng)站導航、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)