先序遍歷

先序遍歷可以想象為，一個(gè)小人從一棵二叉樹的根節(jié)點(diǎn)為起點(diǎn)，沿著二叉樹的外沿，逆時(shí)針走一圈回到根節(jié)點(diǎn)，路上遇到的元素順序，就是先序遍歷的結(jié)果

先序遍歷的結(jié)果為：A B D H I E J C F K G

中序遍歷

中序遍歷可以看成，二叉樹每個(gè)節(jié)點(diǎn)，垂直方向投影下來（可以理解為每個(gè)節(jié)點(diǎn)從最左邊開始垂直掉到地上），然后從左往右數(shù)，得出的結(jié)果便是中序遍歷的結(jié)果
中序遍歷的結(jié)果是：H D I B E J A F K C G

后序遍歷

后序遍歷就像是剪葡萄，我們要把一串葡萄剪成一顆一顆的。就是圍著樹的外圍繞一圈，如果發(fā)現(xiàn)一剪刀就能剪下的葡萄（必須是一顆葡萄）（也就是葡萄要一個(gè)一個(gè)掉下來，不能一口氣掉超過1個(gè)這樣），就把它剪下來，組成的就是后序遍歷了

后序遍歷的結(jié)果是：H I D J E B K F G C A

層次遍歷

層次遍歷就是從根節(jié)點(diǎn)開始，一層一層，從上到下，每層從左到右，依次寫值就可以
層次遍歷的結(jié)果是：A B C D E F G H I J K

解釋跑外圈的意思:

繞著外圍跑一整圈的真正含義是：遍歷所有節(jié)點(diǎn)時(shí)，都先往左孩子走，再往右孩子走

口訣：
先序遍歷：先根，再左，再右
中序遍歷：先左，再根，再右
后序遍歷：先左，再右，再根
（這里的根，指的是每個(gè)分叉子樹的根節(jié)點(diǎn)，并不只是最開始頭頂?shù)母?jié)點(diǎn)，需要靈活思考理解）

代碼展示：

#include<stdio.h> #include<stdlib.h>typrdef struct Tree{int data;//存放數(shù)據(jù)域 struct Tree *lchild;//遍歷左子樹指針 struct Tree *rchild;//遍歷右子樹指針 }Tree,*BitTree;BitTree CreateLink() {int data;int temp;BitTree T;scanf("%d",&data);//輸入數(shù)據(jù) temp=getchar();//吸收空格if(data==-1){return NULL;//輸入-1代表此節(jié)點(diǎn)下子樹不存數(shù)據(jù)，也就是不繼續(xù)遞歸創(chuàng)建 }else{T=(BitTree)malloc(sizeof(Tree));//分配內(nèi)存空間 T->data=data;//把當(dāng)前輸入的數(shù)據(jù)存入當(dāng)前節(jié)點(diǎn)指針的數(shù)據(jù)域中 printf("請(qǐng)輸入%d的左子樹：",data);T->lchild=CreateLink();//開始遞歸創(chuàng)建左子樹 printf("請(qǐng)輸入%d的右子樹：",data);T->rchild=CreateLink();//開始到上一級(jí)節(jié)點(diǎn)的右邊遞歸創(chuàng)建左右子樹 return T;//返回根節(jié)點(diǎn) } }//先序遍歷 void ShowXianXu(BitTree T)//先序遍歷二叉樹 {if(T==NULL) return;//遞歸中遇到NULL,返回上一層節(jié)點(diǎn) printf("%d ",T->data);ShowXianXu(T->lchild);//遞歸遍歷左子樹 ShowXianXu(T->rchild);//遞歸遍歷右子樹 }//中序遍歷 void ShowZhongXu(BitTree T) {if(T==NULL) return;//遞歸中遇到NULL，返回上一層節(jié)點(diǎn) ShowZhongXu(T->lchild);//遞歸遍歷左子樹printf("%d ",T->data);ShowZhongXu(T->rchild);//遞歸遍歷右子樹 }//后序遍歷 void ShowHouXu(BitTree T) {if(T==NULL) return;//遞歸中遇到NULL，返回上一層節(jié)點(diǎn)ShowHouXu(T->lchild);//遞歸遍歷左子樹 ShowHouXu(T->rchild);//遞歸遍歷右子樹 printf("%d ",T->data); }int main() {BitTree S;printf("請(qǐng)輸入第一個(gè)節(jié)點(diǎn)的數(shù)據(jù):\n");S = CreateLink();//接受創(chuàng)建二叉樹完成的根節(jié)點(diǎn) printf("先序遍歷結(jié)果: \n");ShowXianXu(S);//先序遍歷二叉樹 printf("\n中序遍歷結(jié)果: \n");ShowZhongXu(S);//中序遍歷二叉樹 printf("\n后序遍歷結(jié)果: \n");ShowHouXu(S);//后序遍歷二叉樹 return 0; }

樹結(jié)點(diǎn)定義：

typedef struct TNode *Position; typedef Position BinTree;//二叉樹類型 struct TNode{ElementType Data;BinTree Left;BinTree Right; };

先序遍歷：

• 先訪問根節(jié)點(diǎn)
• 先序遍歷其左子樹
• 先序遍歷其右子樹

void PreorderTraversal(BinTree BT) {if(BT){printf("%d",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);} }

中序遍歷：

• 先序遍歷其左子樹
• 先訪問根節(jié)點(diǎn)
• 先序遍歷其右子樹

void InorderTraversal(BinTree BT) {if(BT){InorderTraversal(BT->Left);printf("%d",BT->Data);InorderTraversal(BT->Right);} }

后序遍歷：

• 先序遍歷其左子樹
• 先序遍歷其右子樹
• 先訪問根節(jié)點(diǎn)

void PostorderTraversal(BinTree BT) {if(BT){PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf("%d",BT->Data);} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的二叉树先序，中序，后序，层次遍历（数据结构）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。