leveltree.cpp

按层序方式（自上而下

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct QNode{
  int Data;
  QNode *Next;
};  

class Queue{
  private:
    int Size;
    QNode *Head, *Tail;
  public:
    Queue();
    ~Queue();
    void InQueue(int x);
    bool OutQueue(int &x);
    int GetSize(){return Size;};
}; 

Queue::Queue()
{
  Size = 0;
  Head = 0;
  Tail = 0;
}   

Queue::~Queue()
{
  QNode *Temp;
  for(int i=0; i<Size; ++i)
  {
    Temp = Head;
    Head = Head->Next;
    delete Temp;
  }
}  

void Queue::InQueue(int x)
{
  QNode *Temp;
  Temp = new QNode;
  Temp->Data = x;
  if(Tail)
  {
    Tail->Next = Temp;
    Tail = Temp;
  }  
  else
  {
    Tail = Temp;
    Head = Temp;
  }  
  ++Size;
}

bool Queue::OutQueue(int &x)
{
  if(Size > 0)
  {
    QNode *Temp;
    x = Head->Data;
    Temp = Head;
    Head = Head->Next;
    delete Temp; 
    if (--Size == 0)
    {
      Head = 0;
      Tail = 0;
    } 
    return true;
  }  
  else return false;
}  

class IntStack{
private:
  int StackSize;
  int *Base;
  int *Top;
public:
  IntStack(int Size);
  ~IntStack();
  void Resize(int Size);
  bool Push(int x);
  bool Pop(int &x);
  bool IsEmpty(){return (Top == Base);}
  int GetTop(){return *Top;}
  int Size(){return StackSize;}
};

IntStack::IntStack(int Size)
{
  Base = (int*)malloc(Size);
  StackSize = Size;
  Top = Base;
}

IntStack::~IntStack()
{
  free(Base);
}

void IntStack::Resize(int Size)
{
  int Temp;
  Temp = Top - Base;
  realloc(Base, Size);
  StackSize = Size;
  Top = Base + Temp;
}

bool IntStack::Push(int x)
{
  if(Top < (Base + StackSize))
  {
    *(++Top) = x;
    return true;  
  }  
  else return false;
}

bool IntStack::Pop(int &x)
{
  if(!IsEmpty())
  {
    x = *(Top--);
    return true;
  }  
  else
  {
    x = 0;
    return false;
  }  
}

typedef struct BiTreeNode{
  char Data;
  BiTreeNode *LChild, *RChild;
};

/* Class and Strcuture Defination Ended */

BiTreeNode *Root;

BiTreeNode* CreateBiTree()
{
  char N;
  cin >> N;
  if(N==';')
  {
    return NULL;
  }
  else
  {
    BiTreeNode *T;
    T = new BiTreeNode;
    T->Data = N;
    T->LChild = CreateBiTree();
    T->RChild = CreateBiTree();
    return T;
  }  
}  

void PreOrder(BiTreeNode *T)
{
  if(T)
  {
    cout << T->Data << ", ";
    PreOrder(T->LChild);
    PreOrder(T->RChild);
  }
}

void InOrder(BiTreeNode *T)
{
  IntStack St(256);
  St.Push((int)T);
  while(!St.IsEmpty()) 
  {
    while(St.GetTop() != 0) St.Push((int)(((BiTreeNode*)St.GetTop())->LChild));
    int T;
    St.Pop(T);
    if(!St.IsEmpty())
    {
      St.Pop(T);
      cout << ((BiTreeNode*)T)->Data << ", ";
      St.Push((int)(((BiTreeNode*)T)->RChild));
    }  
  }    
}

void LaOrder(BiTreeNode *T)
{
  if(T)
  {
    LaOrder(T->LChild);
    LaOrder(T->RChild);
    cout << T->Data << ", "; 
  }  
}

void LayerOrder(BiTreeNode *T)
{
  Queue Q;
  Q.InQueue((int)T);
  while(Q.GetSize()>0)
  {
    int Temp;
    Q.OutQueue(Temp);
    cout << ((BiTreeNode*)Temp)->Data << ", ";
    if((((BiTreeNode*)Temp)->LChild)) Q.InQueue((int)(((BiTreeNode*)Temp)->LChild));
    if((((BiTreeNode*)Temp)->RChild)) Q.InQueue((int)(((BiTreeNode*)Temp)->RChild));
  }  
}

int ShowMenu()
{
  cout << endl;
  cout << "1、由前序序列建立树" << endl;
  cout << "2、前序遍历树" << endl;
  cout << "3、中序遍历树(非递归)" << endl;
  cout << "4、后序遍历树" << endl;
  cout << "5、层序遍历树" << endl;
  cout << "0、结束" << endl;
  cout << "请选择一项操作：";
  int m;
  cin >> m;
  if((m > 5)||(m < 0))
  {
    cout << endl << "输入错误！" << endl;
    return 5;
  }
  else
  {
    switch(m)
    {
      case 1: 
      {
        cout << "请输入二叉树的前序序列，用“;”作为分割符。" << endl;
        Root = CreateBiTree();
      }break;
      case 2: 
      {
        PreOrder(Root);
        cout << endl << endl;
      }break;
      case 3: 
      {
        InOrder(Root);
        cout << endl << endl;
      }break;
      case 4: 
      {
        LaOrder(Root);
        cout << endl << endl;
      }break;
      case 5:
      {
        LayerOrder(Root);
        cout << endl << endl;
      }    
    }
    return m;
  }
}

int main(int argc, char *argv[])
{
  system("CLS");
  cout << "数据结构练习：二叉树的操作" << endl;
  while( ShowMenu() != 0 ){}
  system("PAUSE");	
  return 0;
}