bintree.cpp

二叉树的非递归遍历算法 可以直接上交

#ifndef BinTree_CPP
#define BinTree_CPP

#include "BinTree.h"

template <class T>
BinTree<T>::BinTree()
{ m_Root=NULL; } 

template <class T>
BinTree<T>::~BinTree()
{ Free(); }

template <class T>
BinTree<T>::BinTree(vector<T> &pre) // 根据pre创建二叉树
{ m_pre=pre; m_prei=0;      // 完成数据准备
  m_Root=DoCreateByPre(); // 调用核心函数
}

template <class T>
BinTreeNode<T> *BinTree<T>::DoCreateByPre()
{ T e=m_pre[m_prei];   m_prei++;
  if(e=='*') return(NULL); 
  BinTreeNode<T> *p=new BinTreeNode<T>;
  p->data=e;
  p->lchild=DoCreateByPre();  // 建左子树
  p->rchild=DoCreateByPre();  // 建右子树
  return(p);
}

template <class T>
void BinTree<T>::Free()  // 释放整个树的空间
{ DoFree(m_Root); m_Root=NULL; }

template <class T>
void BinTree<T>::DoFree(BinTreeNode<T> *p)
{ if(p==NULL)  return;
  DoFree( p->lchild );  // 释放左子树
  DoFree( p->rchild );  // 释放右子树
  delete p;                  // 按后序次序
}

template <class T>
void BinTree<T>::TraverseDFS(int kind)  // 深度遍历二叉树
{ stack<Status<T> > S;
  Status<T> s1={m_Root,START};  
  S.push(s1);
  while( !S.empty() )
  { Status<T> &s=S.top(); // s是栈顶状态的引用
    Status<T> nexts;
    switch (s.flag)
    { case START:
        if(kind==1) cout<<s.p->data<<" ";
        if(s.p->lchild)  // 若存在左孩子，向左孩子方向前进
        { nexts.p=s.p->lchild; nexts.flag=START;
          S.push(nexts); 
        }
        s.NextFlag();    // 调整栈顶状态的方向
        break;
      case LEFT:
        if(kind==2) cout<<s.p->data<<" ";  
        if(s.p->rchild) // 若存在左孩子，向左孩子方向前进
        { nexts.p=s.p->rchild; nexts.flag=START;
          S.push(nexts); 
        }
        s.NextFlag();    // 调整栈顶状态的方向
        break;
      case RIGHT:  
        if(kind==3) cout<<s.p->data<<" ";  
        S.pop(); 
     } 
   }   
  cout<<endl;
}


#endif