幫同學(xué)妹妹弄的作業(yè)。。。
以后可以參考

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

#define HeadSTUDENT int


//以下是數(shù)據(jù)類型的定義

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];        //定義一個(gè)用于存放二叉樹結(jié)點(diǎn)指針的數(shù)組

    for (int i=1;i<MaxSize;i++)                //對(duì)指針數(shù)組初始化，初值設(shè)為NULL
        element[i].ptr=NULL;
    p = BT;
    temp.ptr = p;
    if (p) element[1]=temp;        
    for (int i=1;i<MaxSize/2;i++)    //將二叉樹中的每個(gè)結(jié)點(diǎn)指針以順序存儲(chǔ)結(jié)構(gòu)存放到數(shù)組中，并同時(shí)求取最大結(jié)點(diǎn)的編號(hào)
    {
        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中記載當(dāng)前輸入出項(xiàng)的字符串
    char    prespace[42];                    //prespace中記載當(dāng)前輸入出項(xiàng)前面的空格串
    char    postspace[42];                    //postspace中記載當(dāng)前輸入出項(xiàng)后面的空格串

    cout<<"                                 "<<"根結(jié)點(diǎn)BT"<<endl;
    cout<<"                                   "<<"  ↘"<<endl;

    High=log((double)node_last_position)/log(2.0)+1;
    startnum=1;                                //startnum中記載當(dāng)前層中起始結(jié)點(diǎn)編號(hào)
    startnum1=2;                            //startnum中記載當(dāng)前層中起始結(jié)點(diǎn)編號(hào)
    for (int i=1;i<=High;i++)
    {
        endnum=pow(2.0,i)-1;                    //endnum中記載當(dāng)前層中最大結(jié)點(diǎn)編號(hào)
        if (endnum>node_last_position)
            endnum=node_last_position;
        prelenharf=0;
        //輸出第一個(gè)數(shù)據(jù)項(xiàng)
        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);                        //前導(dǎo)空格串的初值為空串            
            for (kk=1;kk<=num_space;kk++)                    //用字符串聯(lián)接方式生成前導(dǎo)空格串prechar
                strcat(prechar,space);
            prelenharf=curlenharf;
            if (p) 
                cout<<prechar<<p->data.age;
            else
                cout<<prechar<<"   ";                        //" 0 "
        }
        cout<<endl;
        //輸出第二個(gè)數(shù)據(jù)項(xiàng)
        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);                        //前導(dǎo)空格串的初值為空串
            for (kk=1;kk<=num_space;kk++)                    //用字符串聯(lián)接方式生成前導(dǎo)空格串prechar
                strcat(prechar,space);
            prelenharf=curlenharf;
            if (p) 
                cout<<prechar<<p->data.name ;
            else
                cout<<prechar<<"   ";                        //" ^ "
        }
        startnum=endnum+1;
        cout<<endl;

        //以下程序是完成分支結(jié)的輸出
        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層下面的分枝線層中最大結(jié)點(diǎn)編號(hào)
            for(k=startnum1;k<=endnum1;k++)
            {
                strcpy(prechar,emptystr);                //前導(dǎo)空格串的初值為空串            
                for (kk=1;kk<=position_line[k];kk++)    //用字符串聯(lián)接方式生成前導(dǎo)空格串prechar==startnum1
                    if (!(k%2))
                        strcat(prechar,space);            //形成當(dāng)前中第偶數(shù)個(gè)結(jié)點(diǎn)前的空格串
                    else
                        strcat(prechar,line);            //形成當(dāng)前中第奇數(shù)個(gè)結(jié)點(diǎn)前的"─"串

                if (!(k%2)) 
                    cout<<prechar;                        //當(dāng)前中第偶數(shù)個(gè)結(jié)點(diǎn)前輸出空格串
                else 
                {
                    len=strlen(prechar);
                    lenharf=len/2;
                    if ((element[k-1].ptr && element[k].ptr))        //當(dāng)前分支左右均有結(jié)點(diǎn)
                    {
                        prechar[lenharf]='┴';
                        cout<<"┌"<<prechar<<"┐";
                    }
                    if ((element[k-1].ptr && !element[k].ptr))        //當(dāng)前分支左邊有結(jié)點(diǎn)，右邊無(wú)結(jié)點(diǎn)
                    {
                        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))        //當(dāng)前分支右邊有結(jié)點(diǎn)，左邊無(wú)結(jié)點(diǎn)
                    {
                        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))        //當(dāng)前分支左右均無(wú)結(jié)點(diǎn)
                    {
                        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)
{// 構(gòu)造一個(gè)最大容量為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進(jìn)s棧，返回進(jìn)棧后的狀態(tài)值
    if (IsFull(S))   return ERROR;
    S.top++;
    S.element[S.top] = x;
    return OK;
}

Status Pop(Stack &S , SType &x)
{// 將s棧頂?shù)闹等≈義中，返回出棧后的狀態(tài)值
    if (IsEmpty(S))   return ERROR;
    x = S.element[S.top];
    S.top--;
    return OK;
}

BinaryTreeNode   *MakeNode(STUDENT &x)    
{//構(gòu)造結(jié)點(diǎn)
      BinaryTreeNode* newtree=new BinaryTreeNode;
      newtree->data=x;
      return newtree;
}

void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right)
{// 聯(lián)接root，left, right所指的結(jié)點(diǎn)指針為二叉樹
    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);            //產(chǎn)生一個(gè)空棧，這一過(guò)程函數(shù)可以不在這里進(jìn)行
    while (p!=NULL || !IsEmpty(S))
    {
        while (p!=NULL)             //遍歷左子樹
        {
            temp.ptr=p;
            Push(S,temp);
            cout<<p->data.name<<" ";
            p=p->LChild;  
        }

        if (!IsEmpty(S))         //通過(guò)下一次循環(huán)中的內(nèi)嵌while實(shí)現(xiàn)右子樹遍歷
        {
            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);                //產(chǎn)生一個(gè)空棧，這一過(guò)程函數(shù)可以不在這里進(jìn)行
    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;;            //通過(guò)下一次循環(huán)實(shí)現(xiàn)右子樹遍歷
        }  

    }
   cout<<endl;
}


void PostOrderN(BinaryTreeNode *BT) 
{//二叉樹的后序遍歷非遞歸算法
    SType            temp;
    Stack            S;
    BinaryTreeNode    *p = BT;
    int MaxStackSize=50;
    CreatStack (S , MaxStackSize);    //產(chǎn)生一個(gè)空棧，這一過(guò)程函數(shù)可以不在這里進(jìn)行
    do 
    {
        while (p!=NULL)        //遍歷左子樹
        {
            temp.ptr = p; 
            temp.B = false;         //標(biāo)記為左子樹
            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，表示右子樹訪問完畢，故訪問根結(jié)點(diǎn)       
        }

        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<<"先序遍歷的順序?yàn)椋?/span>"<<endl;
    PreOrderN(BT);
    cout<<"中序遍歷的順序?yàn)椋?/span>"<<endl;
    InOrderN(BT);
    cout<<"后序遍歷的順序?yàn)椋?/span>"<<endl;
    PostOrderN(BT);
    return 0;
}