a18-5.c

数据结构168个实验程序,很全面

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
struct tree                /*声明树的结构*/
 {struct tree *left;       /*存放左子树的指针*/
  char data;               /*存放节点数据内容*/
  struct tree *right;      /*存放右子树的指针*/
 };
typedef struct tree treenode; /*声明新类型树结构*/
typedef treenode *b_tree;     /*声明二叉树的链表*/
/*-------------------------------------------------------*/
/*       使用递归建立二叉树                              */
/*-------------------------------------------------------*/
b_tree create_btree(int *nodelist,int position)
 {b_tree newnode;          /*声明新节点指针*/
  if(nodelist[position]==0|| position>7)   /*递归的终止条件*/
       return NULL; 
  else
    {
     /*-------建立新节点的内存空间----*/
     newnode=(b_tree) malloc (sizeof (treenode));
     /*-------建立节点内容-------------*/
     newnode->data=nodelist[position];
     /*-------递归建立左子树----------*/
     newnode->left=create_btree(nodelist,2*position);
     /*--------递归建立右子树---------*/
     newnode->right=create_btree(nodelist,2*position+1);
     return newnode;
    }
  }
void preorder(b_tree point)
{ 
 if(point!=NULL)  /*遍历的终止条件*/
    {
 printf("%c",point->data);
 preorder(point->left);
 preorder(point->right);
    }
}
void inorder(b_tree point)
{ 
  if(point!=NULL)/*遍历的终止条件*/
 { inorder(point->left);/*处理左子树*/
   printf("%c",point->data);/*处理打印节点内容*/
   inorder(point->right);/*处理右子树*/
 }
}

void postorder(b_tree point)
{if(point!=NULL)
   {postorder(point->left);/*处理左子树*/
    postorder(point->right);/*处理右子树*/
    printf("%c",point->data);/*处理打印节点内容*/
}
}
int calculate(b_tree point)
{int oper1=0;
 int oper2=0;
 if(point->left==NULL && point->right==NULL)
 {return point->data-48;}
 else
   {oper1=calculate(point->left);
    oper2=calculate(point->right);
     return get_value(point->data,oper1,oper2);
   }
}

int get_value(int oper,int oper1,int oper2)  /*抽取运算值并计算*/
 { switch ((char) oper)
   {case '*' :  return(oper1*oper2);
    case '/' :   return(oper1/oper2);
    case '+' :   return(oper1+oper2);
    case '-' :  return(oper1-oper2);
   }
 }

void main()
{
b_tree root=NULL;/*声明表达式二叉树指针*/
int cal_result; /*计算结果*/
/*-----声明二叉树数组节点数据-----*/
int nodelist[8]={' ','+','*','/','4','8','6','2'};
root=create_btree(nodelist,1);/*建立表达式二叉树*/
printf("\nPreorder expression:[");
preorder(root);
printf("]\n");
printf("Inorder expression: [");
inorder(root);
printf("]\n");
printf("Postorder expression:[");
postorder(root);
printf("]\n");
/*---------计算表达式结果------*/
cal_result=calculate(root);
printf("\nCalulate result is [%2d]\n",cal_result);
}