二叉树转双向链表-和-中缀转二树.doc

《二叉树转双向链表-和-中缀转二树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#includetypedefcharelemtype;structbnode{elemtypedata;structbnodelchild,rchild;};constN=10;structbnodes[N];inth=-1,r=-1,k=0;structbnodeset_tree(){structbnodet,p,q;inti;chard;t=new(bnode);t->data=rand()%26+'A';t->lc

2、hild=NULL;t->rchild=NULL;for(i=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(d>q->data)q->rchild=p;elseq->lchild=p;}returnt;}voidinq(structbnodet){if(k!=N2){r++;s[r]=t;

3、k++;}elsecout<<"Overflow";}voidpre_order(structbnodet){if(t!=NULL){cout<data<<"";pre_order(t->lchild);pre_order(t->rchild);}}voidmid_order(structbnodet){if(t!=NULL){mid_order(t->lchild);cout<data<<"";mid_order(t->rchild);}}voidallinq(structbnodet)//二叉树中序进队（数组）{if(t!=N

4、ULL){allinq(t->lchild);inq(t);allinq(t->rchild);}}structbnodeconver(structbnodet){inti=0;structbnodep,m,y;allinq(t);y=s[0];y->lchild=NULL;for(i=0;irchild=m;m->lchild=p;}m->rchild=NULL;returny;}voiddisp_doublelink(bnodeh)//显示双向二叉树{cout<<"显示双向链表(转一圈

5、)"<rchild!=NULL){cout<data<<"";h=h->rchild;}while(h!=NULL){cout<data<<"";h=h->lchild;}cout<

6、isp_doublelink(conver(t));}#include#include#include#defineTRUE1#defineFALSE0#defineMAXNUM1000typedefintDataType;structBinTreeNode;typedefstructBinTreeNodePBinTreeNode;structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;};typedefstru

7、ctBinTreeNodeBinTree;typedefBinTreePBinTree;intextoBinTree(PBinTreepbtree,constcharex,intn)/从中缀表达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回TRUE，且算法结束时pbtree存放二叉树的根节点的地址；否则返回FALSE/{charc;intindex,i,bracket;inthave_bracket=FALSE;/记录表达式中是否包含括号/intnum,state_int,nint;inttag1,tag2;if(ex[0]==''e

8、x[0]=='t'ex[0]=='')returnextoBinTree(pbtree,ex+1,n-1);/忽略掉左边的若干空字