二叉树的存储和遍历 (2).txt

二叉树是另一种树形结构

#include <fstream>
#include <iostream>
#include <string>
using namespace std;

typedef char TreeData;

typedef struct node{
    TreeData data;
    struct node *leftchild,*rightchild;
}BinTreeNode;

typedef BinTreeNode *BinTree;

//判空---这个函数作用好像也不是很大 
int IsEmpty(BinTree T)
{
    if(NULL==T)
    {
        cout<<"树为空!"<<endl;
        return 1;           
    }
    return 0;
} 

//先序遍历法建立二叉树,现在想一想,递归函数,最好还是void型 
void Crt_BinTree(ifstream& in,BinTreeNode *& T ) 
{
    TreeData x;
    char RefValue='@';
    if ( !in.eof ( ) ) 
    {
        in >> x;                       //读入根结点的值
        if ( x != RefValue ) 
        {
            T = new BinTreeNode; //建立根结点
            if ( T == NULL )
            {
                cerr <<"存储分配错!" << endl;
                exit(1);
            }
            T->data = x;
            Crt_BinTree ( in, T->leftchild );
            Crt_BinTree ( in, T->rightchild );
        }
        else T = NULL;     //封闭叶结点
    }
}


//先序遍列显示所有元素 
void PreOrder(BinTree T)
{
    if(T!=NULL)
    {
        cout<<T->data<<" ";
        PreOrder(T->leftchild);
        PreOrder(T->rightchild);           
    }
} 

//中序遍历 
void InOrder(BinTree T)
{
    if(T!=NULL)
    {
        InOrder(T->leftchild);
        cout<<T->data<<" ";
        InOrder(T->rightchild);           
    }
} 

//后序遍历
void PostOrder(BinTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->leftchild);
        PostOrder(T->rightchild);   
        cout<<T->data<<" ";        
    }
} 


//主菜单
void Menu()
{
    cout<<"****************************"<<endl;
    cout<<"1,初始化二叉树"<<endl;
    cout<<"2,先序遍历"<<endl;
    cout<<"3,中序遍历"<<endl;
    cout<<"4,后序遍历"<<endl;
    cout<<"5,退出"<<endl; 
    cout<<"****************************"<<endl;     
} 

int main()
{
    BinTree BT=NULL;         //建立一个指向二叉树结点的指针BT 
    //SetNullTree(BT);    //初始化,使BT=null,也就是建立了一个空的二叉树 
    cout<<"初始状态为一颗空树,选择1使用先序遍历法初始化二叉树"<<endl;
    cout<<"读取的文件中的内容为AB@@C@@"<<endl;
    cout<<"正确结果,先序遍历为ABC,中序为BAC,后序为BCA"<<endl<<endl;
    
    //TreeData elem;
    int idx;
    
    int choice,m;
    
    Menu(); 
    cout<<endl;
    
    while(1)
    {
        cout<<"请输入你的选择: ";
        cin>>choice;
        ifstream in("data.txt");
        switch(choice)
        { 
            case 1:
                 //if(BT!=NULL){cout<<"树不为空,初始化失败!"<<endl;break;}
                 //cout<<"请输入先序序列:";
                 //PreCreateTree(BT);
                 
                 Crt_BinTree (in, BT );
                 cout<<"读取文件,成功建立二叉树!"<<endl;
                 break;
            case 2:
                 if(IsEmpty(BT))break;
                 PreOrder(BT);
                 cout<<endl;
                 break; 
            case 3:
                 if(IsEmpty(BT))break;
                 InOrder(BT);
                 cout<<endl;
                 break;
            case 4:
                 if(IsEmpty(BT))break;
                 PostOrder(BT);
                 cout<<endl;
                 break;
            case 5:
                exit(0);
                break;     
            default:
                 cout<<"输入错误,请重新输入选择"<<endl;
                 break;      
        }
    }            
}