c語言_構建一個靜態二叉樹實現方法

2020-01-26 14:07:16

字體：大中小

來源：轉載

供稿：網友

第一、樹的構建

定義樹結構

struct BTNode {   char data;   struct BTNode* pLChild;   struct BTNode* pRChild; };

靜態方式創建一個簡單的二叉樹

struct BTNode* create_list() {    struct BTNode* pA = (struct BTNode*)malloc(sizeof(BTNode));   struct BTNode* pB = (struct BTNode*)malloc(sizeof(BTNode));   struct BTNode* pC = (struct BTNode*)malloc(sizeof(BTNode));   struct BTNode* pD = (struct BTNode*)malloc(sizeof(BTNode));   struct BTNode* pE = (struct BTNode*)malloc(sizeof(BTNode));      pA->data = 'A';   pB->data = 'B';   pC->data = 'C';   pD->data = 'D';   pE->data = 'E';     pA->pLChild = pB;   pA->pRChild = pC;   pB->pLChild = pB->pRChild = NULL;    pC->pLChild = pD;   pC->pRChild = NULL;    pD->pLChild = NULL;   pD->pRChild = pE;    pE->pLChild = pE->pRChild = NULL;    return pA; }

第二、樹的三種遍歷

1. 先序遍歷

//先序輸出 void PreTravense(struct BTNode* pHead) {   if (NULL!= pHead)   {     printf("%c", pHead->data);     if (NULL!= pHead->pLChild)     {       PreTravense(pHead->pLChild);     }     if (NULL != pHead->pRChild)     {       PreTravense(pHead->pRChild);     }   } }

2. 中序遍歷

//中序輸出 void InTravense(struct BTNode* pHead) {   if (NULL != pHead)   {     if (NULL != pHead->pLChild)     {       PreTravense(pHead->pLChild);     }     printf("%c", pHead->data);          if (NULL != pHead->pRChild)     {       PreTravense(pHead->pRChild);     }   } }

3.后續遍歷

//后序輸出 void PostTravense(struct BTNode* pHead) {   if (NULL != pHead)   {     if (NULL != pHead->pLChild)     {       PreTravense(pHead->pLChild);     }         if (NULL != pHead->pRChild)     {       PreTravense(pHead->pRChild);     }     printf("%c", pHead->data);   } }

第三、最終運行測試

int main() {   printf("創建序列/n");   struct BTNode* pHead = create_list();    printf("先序輸出/n");   PreTravense(pHead);   printf("中序輸出/n");   InTravense(pHead);   printf("后序輸出/n");   PostTravense(pHead);   return 0; }