帮同学妹妹弄的作业。。。
以后可以参考

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define HeadSTUDENT int


//以下是数据类型的定义

enum  Status{OK, ERROR};

typedef struct
{
    char            number[10];
    char            name[8];
    char            sex[3];
    int                age;
    char            place[20];
}STUDENT;
typedef struct BinaryTreeNode
{    
    STUDENT         data;
    BinaryTreeNode    *LChild;
    BinaryTreeNode    *RChild;
} BinaryTree;


typedef struct 
{
    BinaryTreeNode    *ptr;
    bool        B; //true代表左子树，false代表右子树
} SType;


typedef struct //StackElement
{    
    SType            *element;
    int            top;
    int            MaxSize;
} Stack;

void DigitalToString(char str[],int n)
{
    char    temp;
    char    k=1;
    int    i=0;
    while (n && i<80)
    {
        k=n%10+48;
        n=n/10;
        str[i]=k;
        i++;
    }
    str[i]='\0';

    int len=strlen(str);
    for (i=0;i<len/2;i++)
    {
        temp=str[i];
        str[i]=str[len-i-1];
        str[len-i-1]=temp;
    }
}


void OutputLevelOrderTL(BinaryTreeNode *BT)
{// 从左至右，从上至下按层次输出一棵二叉树
    typedef struct 
    {
        BinaryTreeNode    *ptr;
    } Node_Ptr;

    Node_Ptr        temp,*element;
    BinaryTreeNode     *p;
    int        MaxSize=50; 
    int        pagewidth=80;
    int        node_last_position;
    int        High;

    element = new Node_Ptr [MaxSize+1];        //定义一个用于存放二叉树结点指针的数组

    for (int i=1;i<MaxSize;i++)                //对指针数组初始化，初值设为NULL
        element[i].ptr=NULL;
    p = BT;
    temp.ptr = p;
    if (p) element[1]=temp;        
    for (int i=1;i<MaxSize/2;i++)    //将二叉树中的每个结点指针以顺序存储结构存放到数组中，并同时求取最大结点的编号
    {
        p=element[i].ptr;
        if (p)
        {
            if (p->LChild)     
            {
                temp.ptr = p->LChild;
                element[2*i]=temp;

                node_last_position=2*i;
            }
            if (p->RChild)     
            {
                temp.ptr = p->RChild;
                element[2*i+1]=temp;
                node_last_position=2*i+1;
            }
        }
    }

    cout<<endl;
    int position_data[32]={0,
        40,  
        20,                40,  
        10,        20,        20,        20,  
        6,  10,  10, 10,  10,  10, 10,  10,  
        3,5,5,5, 5,5,5,5, 5,5, 5,5, 5,5, 5,5};
    int        kk,k;
    int        startnum,endnum;
    int        startnum1,endnum1;
    int        len, curlenharf,prelenharf,templen,lenharf;
    int        num_space;
    char    str[80];
    char    emptystr[42]={""};
    char    space[2]=" ";
    char    line[3]="─";
    char    prechar[42];                    //prechar中记载当前输入出项的字符串
    char    prespace[42];                    //prespace中记载当前输入出项前面的空格串
    char    postspace[42];                    //postspace中记载当前输入出项后面的空格串

    cout<<"                                 "<<"根结点BT"<<endl;
    cout<<"                                   "<<"  ↘"<<endl;

    High=log((double)node_last_position)/log(2.0)+1;
    startnum=1;                                //startnum中记载当前层中起始结点编号
    startnum1=2;                            //startnum中记载当前层中起始结点编号
    for (int i=1;i<=High;i++)
    {
        endnum=pow(2.0,i)-1;                    //endnum中记载当前层中最大结点编号
        if (endnum>node_last_position)
            endnum=node_last_position;
        prelenharf=0;
        //输出第一个数据项
        for(k=startnum;k<=endnum;k++)
        {
            templen=1;    
            p=element[k].ptr;
            if (p)
            {
                DigitalToString(str, p->data.age);
                len=strlen(str);
                curlenharf=len/2;
                if (!(len%2) && (prelenharf%2)==(curlenharf%2)&&(k%2))
                    templen-=2;
                if ((prelenharf%2)!=(curlenharf%2)&&(k%2))
                    templen--;
                num_space=position_data[k]-curlenharf-prelenharf-templen;
            }
            else
                num_space=position_data[k]-templen-2;
            strcpy(prechar,emptystr);                        //前导空格串的初值为空串            
            for (kk=1;kk<=num_space;kk++)                    //用字符串联接方式生成前导空格串prechar
                strcat(prechar,space);
            prelenharf=curlenharf;
            if (p) 
                cout<<prechar<<p->data.age;
            else
                cout<<prechar<<"   ";                        //" 0 "
        }
        cout<<endl;
        //输出第二个数据项
        prelenharf=0;
        for(k=startnum;k<=endnum;k++)
        {
            templen=1;    
            p=element[k].ptr;
            if (p)
            {
                len=strlen(p->data.name);
                curlenharf=len/2;
                if (!(len%2) && (prelenharf%2)==(curlenharf%2)&&(k%2))
                    templen-=2;
                if ((prelenharf%2)!=(curlenharf%2)&&(k%2))
                    templen--;
                num_space=position_data[k]-curlenharf-prelenharf-templen;
            }
            else
                num_space=position_data[k]-templen-2;

            strcpy(prechar,emptystr);                        //前导空格串的初值为空串
            for (kk=1;kk<=num_space;kk++)                    //用字符串联接方式生成前导空格串prechar
                strcat(prechar,space);
            prelenharf=curlenharf;
            if (p) 
                cout<<prechar<<p->data.name ;
            else
                cout<<prechar<<"   ";                        //" ^ "
        }
        startnum=endnum+1;
        cout<<endl;

        //以下程序是完成分支结的输出
        int position_line[32]={0,
            20,  
            19,                     19,  
            9,        9,            18,          9,  
            5,    3,    10,      3,  10,  3,  10,  3,  
            2,1,  4,1,4,1,  4,1,    4, 1,4,1, 4,1,4,1};
        if (i<High)
        {
            endnum1=pow(2.0,i+1)-1;                        //endnum中记载第i层下面的分枝线层中最大结点编号
            for(k=startnum1;k<=endnum1;k++)
            {
                strcpy(prechar,emptystr);                //前导空格串的初值为空串            
                for (kk=1;kk<=position_line[k];kk++)    //用字符串联接方式生成前导空格串prechar==startnum1
                    if (!(k%2))
                        strcat(prechar,space);            //形成当前中第偶数个结点前的空格串
                    else
                        strcat(prechar,line);            //形成当前中第奇数个结点前的"─"串

                if (!(k%2)) 
                    cout<<prechar;                        //当前中第偶数个结点前输出空格串
                else 
                {
                    len=strlen(prechar);
                    lenharf=len/2;
                    if ((element[k-1].ptr && element[k].ptr))        //当前分支左右均有结点
                    {
                        prechar[lenharf]='┴';
                        cout<<"┌"<<prechar<<"┐";
                    }
                    if ((element[k-1].ptr && !element[k].ptr))        //当前分支左边有结点，右边无结点
                    {
                        prechar[lenharf-1]='\0';
                        cout<<"┌"<<prechar<<"┘";
                        strcpy(postspace,emptystr);
                        for (kk=1;kk<=lenharf+1;kk++)
                            strcat(postspace,space);
                        cout<<postspace;
                    }
                    if ((!element[k-1].ptr && element[k].ptr))        //当前分支右边有结点，左边无结点
                    {
                        strcpy(prespace,emptystr);
                        for (kk=1;kk<=lenharf+1;kk++)
                            strcat(prespace,space);
                        prechar[lenharf-1]='\0';
                        cout<<prespace<<"└"<<prechar<<"┐";
                    }
                    if ((!element[k-1].ptr && !element[k].ptr))        //当前分支左右均无结点
                    {
                        strcpy(prespace,emptystr);
                        for (kk=1;kk<=len;kk++)
                            strcat(prespace,space);
                        cout<<prespace<<"    ";
                    }
                }
            }
            cout<<endl;
            startnum1=endnum1+1;
        }
    }
    cout<<endl<<endl<<endl;
}


void CreatStack(Stack &S, int MaxStackSize)
{// 构造一个最大容量为MaxStackSize 的堆栈
    S.MaxSize = MaxStackSize;
    S.element = new SType[S.MaxSize];
    S.top =-1;
}

bool IsEmpty(Stack &S)
{// 判断堆栈S是否为空
    if (S.top == -1)   return true;
    return  false;
}

bool IsFull(Stack &S)
{// 判断堆栈S是否为满
    if (S.top >= S.MaxSize-1)   return true;
    return  false;
}
Status Push(Stack &S , SType &x)
{// x进s栈，返回进栈后的状态值
    if (IsFull(S))   return ERROR;
    S.top++;
    S.element[S.top] = x;
    return OK;
}

Status Pop(Stack &S , SType &x)
{// 将s栈顶的值取至x中，返回出栈后的状态值
    if (IsEmpty(S))   return ERROR;
    x = S.element[S.top];
    S.top--;
    return OK;
}

BinaryTreeNode   *MakeNode(STUDENT &x)    
{//构造结点
      BinaryTreeNode* newtree=new BinaryTreeNode;
      newtree->data=x;
      return newtree;
}

void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right)
{// 联接root，left, right所指的结点指针为二叉树
    root->LChild=left;
     root->RChild=right;
     
}

int  BinaryHeight(BinaryTreeNode  *BT) 
{// 返回二叉树的高度
    if (BT==NULL) return 0;
    int HighL = BinaryHeight(BT ->LChild);
    int HighR = BinaryHeight(BT ->RChild); 
    if (HighL > HighR)  
        return ++HighL;
    else 
        return ++HighR;
}

void PreOrderN(BinaryTreeNode *BT)
{//二叉树的前序遍历非递归算法
    Stack            S;
    SType            temp;
    BinaryTreeNode    *p = BT;
    int MaxStackSize=50;
    CreatStack(S ,MaxStackSize);            //产生一个空栈，这一过程函数可以不在这里进行
    while (p!=NULL || !IsEmpty(S))
    {
        while (p!=NULL)             //遍历左子树
        {
            temp.ptr=p;
            Push(S,temp);
            cout<<p->data.name<<" ";
            p=p->LChild;  
        }

        if (!IsEmpty(S))         //通过下一次循环中的内嵌while实现右子树遍历
        {
            Pop(S,temp);
            p=temp.ptr->RChild;        
        }

    }
     cout<<endl;
}

void InOrderN(BinaryTreeNode *BT) 
{//二叉树的中序遍历非递归算法
    Stack            S;
    SType            temp;
    BinaryTreeNode    *p = BT;
    int MaxStackSize=50;
    CreatStack (S , MaxStackSize);                //产生一个空栈，这一过程函数可以不在这里进行
    while (p!=NULL || !IsEmpty(S))
    {
        while (p!=NULL)             //遍历左子树
        {
            temp.ptr=p;
            Push(S,temp);
            p=p->LChild;
        }

        if (!IsEmpty(S))
        {
            Pop(S,temp);
            cout<<temp.ptr->data.name<<" ";
            p=temp.ptr->RChild;;            //通过下一次循环实现右子树遍历
        }  

    }
   cout<<endl;
}


void PostOrderN(BinaryTreeNode *BT) 
{//二叉树的后序遍历非递归算法
    SType            temp;
    Stack            S;
    BinaryTreeNode    *p = BT;
    int MaxStackSize=50;
    CreatStack (S , MaxStackSize);    //产生一个空栈，这一过程函数可以不在这里进行
    do 
    {
        while (p!=NULL)        //遍历左子树
        {
            temp.ptr = p; 
            temp.B = false;         //标记为左子树
            Push(S,temp);
            p=p->LChild;
        }

        while (!IsEmpty(S) && S.element[S.top].B==true)  
        {
            Pop(S,temp);
            p = temp.ptr;
            cout<<temp.ptr->data.name<<" ";   //tag为R，表示右子树访问完毕，故访问根结点       
        }

        if (!IsEmpty(S))
        {
            S.element[S.top].B =true;     //遍历右子树
            p=S.element[S.top].ptr->RChild;        
        }    
    }while (!IsEmpty(S));

cout<<endl;
}
 



//下面是主程序
int main()
{
    BinaryTreeNode  *BT,*p=NULL,*pp[10];
    STUDENT        x;
    int        High;


    char    n[][8]={"    ","AAA","BBB","CCC","DDD","EEE","FFF","GGG","HHH"};

    for(int i=1;i<9;i++)
    {
        strcpy(x.number,"7777777");
        strcpy(x.name,n[i]);
        if (i>4)
            strcpy(x.sex,"男");
        else 
            strcpy(x.sex,"女");
        x.age=500+i;
        strcpy(x.place,"WWWWW");
        pp[i]=MakeNode(x);
        p=pp[i];
    }

    MakeBinaryTree(pp[1], pp[2], pp[3]);
    MakeBinaryTree(pp[2], pp[4], NULL);
    MakeBinaryTree(pp[3], pp[5], pp[6]);
    MakeBinaryTree(pp[4], NULL, pp[7]);
    MakeBinaryTree(pp[5], pp[8], NULL);
 
    BT=pp[1];
    pp[7]->LChild=NULL;
    pp[7]->RChild=NULL;
    pp[8]->LChild=NULL;
    pp[8]->RChild=NULL;
    pp[6]->LChild=NULL;
    pp[6]->RChild=NULL;
    High=BinaryHeight(BT) ;
    cout<<"树高="<<High<<endl<<endl;
    OutputLevelOrderTL(BT);
    cout<<"先序遍历的顺序为："<<endl;
    PreOrderN(BT);
    cout<<"中序遍历的顺序为："<<endl;
    InOrderN(BT);
    cout<<"后序遍历的顺序为："<<endl;
    PostOrderN(BT);
    return 0;
}