《二叉树转双向链表-和-中缀转二树》由会员分享，可在线阅读，更多相关《二叉树转双向链表-和-中缀转二树（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=1
2、;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 coutOverflow;void pre_order(struct bnode *t) if (t!=NULL) coutdatalchild); pre_order(t-rchil
3、d); void mid_order(struct bnode *t) if (t!=NULL) mid_order(t-lchild); 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;
4、m-lchild=p;m-rchild=NULL;return y;void disp_doublelink(bnode *h)/显示双向二叉树 cout显示双向链表(转一圈)rchild!=NULL) coutdatarchild; while (h!=NULL) coutdatalchild; coutendl;void main() bnode *t; srand(unsigned)time(NULL); t=set_tree(); coutendlpreorderendl; pre_order(t); coutendlmidorderendl; mid_order(t); couten
5、dl; disp_doublelink(conver(t);#include#include#include#define TRUE 1#define FALSE 0#define MAXNUM 1000typedef int DataType;struct BinTreeNode;typedef struct BinTreeNode*PBinTreeNode;struct BinTreeNode DataType info; PBinTreeNode llink; PBinTreeNode rlink;typedef struct BinTreeNode*BinTree;typedef Bi
6、nTree*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,state_int,nint; int tag1,tag2; if(ex0= |ex0=t|ex0=n) return extoBinTree(pbt
7、ree,ex+1,n-1);/*忽略掉左边的若干空字符*/ if(exn-1= |ex0=t|ex0=n) return extoBinTree(pbtree,ex,n-1);/*忽略掉右边的若干空字符*/ if(ex0=(&exn-1=) return extoBinTree(pbtree,ex+1,n-2);/*忽略掉左右的成对括号*/ bracket=0; index=n; for(i=n-1;i=0;i-)/*从后向前搜索，寻找到第一个不在括号中的优先级最低的运算符*/ c=exi; if(c=)/*进入一层括号*/ have_bracket=TRUE; bracket+; if(c=
8、() 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; return FALSE; /*不应含有括号*/ nint=0;/*nint记录表达式中含有的整数个数*/ state_int=FALSE;/*state_int记录当前读入的字符是否是数字字符*/ num=0; for(i=0;in;i+) c=exi; switch(c) case0:case1:case2:case3:case4: case5:case6:case7:case8:case9: if(state_int=FALSE) num=c-0; state_int=TRUE; nint+; else num=num*10+c-0; break; case :caset:casen:
