creat tree.cpp

设二叉树结点值为大写字母

#include<iostream> 
#define STACK_INIT_SIZE 100//栈或队列的大小常量 
#define STACKINCREMENT 50  //用于扩增栈的大小 
using namespace std;
char preorder[100];   //存放二叉树的前序序列 
char inorder[100];    //存放二叉树的中序序列 
typedef struct BitNode{  //定义二叉链表的结构 
   char value;
   struct BitNode *lchild, *rchild;        
}BitNode ,* BitNodeptr;
typedef struct{   //定义一个存放二叉树结点的栈 
     BitNode *top;
     BitNode *base;
     int stacksize;      
}Stack;
typedef struct{    // 定义一个存放二叉树结点的队列
     BitNode *front;
     BitNode *tail; 
     int Queuesize;       
}Queue;
void InitStack(Stack &S)//初始化栈 
{
   S.base=(BitNode*)malloc(STACK_INIT_SIZE*sizeof(BitNode));
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;    
}
void InitQueue(Queue &S)  //初始化队列 
{
   S.front=(BitNode*)malloc(STACK_INIT_SIZE*sizeof(BitNode));  
   S.tail=S.front;
   S.Queuesize=STACK_INIT_SIZE; 
}
void Pop(Stack &S,BitNodeptr &p) //取出栈顶元素，并把它赋给P 
{
   if(S.top>S.base){
      S.top--;
      p=(BitNode*)malloc(sizeof(BitNode));
      p->value=S.top->value;
      p->lchild=S.top->lchild;
      p->rchild=S.top->rchild;                  
   }     
}
void Dequeue(Queue &S,BitNodeptr &p)  //取出队列的队头元素，并把它赋给P 
{
   if(S.front!=S.tail){
     p=(BitNode*)malloc(sizeof(BitNode));
     p->value=S.front->value;  
     p->lchild=S.front->lchild;
     p->rchild=S.front->rchild; 
     S.front++;
     } 
}
int QueueEmpty(Queue &S)             //判断一个队列是否为空 
{
   if(S.front==S.tail)
     return 1;
   else return 0;       
}
void Enqueue(Queue &S,BitNodeptr p)   //元素P进队列 
{
   if((S.front-S.tail)%STACK_INIT_SIZE!=1){
      S.tail->value=p->value;
      S.tail->lchild=p->lchild;
      S.tail->rchild=p->rchild;
      S.tail++;                                          
   }       
}
void GetTop(Stack &S,BitNodeptr &p)   // 察看当前的栈顶元素 
{
   if(!p)p=(BitNode*)malloc(sizeof(BitNode));
   p->value=(S.top-1)->value;
   p->lchild=(S.top-1)->lchild;
   p->rchild=(S.top-1)->rchild;     
}
void Push(Stack &S,BitNodeptr p)//把元素P压入栈中 
{
   if(S.top-S.base>=S.stacksize){
      S.base=(BitNode*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BitNode));    
      S.top=S.base+S.stacksize;    
      S.stacksize+= STACKINCREMENT;
   }
   S.top->value=p->value;
   S.top->lchild=p->lchild;
   S.top->rchild=p->rchild;
  
   S.top++;
}
int StackEmpty(Stack &S)  //判断当前的栈是否为空 
{
   if(S.top==S.base)
     return 1;
   else return 0;     
}
void creatTree(BitNodeptr &current,int i, int start,int end)//根据前序序列和中叙序列构造一根二叉树 
{
   if(start>end)
      current=NULL;             
   else{
      int k;  
      for(k=start;inorder[k]!=preorder[i];k++);
      current=(BitNode*)malloc(sizeof(BitNode));
      current->value=preorder[i];
      creatTree(current->lchild,i+1,start,k-1);
      creatTree(current->rchild,i+k-start+1,k+1,end);     
   }
}

void visit(BitNodeptr p)
{
   cout<<p->value;     //访问结点P的值 
}

void findvertice(int &control,int n,int &m,char path[],BitNodeptr T,char A)//查找一条到所求结点的路径，如果不存在该路径，则 control为0 
{                                                                          //找到该路径了就返回该路径，并control为1 
     if(control==1)
        path[m]='\0';
     else if(T){
             path[n]=T->value;
             if(path[n]==A){control=1;m=n+1;}
             findvertice(control,n+1,m,path,T->lchild,A);
             findvertice(control,n+1,m,path,T->rchild,A);
          }       
}
void postorderTraverse(BitNodeptr T)  //后序遍历二叉树 
{   
    Stack S;
    InitStack(S);
    Push(S,T);
    T=T->lchild;
    BitNodeptr p;
    int flag;
    while(!StackEmpty(S)){
       while(T){Push(S,T);T=T->lchild;} 
       p=NULL;
       flag=1;
       while(!StackEmpty(S)&&flag){
          GetTop(S,T);                         
          if(!T->rchild||!p){
             if(T->rchild==p){
                visit(T);
                p=T;   
                Pop(S,T);              
             }  
             else{
                T=T->rchild;
                flag=0;     
             }      
          }
          else{
             if(T->rchild->value==p->value){
                 visit(T);
                 p=T;   
                 Pop(S,T);           
             }  
             else{
                T=T->rchild;
                flag=0;     
             }     
          }                                 
       }
                              
    }      
}
void levelTraverse(BitNodeptr T){//按层次遍历二叉树 
   
   BitNodeptr p;
   Queue S;
   InitQueue(S);
   if(T)Enqueue(S,T);
   
   while(!QueueEmpty(S)){
      Dequeue(S,p);
      visit(p);
      if(p->lchild) Enqueue(S,p->lchild);   
      if(p->rchild) Enqueue(S,p->rchild);                  
   }    
}

int main()
{
   cout<<"please input the preorder:"<<endl;//输入前序序列 
   cin>>preorder;
   cout<<"please input the inorder:"<<endl;//输入后序序列 
   cin>>inorder;
   
   int end;          //统计有多少个结点 
   for(end=0;preorder[end]!='\0';end++);
   
   BitNodeptr root;    //调用函数来建立一颗二叉树 
   creatTree(root,0,0,end-1);
   
   cout<<"the postordertraverse is:"; //输出所建二叉树的后序遍历序列 
   postorderTraverse(root);
   cout<<endl;
   
   cout<<"the leveltraverse is:";     //输出所建二叉树的按层次遍历序列 
   levelTraverse(root);
   cout<<endl;
   
   cout<<"please input vertice you want to find:"<<endl;//输入要寻找的结点 
   char A;
   char path[100];       //如果该结点存在树中，就用path数组来记录该路径 
   int n=0,control=0,m=0;
   cin>>A;
   findvertice(control,n,m,path,root,A); //调用函数来判断所求结点是否在树中，并记录下路径 
   if(control==0)             //如果不存在该结点 
     cout<<"there is not the vertice"<<endl;
   else{                       //如果存在该结点 
     cout<<"the path in the tree is:"<<path[0];
     for(int i=1;path[i]!='\0';i++)
       cout<<"-->"<<path[i];  
   }
   system("pause");
   return 0;
}