Manchester- 数据结构-二叉链表存储的二叉树(深度还原题目代码)

解题思路:
①：测试系统不支持栈函数库调用，所以栈操作要自己写

②：定义栈，定义二叉树结点

③：声明栈操作函数

④：声明需要实现的二叉树操作函数

⑤：编写主函数

⑥：定义栈操作，二叉树操作

注意事项:

1）：栈里面存的是二叉树的结点指针，是指针

2）：

void pop_(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/
int getTop(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/

这里和返回一个数道理一样
void get_E(int *e)
{
   (*e)=1+2;
}
/*------------------*/
int e;
get_E(&e);
最后e=3;
void CreatBitree(Bitree *T); 该函数也是一样的道理
刚开始二叉树头结点是没建立的，到了函数里面，才根据输入数据判断是否创建该结点

3）：PreOrderTraverse(T);函数遍历输出后，加上换行

4）：栈操作定义好后，照着题目所示图片打上二叉树的操作，就可以，除了在图片中visit的位置换成

          printf之外，都不用改

5）：题目测试数据为：ABC##DE#G##F###   #代表空格

参考代码:

#include<stdio.h>
#include<malloc.h>

#define MAX 101
typedef struct BiTNode{

    char data;
    struct BiTNode *LeftChild,*RightChild;


}*Bitree,BiTree;

typedef struct Stack_{

   Bitree elem[MAX];/*存放二叉树结点指针*/
   int top;

}*Stack,STACK;


/*---------------------------------------------*/
/*声明栈操作*/
void init_(Stack s);/*初始化栈*/
void push_(Stack s,Bitree T);
void pop_(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/
int getTop(Stack s,Bitree *T);/*返回结点指针，所以Bitree *，指向指针的指针*/
/*getTop返回值为int是因为下面出现这样代码while(getTop(&S,&p)&&p)需要有返回值*/
int stackempty(Stack s);/*判断栈空*/

/*---------------------------------------------*/
/*声明二叉树操作*/
void CreatBitree(Bitree *T); /*二叉树的创建*//*返回结点指针，所以Bitree *，指向指针的指针*/
void PreOrderTraverse(Bitree T);/*先序遍历二叉树*/
void InOrderTraverse1(Bitree T);/*第一种中序遍历二叉树*/
void InOrderTraverse2(Bitree T);/*第二种遍历二叉树*/

/*---------------------------------------------*/

int main()
{

  Bitree T;/*建立二叉树头结点指针*/


     CreatBitree(&T);/*T为指针，&T为它的地址，到了函数里面(*T)才代表这里的T*/

      PreOrderTraverse(T);
           printf("\n");/*先序遍历完后换行*/
        InOrderTraverse1(T);

         InOrderTraverse2(T);

         return 0;

}

/*======================栈操作声明=================*/
void init_(Stack s)/*初始化栈*/
{
  s->top=0;
}
/*----------------------------------------*/
void push_(Stack s,Bitree T)
{

  s->elem[s->top++]=T;

}
/*----------------------------------------*/
void pop_(Stack s,Bitree *T)
{
 (*T)=s->elem[--s->top];
}
/*----------------------------------------*/
int stackempty(Stack s)/*判断栈空*/
{

  if(s->top==0)
   return 1;
   else
   return 0;

}
/*----------------------------------------*/
int getTop(Stack s,Bitree *T)/*返回结点指针*/
{
  (*T)=s->elem[s->top-1];
   return 1;
}
/*=================================================*/

/*====================二叉树操作===================*/
void CreatBitree(Bitree *T) /*二叉树的创建*/
{
    char ch;

    scanf("%c",&ch);
    if(ch==' ')/*如果输入为空格，那么该指针T指向节点为空不存在，所以T=BULL*/
      (*T)=NULL;
      else
      {

         /*否则为该节点分配空间*/
          (*T)=(Bitree)malloc(sizeof(BiTree));
          (*T)->data=ch;/*结点赋值*/
          /*递归创建T的左孩子*/
          CreatBitree(&(*T)->LeftChild);
          /*递归创建T的右孩子*/
          CreatBitree(&(*T)->RightChild);

      }
return ;
}
/*-----------------------------------------*/
void PreOrderTraverse(Bitree T)/*先序遍历二叉树*/
{
    if(T)
     {
       printf("%c ",T->data);
        PreOrderTraverse(T->LeftChild);
        PreOrderTraverse(T->RightChild);

     }
}
/*-----------------------------------------*/
void InOrderTraverse1(Bitree T)/*第一种中序遍历二叉树*/
{
    STACK S;
    init_(&S);

      while(T||!stackempty(&S))
        {

          if(T)
           {
             push_(&S,T);
             T=T->LeftChild;
           }
           else
           {
             pop_(&S,&T);
             printf("%c ",T->data);
             T=T->RightChild;
           }
        }
        /*输出完换行*/
        printf("\n");
        return ;
}
/*-----------------------------------------*/
void InOrderTraverse2(Bitree T)/*第二种遍历二叉树*/
{
  STACK S;
  Bitree p;
  init_(&S);

     push_(&S,T);
       while(!stackempty(&S))
        {
          while(getTop(&S,&p)&&p)
             push_(&S,p->LeftChild);

           pop_(&S,&p);
             if(!stackempty(&S))
               {
                  pop_(&S,&p);
                   printf("%c ",p->data);
                   push_(&S,p->RightChild);
               }
        }


}

给个赞哦-.-！