构造树

<meta http-equiv="Content-Type" content="text/html; charset=gb2312">

include "stdio.h"#include "stdlib.h"#include "conio.h"#include "string.h"#define MAX 20/************************************** 定义树的结构体***************************************/typedef struct tagtree{ char data;                /*数据域*/ int flag;                 /*非递归操作时用来做标志*/ struct tagtree*lchild;    /*指向左孩子的指针域*/ struct tagtree*rchild;    /*指向右孩子的指针域*/}tree;/******************************************** 用括号表示法输出树**********************************************/void OutTree(tree *root){ if(root != NULL) {  printf("%c",root->data);       /*先输出根结点*/  if(root->lchild != NULL || root->rchild != NULL)  {   printf("(");   OutTree(root->lchild);        /*处理左子树*/   if(root->rchild != NULL)   {    printf(",");   }  OutTree(root->rchild);         /*处理右子树*/  printf(")");}}}/************************************************ 用树形表示法输出树*************************************************/void DispTree(tree *root,int x,int y,int n)     /*n用来控制第一层树的高度*/{ int i=0; if(root !=NULL)  {    gotoxy(x,y);                       /*到相应结点输出*/    printf("%c",root->data);    if(root->lchild != NULL)          /*处理左子树，这里只有第一次N为可变的，*/    {       i=1;                            /*为的是能够输出整棵树，而不会被覆盖，*/       while(ilchild,x-n,y+n,2);       /*递归处理左子树*/     }     if(root->rchild != NULL)    {       i=1;       while(irchild,x+n,y+n,2);       /*递归处理右子树*/     }   }}/**************************************** 根据前缀和中缀表达式构造二叉树*****************************************/tree* PreCreateTree(char*pre,char *mid,int n){ tree*root = NULL; int i=0; if(n==0) return NULL; root=(tree*)malloc(sizeof(tree)); while(i<n root-=""></n>data=pre[0]; root->lchild=PreCreateTree(pre+1,mid,i); root->rchild=PreCreateTree(pre+i+1,mid+i+1,n-i-1); return root;}/**************************************** 根据后缀和中缀表达式构造二叉树*****************************************/tree*PostCreateTree(char *post,char *mid,int n){ tree*root=NULL; int lp=0; if(n==0) return NULL; while(lp<n root-="" root="(tree*)malloc(sizeof(tree));"></n>data = post[n-1]; /*printf("\n%c",root->data); getch();*/ root->lchild = PostCreateTree(post,mid,lp); root->rchild = PostCreateTree(post+lp,mid+lp+1,n-lp-1); return root;}void main(){ tree *root; char pre[20],mid[20]; printf("Input the pre string:"); gets(pre); printf("\nInput the mid string:"); gets(mid); root=PreCreateTree(pre,mid,strlen(mid)); printf("\nthe result is:"); DispTree(root,10,10,5); getch();}