当前位置:主页   - 电脑 - 程序设计 - C/C++
数据结构C语言实现之二叉树
来源:网络   作者:    更新时间:2010-09-26
收藏此页】    【字号    】    【打印】    【关闭

  #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 initBTree(struct BTreeNode* *bt)
   {
   *bt = NULL;
   return;
   }
   /* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
   void createBTree(struct BTreeNode* *bt, char *a)
   {
   struct BTreeNode *p;
   struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
   int top = -1;/* 定义top作为s栈的栈顶指针,初值为-1,表示空栈 */
   int k;/* 用k作为处理结点的左子树和右子树,k = 1处理左子树,k = 2处理右子树 */
   int i = 0;/* 用i扫描数组a中存储的二叉树广义表字符串,初值为0 */
   *bt = NULL;/* 把树根指针置为空,即从空树开始建立二叉树 */
   /* 每循环一次处理一个字符,直到扫描到字符串结束符为止 */
   while(a[i] != ''){
   switch(a[i]){
   case ' ':
   break; /* 对空格不作任何处理 */
   case '(':
   if(top == STACK_MAX_SIZE - 1){
   printf("栈空间太小! ");
   exit(1);
   }
   top++;
   s[top] = p;
   k = 1;
   break;
   case ')':
   if(top == -1){
   printf("二叉树广义表字符串错误! ");
   exit(1);
   }
   top--;
   break;
   case ',':
   k = 2;
   break;
   default:
   p = malloc(sizeof(struct BTreeNode));
   p->data = a[i];
   p->left = p->right = NULL;
   if(*bt == NULL){
   *bt = p;
   }else{
   if( k == 1){
   s[top]->left = p;
   }else{
   s[top]->right = p;
   }
   }
   }
   i++; /* 为扫描下一个字符修改i值 */
   }
   return;
   }
   /* 3.检查二叉树是否为空,为空则返回1,否则返回0 */
   int emptyBTree(struct BTreeNode *bt)
   {
   if(bt == NULL){
   return 1;
   }else{
   return 0;
   }
   }
   /* 4.求二叉树深度 */
   int BTreeDepth(struct BTreeNode *bt)
   {
   if(bt == NULL){
   return 0; /* 对于空树,返回0结束递归 */
   }else{
   int 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(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 != NULL){
   printf("%c", bt->data); /* 输出根结点的值 */
   if(bt->left != NULL

其它资源
来源声明

版权与免责声明
1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
3、本站部分文章来源于本站原创,本站拥有所有权利。
4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
请参阅权责声明