bitree.h

数据结构试验 实验一 线性表的顺序表示与实现 实验二 线性表的链式表示与实现 实验三 栈与队列及其应用 实验四 二叉树的应用 实验五 图的遍历与应用 实验六 查找技术 实验七 内部排序

#include <iostream>
#include <stack>
using namespace std;
typedef int telemtype;
struct bitnode 
{
  bitnode* lchild;
  bitnode* rchild;
  telemtype data;
  bitnode(int e=0, bitnode* left=NULL, bitnode* right=NULL)
  {
    data = e;
    lchild = left;
    rchild = right;
  }
};

class Tree
{
  
public:
  Tree()
  {
    root = NULL;
  }
  Tree(int array[], int size);
  ~Tree();
  void traverse();
  void postTraverse();
  void recur_postTraverse(bitnode* cur);
  void preTraverse();
  void recur_preTraverse(bitnode* cur);
  void inTraverse();
  void recur_inTraverse(bitnode* cur);

private:
  Tree(const Tree& t);
  Tree& operator=(const Tree& t);
  bitnode* createTree(int array[], int size);
  void destroyTree(bitnode* cur);
private:
  bitnode* root;
  
};

Tree::Tree(int array[], int size)
{
  if ((array==NULL)||(size<=0))
    root = NULL;
  else
    root = createTree(array, size);
}
//建树
bitnode* Tree::createTree(int array[], int size)
{
  if ((array==NULL)||(size<=0))
    return NULL;
  int mid=size/2;
  bitnode* cur=new bitnode(array[mid]);
  cur->lchild = createTree(array, mid);
  cur->rchild = createTree(array+mid+1, size-mid-1);
  return cur;
}

Tree::~Tree()
{
  destroyTree(root);
}

void Tree::destroyTree(bitnode* cur)
{
  if (cur != NULL)
  {
    destroyTree(cur->lchild);
    destroyTree(cur->rchild);
    delete cur;
  }
  
}


//后序递归遍历

void Tree::recur_postTraverse(bitnode* cur)
{
  if (cur!=NULL)
  {
    recur_postTraverse(cur->lchild);
    recur_postTraverse(cur->rchild);
    cout << cur->data << " ";
  }
}

//先序递归遍历

void Tree::recur_preTraverse(bitnode* cur)
{
  if (cur!=NULL)
  {
    cout << cur->data << " ";
    recur_preTraverse(cur->lchild);
    recur_preTraverse(cur->rchild);
  }
}

//中序递归遍历

void Tree::recur_inTraverse(bitnode* cur)
{
  if (cur!=NULL)
  {
    recur_inTraverse(cur->lchild);
    cout << cur->data << " ";
    recur_inTraverse(cur->rchild);
  }
}

//后序非递归遍历

void Tree::postTraverse()
{
  stack<bitnode*> treeStack;
  bitnode *pre, *cur;
  cur = root;
  pre = NULL;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    if (((cur->lchild==NULL)&&(cur->rchild==NULL))|| //没有孩子结点或者

        ((pre!=NULL)&&((pre==cur->lchild)||(pre==cur->rchild)))) //孩子遍历过了

    {
      treeStack.pop();
      cout << cur->data << " ";
      pre = cur;
    }
    else
    {
      if (cur->rchild!=NULL)
        treeStack.push(cur->rchild);
      if (cur->lchild!=NULL)
        treeStack.push(cur->lchild);
    }
   
  }
  
}

//中序非递归遍历

void Tree::inTraverse()
{
  stack<bitnode*> treeStack;
  bitnode  *cur;
  cur = root;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    treeStack.pop();
    if (cur == NULL)
      continue;
    if ((cur->lchild==NULL)|| //没有左孩子或者

        ((!treeStack.empty())&&(treeStack.top()==cur->rchild))) //右孩子已经入过栈

      cout << cur->data << " ";
    else
    {
      treeStack.push(cur->rchild);
      treeStack.push(cur);
      if (cur->lchild!=NULL)
        treeStack.push(cur->lchild);
    }
   
  }
}

//先序非递归遍历

void Tree::preTraverse()
{
  stack<bitnode*> treeStack;
  bitnode  *cur;
  cur = root;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    treeStack.pop();
    cout << cur->data << " ";
    if (cur->rchild!=NULL)
      treeStack.push(cur->rchild);
    if (cur->lchild!=NULL)
      treeStack.push(cur->lchild);
  }
}


void Tree::traverse()
{
  cout<<"递归前序遍历二叉树"<<endl;
  recur_preTraverse(root);
  cout << endl;
    cout<<"非递归前序遍历二叉树"<<endl;
  preTraverse();
  cout << endl << endl;

  cout<<"递归中序遍历二叉树"<<endl;
  recur_inTraverse(root);
  cout << endl;
   cout<<"非递归中序遍历二叉树"<<endl;
  inTraverse();
  cout << endl << endl;

    cout<<"递归后序遍历二叉树"<<endl;
  recur_postTraverse(root);
  cout << endl;
   cout<<"非递归后序遍历二叉树"<<endl;
  postTraverse();
  cout << endl << endl;
}