tree.cpp_C语言_源码

~~~c #include<stdio.h> #include<stdlib.h> typedef char ElemType; typedef struct BiThrNode { ElemType data; struct BiThrNode *lchild; struct BiThrNode *rchild; struct BiThrNode *parent; int LTag,RTag; }BiThrNode,*BiThrTree; void createBiTree(BiThrTree &T) //创建二叉树 { ElemType c=NULL; scanf("%c",&c); if(c=='#') T=NULL; else { T=(BiThrTree)malloc(sizeof(BiThrNode)); T->data=c; createBiTree(T->lchild); createBiTree(T->rchild); } } void createparent(BiThrTree &T,BiThrTree T1) //创建parent节点 { ElemType c=NULL; scanf("%c",&c); if(c=='#') T=NULL; else { T=(BiThrTree)malloc(sizeof(BiThrNode)); T->parent=T1; T->data=c; T->LTag=0; T->RTag=0; createparent(T->lchild,T); createparent(T->rchild,T); } } int In(char e)//判断读入字符是否为运算符 { if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#') return 1;//是 else return 0; //不是 } void precreateBiTree(BiThrTree &T) //先序创造表达式二叉树 { ElemType c=NULL; scanf("%c",&c); T=(BiThrTree)malloc(sizeof(BiThrNode)); if(!In(c)) {T->data=c;T->rchild=NULL;T->lchild=NULL;} else { T->data=c; precreateBiTree(T->lchild); precreateBiTree(T->rchild); } } void PreOrderTraverse(BiThrTree T) //后序输出二叉树 { if(!T) { printf("#"); } else{ printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);} } void PreOrderTraverse2(BiThrTree T) //先序输出表达式二叉树 { if(!T) { } else{ printf("%c",T->data); PreOrderTraverse2(T->lchild); PreOrderTraverse2(T->rchild);} } InOrderTraverse(BiThrTree T) //中序输出二叉树 { if(!T) { printf("#"); return 1;} else{ InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild);} } AftOrderTraverse(BiThrTree T) //后序输出二叉树 { if(!T) { printf("#"); return 1;} else{ InOrderTraverse(T->lchild); InOrderTraverse(T->rchild); printf("%c",T->data);} } InOrderTraverse2(BiThrTree T) //中序输出表达式二叉树 { if(!T) { return 1;} else{ InOrderTraverse2(T->lchild); printf("%c",T->data); InOrderTraverse2(T->rchild);} } aftOrderTraverse2(BiThrTree T) //后序输出 表达式二叉树 { if(!T) { return 1;} else{ aftOrderTraverse2(T->lchild); aftOrderTraverse2(T->rchild); printf("%c",T->data);} } BiThrTree pre; void aftThreading(BiThrTree p) //后序线索化二叉树 { if(p){ aftThreading(p->lchild); aftThreading(p->rchild); if(!p->lchild){ p->LTag=1; p->lchild=pre; } if(pre&&!pre->rchild){ pre->RTag=1; pre->rchild=p; } pre=p; } } void aftOrderThreading(BiThrTree &Thrt,BiThrTree T){ //后序线索化二叉树 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (0); Thrt->LTag=0; Thrt->RTag=1; Thrt->rchild=Thrt; if(!T) Thrt->lchild=Thrt; else{ Thrt->lchild=T; pre=Thrt; aftThreading(T); if(!pre->lchild) { pre->lchild=pre->rchild; pre->LTag=1;} if (!pre->rchild) { pre->rchild=Thrt; pre->RTag=1;} } } void AftOrderTraverse2(BiThrTree T)//后序遍历线索化二叉树 { BiThrTree p=T->lchild; while(p!=T){ while(p->LTag!=1) p=p->lchild; if(p->RTag==1) { while(p->RTag==1||p->parent->LTag==1||p->parent->RTag==1||p==p->parent->rchild) { printf("%c",p->data); if(p->RTag==1) p=p->rchild; else p=p->parent; if (p==T->lchild) break; } printf("%c",p->data); if (p==T->lchild) break; p=p->parent->rchild; } else p=p->rchild; } } //HDA##C#B##GF#E### //ab#dg###ce#h##f## //-+a##*b##-c##d##/e##f## //abcd##### //a#b#c#d## char operate(char a,char theta,char b)//运算 { char c; a=a-'0'; b=b-'0'; if(theta=='+') c=a+b+'0'; else if(theta=='-') c=a-b+'0'; else if(theta=='*') c=a*b+'0'; else if(theta=='/') c=a/b+'0'; return c; } //-+a##*b##-c##d##/e##f## main(){ BiThrTree T,T1,T2; int i,nn=1; printf("1:先序创造二叉树\n"); printf("21/22/23:先序/中序/后序遍历二叉树\n"); printf("3:后序线索化二叉树\n"); printf("4:后序遍历线索二叉树\n"); printf("5:先序创造表达式二叉树\n"); printf("61/62/63:先序/中序/后序遍历算术二叉树\n"); if(!(T1=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (0); for(i=1;i<=100;++i){ scanf("%d",&nn); if (nn==1){ createparent(T,T1); } if(nn==21){ PreOrderTraverse(T); } if(nn==22){ InOrderTraverse(T); } if(nn==23){ AftOrderTraverse(T); } if (nn==3){ aftOrderThreading(T1,T); } if (nn==4){ AftOrderTraverse2(T1); } if (nn==5){ precreateBiTree(T2); } if (nn==61){ PreOrderTraverse2(T2); } if(nn==62){ InOrderTraverse2(T2); } if(nn==63){ aftOrderTraverse2(T2); } // precreateBiTree(T); // createBiTree(T); // printf("%d",T1->lchild->rchild->rchild->LTag); //InOrderTraverse2(T); //printf("\n"); } } ~~~