1、/*/二叉樹在 C 語言中的實現與應用/*/ #include <stdio.h>#include <stdlib.h> #define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType;#endif/*/ /* 以下是關于二叉樹操作的 11 個簡單算法 */*/ struct BTreeNode elemType data;struct BTreeNode *left; struct BTreeNode *right;/* 1. 初始化二叉樹 */void

2、 initBTree(struct BTreeNode* *bt)*bt = NULL;return;/* 2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立)*/void createBTree(struct BTreeNode* *bt, char *a)struct BTreeNode *p;struct BTreeNode *sSTACK_MAX_SIZE;/* 定義 s 數組為存儲根結點指針的棧使用 */int top = -1; /* 定義 top 作為 s 棧的棧頂指針，初值為 -1, 表示空棧 */int k; /* 用 k 作為處理結點的左子樹和右子樹， k = 1 處理左

3、子樹， k = 2 處理右子樹 */int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字符串，初值為 0 */*bt = NULL; /* 把樹根指針置為空，即從空樹開始建立二叉樹 */* 每循環一次處理一個字符，直到掃描到字符串結束符 0 為止 */while(ai != '0')switch(ai)case ' ':break; /* 對空格不作任何處理 */case '(':if(top = STACK_MAX_SIZE - 1)printf(" ?？臻g太??！ n");exit(1);top+; stop =

4、 p;k = 1;break; case ')':if(top = -1)printf(" 二叉樹廣義表字符串錯誤 !n"); exit(1); top-; break;case ',': k = 2; break; default: p = new BTreeNode ; p->data = ai;p->left = p->right = NULL; if(*bt = NULL) *bt = p;elseif( k = 1) stop->left = p;else stop->right = p;i+; /*

5、為掃描下一個字符修改 i 值 */ return;/* 3. 檢查二叉樹是否為空，為空則返回 1,否則返回 0 */ int emptyBTree(struct BTreeNode *bt)if(bt = NULL)return 1;elsereturn 0;/* 4. 求二叉樹深度 */int BTreeDepth(struct BTreeNode *bt)if(bt = NULL)return 0; /* 對于空樹，返回 0 結束遞歸 */ elseint dep1 = BTreeDepth(bt->left); /* int dep2 = BTreeDepth(bt->rig

6、ht); /* if(dep1 > dep2) return dep1 + 1;elsereturn dep2 + 1;計算左子樹的深度 */計算右子樹的深度 */若存在則返回元素存儲位置，否則返回空值 */* 5. 從二叉樹中查找值為 x 的結點， elemType *findBTree(struct BTreeNode *bt, elemType x) if(bt = NULL) return NULL;else if(bt->data = x) return &(bt->data);else /* 分別向左右子樹遞歸查找 */ elemType *p;if(p

7、= findBTree(bt->left, x) return p;if(p = findBTree(bt->right, x) return p; return NULL; /* 6. 輸出二叉樹 (前序遍歷) */ void printBTree(struct BTreeNode *bt) /* 樹為空時結束遞歸，否則執行如下操作 */ if(bt != NULL)printf("%c", bt->data); /* 輸出根結點的值 */ if(bt->left != NULL | bt->right != NULL) printf(&qu

8、ot;(");printBTree(bt->left); if(bt->right != NULL) printf(","); printBTree(bt->right); printf(")"); return;/* 7. 清除二叉樹，使之變為一棵空樹 */void clearBTree(struct BTreeNode* *bt)if(*bt != NULL) clearBTree(&(*bt)->left); clearBTree(&(*bt)->right); free(*bt);*bt =

9、 NULL;return;/* 8. 前序遍歷 */void preOrder(struct BTreeNode *bt) if(bt != NULL) printf("%c ", bt->data); /* preOrder(bt->left); /* preOrder(bt->right); /* return;訪問根結點 */ 前序遍歷左子樹 */ 前序遍歷右子樹 */* 9. 前序遍歷 */void inOrder(struct BTreeNode *bt) if(bt != NULL) inOrder(bt->left); /* print

10、f("%c ", bt->data); /* inOrder(bt->right); /* return;中序遍歷左子樹 */ 訪問根結點 */ 中序遍歷右子樹 */* 10. 后序遍歷 */ void postOrder(struct BTreeNode *bt) if(bt != NULL) postOrder(bt->left); /* postOrder(bt->right); /* printf("%c ", bt->data); /* return;后序遍歷左子樹 */ 后序遍歷右子樹 */ 訪問根結點 */*

11、11. 按層遍歷 */void levelOrder(struct BTreeNode *bt) struct BTreeNode *p;struct BTreeNode *qQUEUE_MAX_SIZE;int front = 0, rear = 0;/* 將樹根指針進隊 */ if(bt != NULL) rear = (rear + 1) % QUEUE_MAX_SIZE; qrear = bt;使隊首指針指向隊首元素 */ while(front != rear) /*隊列非空 */front = (front + 1) % QUEUE_MAX_SIZE; /* p = qfront;

12、 printf("%c ", p->data);/* 若結點存在左孩子，則左孩子結點指針進隊 */ if(p->left != NULL)rear = (rear + 1) % QUEUE_MAX_SIZE;#include <stdio.h> #include <stdlib.h> #define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType ;#endif /*/* 以下是關于二叉樹操作的 11 個簡單算法 */*/s

13、truct BTreeNodeelemType data ;struct BTreeNode *left ;struct BTreeNode *right ;/* 1. 初始化二叉樹 */void initBTree(struct BTreeNode* *bt)*bt = NULL ;return ;/* 2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立)*/ void createBTree(struct BTreeNode* *bt, char *a)struct BTreeNode *p;struct BTreeNode *sSTACK_MAX_SIZE;/* 定義 s 數組為存儲根

14、結點指針的棧使用 */int top = -1; /* 定義 top 作為 s 棧的棧頂指針，初值為 -1, 表示空棧 */int k ; /* 用k作為處理結點的左子樹和右子樹，k = 1處理左子樹，k = 2處理右子樹*/int i = 0 ; /* 用i掃描數組a中存儲的二叉樹廣義表字符串，初值為 0 */*bt = NULL ; /* 把樹根指針置為空，即從空樹開始建立二叉樹 */* 每循環一次處理一個字符，直到掃描到字符串結束符 0 為止 */ while(ai != '0')switch(ai)case ' ':break; /* 對空格不作任何處理

15、 */case '(':if( top = STACK_MAX_SIZE - 1 )printf(" ?？臻g太??！ n") ; exit(1) ;top+ ; stop = p ;k = 1 ;break;case ')':if(top = -1)printf(" 二叉樹廣義表字符串錯誤 !n"); exit(1); top- ;break ; case ',':k = 2;break; default: p = new BTreeNode ; p->data = ai ;p->left = p

16、->right = NULL ; if( *bt = NULL)*bt = p ;elseif( k = 1) stop->left = p ;else stop->right = p ;i+ ; /* 為掃描下一個字符修改 i 值 */ return;/* 3. 檢查二叉樹是否為空，為空則返回 1,否則返回 0 */ int emptyBTree(struct BTreeNode *bt)if(bt = NULL)return 1;elsereturn 0;/* 4. 求二叉樹深度 */int BTreeDepth(struct BTreeNode *bt)計算左子樹的深度

17、 */ 計算右子樹的深度 */ if(bt = NULL) return 0; /* 對于空樹，返回 0 結束遞歸 */ elseint dep1 = BTreeDepth(bt->left); /* int dep2 = BTreeDepth(bt->right); /* if(dep1 > dep2) return dep1 + 1; else return dep2 + 1; */* 5. 從二叉樹中查找值為 x 的結點，若存在則返回元素存儲位置，否則返回空值 elemType *findBTree(struct BTreeNode *bt, elemType x)if

18、(bt = NULL)return NULL;else if(bt->data = x) return &(bt->data);else /* 分別向左右子樹遞歸查找 */ elemType *p ;if(p = findBTree(bt->left, x)return p ;if(p = findBTree(bt->right, x)return p ;return NULL ;/* 6. 輸出二叉樹 (前序遍歷) */ void printBTree(struct BTreeNode *bt) */* 樹為空時結束遞歸，否則執行如下操作 if(bt != N

19、ULL) printf("%c ", bt->data); /*輸出根結點的值 */if(bt->left != NULL | bt->right != NULL) printf("(") ; printBTree(bt->left) ; if(bt->right != NULL) printf(",") ; printBTree(bt->right) ; printf(")"); return;/* 7. 清除二叉樹，使之變為一棵空樹 */ void clearBTree(st

20、ruct BTreeNode* *bt) if(*bt != NULL) clearBTree(&(*bt)->left) ; clearBTree(&(*bt)->right) ; free(*bt) ;*bt = NULL ;return ;/* 8. 前序遍歷 */void preOrder(struct BTreeNode *bt) 訪問根結點 */ 前序遍歷左子樹 */ 前序遍歷右子樹 */if(bt != NULL) printf("%c ", bt->data) ; /* preOrder(bt->left) ; /*

21、preOrder(bt->right) ; /* return ;/* 9. 中序遍歷 */ void inOrder(struct BTreeNode *bt) if(bt != NULL) inOrder(bt->left); /* printf("%c ", bt->data); /* inOrder(bt->right); /* return;中序遍歷左子樹 */ 訪問根結點 */ 中序遍歷右子樹 */* 10. 后序遍歷 */ void postOrder(struct BTreeNode *bt) if(bt != NULL) postO

22、rder(bt->left); /* postOrder(bt->right); /* printf("%c ", bt->data); /* return;后序遍歷左子樹 */ 后序遍歷右子樹 */ 訪問根結點 */* 11. 按層遍歷 */void levelOrder(struct BTreeNode *bt)struct BTreeNode *p;struct BTreeNode *qQUEUE_MAX_SIZE;int front = 0, rear = 0;/* 將樹根指針進隊 */if(bt != NULL)rear = (rear + 1)

23、 % QUEUE_MAX_SIZE; qrear = bt;while(front != rear) /*隊列非空 */front = (front + 1) % QUEUE_MAX_SIZE; /* p = qfront;printf("%c ", p->data);/* 若結點存在左孩子，則左孩子結點指針進隊 if(p->left != NULL)rear = (rear + 1) % QUEUE_MAX_SIZE; qrear = p->left;/* 若結點存在右孩子，則右孩子結點指針進隊 if(p->right != NULL)rear =

24、 (rear + 1) % QUEUE_MAX_SIZE; qrear = p->right;使隊首指針指向隊首元素 */*/*/return;/*/int main(int argc, char *argv) struct BTreeNode *bt ; /*指向二叉樹根結點的指針 */char *b ; /*用于存入二叉樹廣義表的字符串 */elemType x, *px ;initBTree(&bt) ; printf(" 輸入二叉樹廣義表的字符串： n") ;/* scanf("%s", b); */ b = "a(b(c), d(e(f, g), h(, i)"