C語言之二叉樹的遍歷
0.寫在前面
認(rèn)識二叉樹結(jié)構(gòu)最簡單的方式就是遍歷二叉樹。所謂遍歷二叉樹就是按照某種特定的規(guī)則,對二叉樹的每一個節(jié)點進行訪問,且每個節(jié)點只訪問一次。
二叉樹遍歷的規(guī)則一般有四種:前序遍歷、中序遍歷、后序遍歷和層序遍歷。其中,前三種較為簡單且實現(xiàn)方式大同小異。
1.前序遍歷:先訪問根節(jié)點,再遍歷左右子樹;
2.中序遍歷:先遍歷左子樹,再訪問根節(jié)點,再遍歷右子樹;
3.后序遍歷:先遍歷左子樹,再遍歷右子樹,再訪問根節(jié)點。
簡單記憶:前(根,左,右)、中(左,根,右)、后(左,右,根)。
在遍歷二叉樹之前,首先得擁有一棵二叉樹。因為目前還沒有學(xué)習(xí)如何構(gòu)建二叉樹,所以此處我們用最原始的辦法——申請N個節(jié)點,將它們手動拼接為二叉樹。
typedef int BTDataType; //二叉樹節(jié)點的結(jié)構(gòu) typedef struct BTNode { BTDataType data; struct BTNode* left; struct BTNode* right; }BTNode; //定義一個申請新節(jié)點的函數(shù) BTNode* BuyBTNode(BTDataType data) { BTNode* newNode = (BTNode*)malloc(sizeof(BTNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { //手動申請節(jié)點加連接 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); n1->left = n2; n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; return 0; }
1.前序遍歷
前序遍歷:先訪問根節(jié)點,再訪問左子樹,再訪問右子樹;
void PrevOrder (BTNode* root)
為了更好的理解前序遍歷的規(guī)則,接下來展示一下詳細(xì)步驟。
步驟詳解
1.先訪問根節(jié)點 (data = 1),再訪問左子樹;
2.再訪問左子樹的根節(jié)點(data = 2),再訪問左子樹的左子樹;
3.依舊先訪問根節(jié)點(data = 3),此時 n3 節(jié)點的左右子樹都為 NULL ,則不再往下遞歸,回到上一層;接著訪問上一層的右子樹;
4.因為 n2 節(jié)點的右子樹為 NULL,所以繼續(xù)返回上一層;訪問上一層的右子樹;
5.訪問右子樹的根節(jié)點(data = 4),再訪問右子樹的左子樹;先左子樹的根節(jié)點(data = 5),n5 節(jié)點的左右子樹都為 NULL,返回上一層訪問右子樹(data = 6),同樣 n6 節(jié)點的左右子樹都為 NULL,返回上一層。
至此每個節(jié)點都訪問完畢,總體的訪問順序是這樣的:
按照訪問順序打印的結(jié)果應(yīng)該是(空節(jié)點用 NULL 表示):
代碼實現(xiàn)
按照前序遍歷的邏輯,前序遍歷的實現(xiàn)肯定是離不開遞歸。
void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL ");//空節(jié)點用 NULL 表示 return; } printf("%d ", root->data);//前序在前 PrevOrder(root->left); PrevOrder(root->right); }
運行程序,看結(jié)果是否與之前推理的結(jié)果一致:
int main() { //手動申請節(jié)點加連接 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); n1->left = n2; n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; PrevOrder(n1); return 0; }
2.中序遍歷
前中后序三種遍歷大同小異,實現(xiàn)代碼也幾乎相同。
void InOrder(BTNode* root)
步驟詳解
代碼實現(xiàn)
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PrevOrder(root->left); printf("%d ", root->data);//中序在中 PrevOrder(root->right); }
3.后序遍歷
步驟詳解
參考1、2。
代碼實現(xiàn)
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data);//后序在后 }
到此這篇關(guān)于C語言之二叉樹的遍歷的文章就介紹到這了,更多相關(guān)二叉樹的遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!