《二叉树转双向链表 和 中缀转二树》由会员分享，可在线阅读，更多相关《二叉树转双向链表 和 中缀转二树（9页珍藏版）》请在金锄头文库上搜索。
1、#include #include #include #include typedef char elemtype; struct bnode elemtype data;struct bnode *lchild,*rchild; ; const N=10; struct bnode *sN; int h=-1,r=-1,k=0; struct bnode *set_tree() struct bnode *t,*p,*q;int i;char d;t=new(bnode); t-data=rand() % 26 + A;t-lchild=NULL; t-rchild=NULL;for (i=
2、1;ip-data) q=p; p=p-rchild;else q=p; p=p-lchild;p=new(bnode); p-data=d; p-lchild=NULL; p-rchild=NULL;if (dq-data) q-rchild=p;else q-lchild=p;return t; void inq(struct bnode *t) if(k!=N*2) r+;sr=t;k+; else coutdatalchild);pre_order(t-rchild); void mid_order(struct bnode *t) if (t!=NULL)mid_order(t-lc
3、hild);coutdatarchild); void allinq(struct bnode *t)/二叉树中序进队（数组）二叉树中序进队（数组） if (t!=NULL)allinq(t-lchild);inq(t);allinq(t-rchild); struct bnode * conver(struct bnode *t) int i=0; struct bnode *p,*m,*y; allinq(t); y=s0;y-lchild=NULL; for(i=0;irchild=m; m-lchild=p; m-rchild=NULL; return y; void disp_dou
4、blelink(bnode *h)/显示双向二叉树显示双向二叉树 coutrchild!=NULL) coutdatarchild;while (h!=NULL) coutdatalchild;cout #include #include#define TRUE 1 #define FALSE 0 #define MAXNUM 1000typedef int DataType;struct BinTreeNode; typedef struct BinTreeNode*PBinTreeNode; struct BinTreeNode DataType info;PBinTreeNode lli
5、nk;PBinTreeNode rlink; ; typedef struct BinTreeNode*BinTree; typedef BinTree*PBinTree;int extoBinTree(PBinTree pbtree,const char *ex,int n) /*从中缀表达式 ex(长度为 n)创建二叉树。若是一个合法的表达式，则返回 TRUE，且算法 结束时*pbtree 存放二叉树的根节点的地址；否则返回 FALSE*/ char c;int index,i,bracket;int have_bracket=FALSE; /*记录表达式中是否包含括号*/int num,
6、state_int,nint;int tag1,tag2;if(ex0= |ex0=t|ex0=n)return extoBinTree(pbtree,ex+1,n-1);/*忽略掉左边的若干空字符*/if(exn-1= |ex0=t|ex0=n)return extoBinTree(pbtree,ex,n-1);/*忽略掉右边的若干空字符*/if(ex0=(/*忽略掉左右的成对括号*/bracket=0;index=n;for(i=n-1;i=0;i-)/*从后向前搜索，寻找到第一个不在括号中的优先级最低的运算符*/c=exi;if(c=)/*进入一层括号*/have_bracket=TRU
7、E;bracket+;if(c=() bracket-;/*出一层括号*/if(bracket0) continue;/*若当前位置在某层括号中，直接搜索下个位置*/if(c=+|c=-)if(index=n|exindex=*|exindex=/)index=i;if(c=*|c=/)if(index=n)index=i;if(bracket!=0) return FALSE;/*左右括号不相匹配，表达式非法*/if(index=n)/*说明这是一个只含一个数字和若干空字符的表达式，相应地创建一棵只 含一个根节点的二叉树*/if(have_bracket=TRUE)*pbtree=NULL;
8、return FALSE;/*不应含有括号*/nint=0;/*nint 记录表达式中含有的整数个数*/state_int=FALSE;/*state_int 记录当前读入的字符是否是数字字符*/num=0;for(i=0;iinfo=num;(*pbtree)-llink=NULL;(*pbtree)-rlink=NULL;return TRUE; /*成功创建了一棵只含一个根节点的二叉树*/*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode);(*pbtree)-info=exindex;tag1 =extoBinTree(/*递归调用本算法
9、创建左子数*/tag2 =extoBinTree(/*递归调用本算法创建右子 数*/if(tag1=TRUEreturn FALSE; int cal(BinTree btree,int*presult)/*计算二叉树 btree 所代表的表达式的值。若是一个合法的表 达式，则返回 TRUE，且算法结束时*presult 中存放计算结果；否则，返回 FALSE.*/int result1,result2;if(btree=NULL) return FALSE; /*空树，无法计算*/if(btree-llink=NULLreturn TRUE;if(btree-llink=NULL|btree
10、-rlink=NULL) /*只有左子树或只有右子树，无法 计算*/return FALSE;switch(btree-info)case+:if(cal(btree-llink,if(cal(btree-rlink,*presult=result1+result2;return TRUE;case-:if(cal(btree-llink,if(cal(btree-rlink,*presult=result1-result2;return TRUE;case*:if(cal(btree-llink,if(cal(btree-rlink,*presult=result1*result2;retu
11、rn TRUE;case/:if(cal(btree-llink,if(cal(btree-rlink,*presult=result1/result2;return TRUE;default:return FALSE;void delete_BTree(PBinTree ptree) BinTree temp=(*ptree);if(temp=NULL) return;delete_BTree(delete_BTree(free(temp); void getline(char *line,int limit)/*从标准输入中读入一行，作为字符串 line*/ char c;int i=0;
12、while(ilimit-1linei=0; int main() char c,exMAXNUM;int result,flag=TRUE;BinTree btree;while(flag=TRUE)printf(“Please input the expression:“);getline(ex,MAXNUM);/*读入中缀表达式*/if(extoBinTree(delete_BTree(printf(“nContinue?(y/n)“);scanf(“%c“,if(c=n|c=N) flag=FALSE;while(getchar()!=n);printf(“n“);continue;if(cal(btree,else printf(“Wrong input!n“);delete_BTree(printf(“nContinue?(y/n)“);scanf(“%c“,if(c=n|c=N) flag=FALSE;while(getchar()!=n);printf(“n“);
