我們以這個二叉樹為例
1.構造二叉樹的鏈式存盤結構
1 struct BTNode{ 2 char data; //結點資料域 3 struct BTNode * pLchild; //左孩子指標-->指向左孩子 4 struct BTNode * pRchild; //右孩子指標-->指向右孩子 5 };View Code
2.靜態的創建二叉樹
struct BTNode * createBTree() { struct BTNode* pa = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pb = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pc = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pd = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pe = (struct BTNode*)malloc(sizeof(struct BTNode)); pa->data = https://www.cnblogs.com/wwww2/p/'A'; pb->data = https://www.cnblogs.com/wwww2/p/'B'; pc->data = https://www.cnblogs.com/wwww2/p/'C'; pd->data = https://www.cnblogs.com/wwww2/p/'D'; pe->data = https://www.cnblogs.com/wwww2/p/'E'; pa->pLchild = pb; pb->pLchild = pb->pRchild = NULL; pa->pRchild = pc; pc->pLchild = pd; pc->pRchild = NULL; pd->pLchild = NULL; pd->pRchild = pe; pe->pLchild = pe->pRchild = NULL; return pa; }View Code
3.先序遍歷二叉樹(遞回方式)
void preBTree(struct BTNode * PT) { if(PT!=NULL) { printf("%c\n",PT->data); preBTree(PT->pLchild); preBTree(PT->pRchild); } //先序訪問的步驟 //先訪問根節點 //再先序訪問左子樹 //再先序訪問右子樹 }View Code
3.中序遍歷二叉樹(遞回方式)
1 void midBTree(struct BTNode * PT) 2 { 3 //中序遍歷二叉樹的步驟 4 //中序遍歷左子樹 5 //訪問根節點 6 //中序遍歷右子樹 7 if(PT!=NULL) 8 { 9 if(PT->pLchild!=NULL) 10 { 11 midBTree(PT->pLchild);//中序遍歷左子樹 12 } 13 printf("%c\n",PT->data); //訪問根節點 14 if(PT->pRchild!=NULL) 15 { 16 midBTree(PT->pRchild);//中序遍歷右子樹 17 } 18 } 19 }View Code
4.后序遍歷二叉樹（遞回方式）
void lastBTree(struct BTNode * PT) { //后序遍歷二叉樹的步驟 //后序遍歷左子樹 //后序遍歷右子樹 //訪問根節點 if(PT!=NULL) { if(PT->pLchild!=NULL) { lastBTree(PT->pLchild); //后序遍歷左子樹 } if(PT->pRchild!=NULL) { lastBTree(PT->pRchild);//后序遍歷右子樹 } printf("%c\n",PT->data);//訪問根節點 } }View Code
完整代碼：
#include<stdio.h> #include<stdlib.h> //二叉樹的鏈式存盤結構 struct BTNode{ char data; struct BTNode * pLchild; struct BTNode * pRchild; }; struct BTNode * createBTree(); void preBTree(struct BTNode * PT); void midBTree(struct BTNode * PT); void postBTree(struct BTNode * PT); //主函式 int main() { struct BTNode *PT = createBTree(); preBTree(PT); printf("\n"); midBTree(PT); printf("\n"); postBTree(PT); } //后序遍歷二叉樹 void postBTree(struct BTNode * PT) { if(PT!=NULL) { if(PT->pLchild!=NULL) { postBTree(PT->pLchild); } if(PT->pRchild!=NULL) { postBTree(PT->pRchild); } printf("%c\n",PT->data); } } //中序遍歷二叉樹 void midBTree(struct BTNode * PT) { if(PT!=NULL) { if(PT->pLchild!=NULL) { midBTree(PT->pLchild); } printf("%c\n",PT->data); if(PT->pRchild!=NULL) { midBTree(PT->pRchild); } } } //后序遍歷二叉樹 void preBTree(struct BTNode * PT) { if(PT!=NULL) { printf("%c\n",PT->data); preBTree(PT->pLchild); preBTree(PT->pRchild); } //先訪問根節點 //再先序訪問左子樹 //再先序訪問右子樹 } //創建一個二叉樹 struct BTNode * createBTree() { struct BTNode* pa = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pb = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pc = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pd = (struct BTNode*)malloc(sizeof(struct BTNode)); struct BTNode* pe = (struct BTNode*)malloc(sizeof(struct BTNode)); pa->data = https://www.cnblogs.com/wwww2/p/'A'; pb->data = https://www.cnblogs.com/wwww2/p/'B'; pc->data = https://www.cnblogs.com/wwww2/p/'C'; pd->data = https://www.cnblogs.com/wwww2/p/'D'; pe->data = https://www.cnblogs.com/wwww2/p/'E'; pa->pLchild = pb; pb->pLchild = pb->pRchild = NULL; pa->pRchild = pc; pc->pLchild = pd; pc->pRchild = NULL; pd->pLchild = NULL; pd->pRchild = pe; pe->pLchild = pe->pRchild = NULL; return pa; }View Code
輸出結果：
A
B
C
D
E
B
A
D
E
C
B
E
D
C
A
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135932.html
標籤：其他