| 订阅 | 在线投稿
分享
 
 
当前位置: 王朝网络 >> c/c++ >> 数据结构C语言实现系列——二叉树
 

数据结构C语言实现系列——二叉树

2008-06-01 02:07:09 编辑來源:互联网 繁體版 评论
 
 
  Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid"

  #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; /* 把树根指针置为空,即从空树开始建立二叉树 */

  /* 每循环一次处理一个字符,直到扫描到字符串结束符\0为止 */

  while(a[i] != '\0'){

   switch(a[i]){

   case ' ':

   break; /* 对空格不作任何处理 */

   case '(':

   if(top == STACK_MAX_SIZE - 1){

   printf("栈空间太小!\n");

   exit(1);

   }

   top++;

   s[top] = p;

   k = 1;

   break;

   case ')':

   if(top == -1){

   printf("二叉树广义表字符串错误!\n");

   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 bt->right != NULL){

   printf("(");

   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 = 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); /* 中序遍历左子树 */

   printf("%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.按层遍历 */

  void levelOrder(struct BTreeNode *bt)

  {

  struct BTreeNode *p;

  struct BTreeNode *q[QUEUE_MAX_SIZE];

  int front = 0, rear = 0;

  /* 将树根指针进队 */

  if(bt != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = bt;

  }

  while(front != rear){ /* 队列非空 */

   front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */

   p = q[front];

   printf("%c ", p->data);

   /* 若结点存在左孩子,则左孩子结点指针进队 */

   if(p->left != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = p->left;

   }

   /* 若结点存在右孩子,则右孩子结点指针进队 */

   if(p->right != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = 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)))";

  createBTree(&bt, b);

  if(bt != NULL)

  printf(" %c ", bt->data);

  printf("以广义表的形式输出:\n");

  printBTree(bt); /* 以广义表的形式输出二叉树 */

  printf("\n");

  printf("前序:"); /* 前序遍历 */

  

   preOrder(bt);

  printf("\n");

  printf("中序:"); /* 中序遍历 */

  inOrder(bt);

  printf("\n");

  printf("后序:"); /* 后序遍历 */

  postOrder(bt);

  printf("\n");

  printf("按层:"); /* 按层遍历 */

  levelOrder(bt);

  printf("\n");

  /* 从二叉树中查找一个元素结点 */

  printf("输入一个待查找的字符:\n");

  scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */

  px = findBTree(bt, x);

  if(px){

   printf("查找成功:%c\n", *px);

  }else{

   printf("查找失败!\n");

  }

  printf("二叉树的深度为:");

  printf("%d\n", BTreeDepth(bt));

  clearBTree(&bt);

  return 0;

  }

  */
 
 
 
上一篇《在C语言中如何处理时间和日期》
下一篇《C++设计模式之Singleton》
 
 
 
 
 
 
日版宠物情人插曲《Winding Road》歌词

日版宠物情人2017的插曲,很带节奏感,日语的,女生唱的。 最后听见是在第8集的时候女主手割伤了,然后男主用嘴帮她吸了一下,插曲就出来了。 歌手:Def...

兄弟共妻,我成了他们夜里的美食

老钟家的两个儿子很特别,就是跟其他的人不太一样,魔一般的执着。兄弟俩都到了要结婚的年龄了,不管自家老爹怎么磨破嘴皮子,兄弟俩说不娶就不娶,老父母为兄弟两操碎了心...

如何磨出破洞牛仔裤?牛仔裤怎么剪破洞?

把牛仔裤磨出有线的破洞 1、具体工具就是磨脚石,下面垫一个硬物,然后用磨脚石一直磨一直磨,到把那块磨薄了,用手撕开就好了。出来的洞啊很自然的。需要猫须的话调几...

我就是扫描下图得到了敬业福和爱国福

先来看下敬业福和爱国福 今年春节,支付宝再次推出了“五福红包”活动,表示要“把欠大家的敬业福都还给大家”。 今天该活动正式启动,和去年一样,需要收集“五福”...

冰箱异味产生的原因和臭味去除的方法

有时候我们打开冰箱就会闻到一股异味,冰箱里的这种异味是因为一些物质发出的气味的混合体,闻起来让人恶心。 产生这些异味的主要原因有以下几点。 1、很多人有这种习...

 
 
 
Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid" #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; /* 把树根指针置为空,即从空树开始建立二叉树 */ /* 每循环一次处理一个字符,直到扫描到字符串结束符\0为止 */ while(a[i] != '\0'){ switch(a[i]){ case ' ': break; /* 对空格不作任何处理 */ case '(': if(top == STACK_MAX_SIZE - 1){ printf("栈空间太小!\n"); exit(1); } top++; s[top] = p; k = 1; break; case ')': if(top == -1){ printf("二叉树广义表字符串错误!\n"); 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 bt->right != NULL){ printf("("); 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 = 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); /* 中序遍历左子树 */ printf("%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.按层遍历 */ void levelOrder(struct BTreeNode *bt) { struct BTreeNode *p; struct BTreeNode *q[QUEUE_MAX_SIZE]; int front = 0, rear = 0; /* 将树根指针进队 */ if(bt != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = bt; } while(front != rear){ /* 队列非空 */ front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */ p = q[front]; printf("%c ", p->data); /* 若结点存在左孩子,则左孩子结点指针进队 */ if(p->left != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = p->left; } /* 若结点存在右孩子,则右孩子结点指针进队 */ if(p->right != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = 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)))"; createBTree(&bt, b); if(bt != NULL) printf(" %c ", bt->data); printf("以广义表的形式输出:\n"); printBTree(bt); /* 以广义表的形式输出二叉树 */ printf("\n"); printf("前序:"); /* 前序遍历 */ preOrder(bt); printf("\n"); printf("中序:"); /* 中序遍历 */ inOrder(bt); printf("\n"); printf("后序:"); /* 后序遍历 */ postOrder(bt); printf("\n"); printf("按层:"); /* 按层遍历 */ levelOrder(bt); printf("\n"); /* 从二叉树中查找一个元素结点 */ printf("输入一个待查找的字符:\n"); scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */ px = findBTree(bt, x); if(px){ printf("查找成功:%c\n", *px); }else{ printf("查找失败!\n"); } printf("二叉树的深度为:"); printf("%d\n", BTreeDepth(bt)); clearBTree(&bt); return 0; } */
󰈣󰈤
 
 
 
  免责声明:本文仅代表作者个人观点,与王朝网络无关。王朝网络登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述,其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
情人节的清纯女生(9)
情人节的清纯女生(8)
情人节的清纯女生(7)
情人节的清纯女生(6)
山东蓬莱海边组照
一探哲蚌 II
一探哲蚌 III
古长城的一角
 
>>返回首页<<
 
 
 为你推荐
 
 
 
 转载本文
 UBB代码 HTML代码
复制到剪贴板...
 
 热帖排行
 
 
 
 
©2005- 王朝网络 版权所有