二叉树的链式存储结构 C++代码实现

/*二叉树的链式存储结构*/

 
#include <iostream>
using namespace std;


/*二叉链表的定义*/
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;

}BiTNode;  

 
typedef BiTNode * BiTree;

//***************************************************
//***************************************************

/*顺序栈的定义*/

typedef struct sqStack
{
       BiTNode **elem;//栈里面应该存放的是BiTNode数据的指针，也就是地址，而不是BiTNode型的数据
       int top;
       int stackSize;

}sqStack;


/*顺序栈的初始化*/
void initStack_Sq(sqStack &S)
{
       S.elem=new BiTNode*[100];//应该分配(BiTNode * )型的空间
       S.top=-1;
       S.stackSize=100;
}

/*入栈*/
void push_Sq(sqStack &S,BiTNode * x)//此处形参应该为指针型的。
{

       if(S.top==99)
              cout<<"Stack Overflow!";
       else
       {
              S.top++;
              S.elem[S.top]=x;
       }

}

/*出栈*/
BiTNode * pop_Sq(sqStack &S)//此处返回值也应该是指针型的
{

       BiTNode * x;
       if(S.top==-1)
              cout<<"Stack Empty!";
       x=S.elem[S.top];
       S.top--;
       return x;

}

//*******************************************************
//*******************************************************

/*按先序序列，用递归算法创建二叉链表*/
BiTree CreatBiTree_Pre(BiTree &BT)
{

       char ch;
 
       cin>>ch;
       if(ch=='0')
              BT=NULL;//如果是空格字符，则表示为空树。
       else
       {
              BT=new BiTNode;
              BT->data=ch;//生成根结点
              CreatBiTree_Pre(BT->lchild);//递归建立左子树,不能写成BT->lchild=CreatBiTree_Pre(BT)，递归应该在现有的基础上进行递归。牢记此形式！！！

              CreatBiTree_Pre(BT->rchild);//递归建立右子树
       }
       return 0;

}

/*前序递归遍历*/
void PreOrder_Re(BiTree &BT)
{

       if(BT)
       {
              cout<<BT->data<<" ";
              PreOrder_Re(BT->lchild);
              PreOrder_Re(BT->rchild);
       }

}

/*中序递归遍历*/
void InOrder_Re(BiTree &BT)
{

       if(BT)
       {
              InOrder_Re(BT->lchild);
              cout<<BT->data<<" ";
              InOrder_Re(BT->rchild);

       }

}


/*前序非递归遍历*/
void PreOrder_NRe(BiTree &BT)
{

       BiTNode *p;
       sqStack S;
       initStack_Sq(S);

       p=BT;

       while(p||!(S.top==-1))
       {
              if(p)
              {
                     push_Sq(S,p);
                     cout<<p->data<<" ";
                     p=p->lchild;
              }
              else
              {
                     p=pop_Sq(S);
                     p=p->rchild;
              }
       }
       cout<<endl;

}


/*中序非递归遍历*/
void InOrder_NRe(BiTree &BT)
{

       BiTNode *p;
       sqStack S;
       initStack_Sq(S);
       p=BT;

       while(p||!(S.top==-1))
       {
              if(p)
              {
                     push_Sq(S,p);
                     p=p->lchild;
              }
              else
              {
                     p=pop_Sq(S);
                     cout<<p->data<<" ";
                     p=p->rchild;
              }
       }
       cout<<endl;
}

void main()
{

       BiTree BT;

       //creatBiTree(BT);
       CreatBiTree_Pre(BT);

       //PreOrder_NRe(BT);
       InOrder_NRe(BT);
       InOrder_Re(BT);

       cout<<endl;

       PreOrder_NRe(BT);
       PreOrder_Re(BT);

       cout<<endl;

}