二叉树在C语言中的实现与应用汇总

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(" 栈空间太小！ 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(" 栈空间太小！ 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)"