[小记]二叉树的先序中序后序递归非递归遍历，层次遍历和完全二叉树的判断[4.24更新]

// BinaryTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
/************************************************************************/
/* 二叉树的递归，非递归的前序，中序和后序遍历
/* 二叉树的层次遍历，和完全二叉树的判断
/************************************************************************/

#include <iostream>
#include <stack>
#include <queue>
#include <string>

using namespace std;

template<class T>
struct tree_node{
 T value;
 tree_node* left;
 tree_node* right;
 tree_node():value(),left(0),right(0){}
 tree_node(tree_node* l, tree_node* r):value(),left(l),right(r){}
};

template<class T>
struct visit{
 void operator()(const T& t){cout<<t<<" ";}
};


//递归,先序遍历
template<class T, class F>
void PreOrderTraverse_Rec(tree_node<T>* root,F func)
{
 if(root)
 {
  func(root->value); //访问节点
  PreOrderTraverse_Rec(root->left,func);
  PreOrderTraverse_Rec(root->right,func);
 }
}

//递归，中序遍历
template<class T, class F>
void InOrderTraverse_Rec(tree_node<T>* root, F func)
{
 if(root)
 {
  InOrderTraverse_Rec(root->left,func);
  func(root->value);
  InOrderTraverse_Rec(root->right,func);
 }
}

//递归，后序遍历
template<class T, class F>
void PostOrderTraverse_Rec(tree_node<T>* root, F func)
{
 if(root)
 {
  PostOrderTraverse_Rec(root->left,func);
  PostOrderTraverse_Rec(root->right,func);
  func(root->value);
 }
}

//非递归，先序遍历,版本1
template<class T, class F>
void PreOrderTraverse_Non_Rec_v1(tree_node<T>* root, F func)
{
 typedef tree_node<T>* node;
 stack< tree_node<T>* > st;
 while(root || !st.empty()) //root不为空或者栈不空，则循环遍历
 {
  if (root)//root不为空，则访问此root节点
  {
   func(root->value); 
   st.push(root);
   root = root->left; //往左访问
  }else{
   node n=st.top(); //弹出栈顶，访问右子树
   root = n->right;
   st.pop();
  }
 }
}

//非递归，先序遍历,版本2(简单版本)
template<class T, class F>
void PreOrderTraverse_Non_Rec_v2(tree_node<T>* root, F func)
{
 if(!root) return;
 stack< tree_node<T>* > st;
 st.push(root);
 while(!st.empty())
 {
  func(root->value);
  if(root->right) st.push(root->right); //右子树非空，先压入右子树
  if(root->left) st.push(root->left);
  root = st.top();
  st.pop();
 }
}

//非递归，中序遍历
template<class T, class F>
void InOrderTraverse_Non_Rec(tree_node<T>* root, F func)
{
 stack< tree_node<T>* > st;
 typedef tree_node<T>* node;

 while(root || !st.empty())
 {
  while(root) //一直往左到左子树的最左边，即整棵树的最左下
  {
   st.push(root);
   root=root->left;
  }

  if(!st.empty()) //如果不空，则弹出栈顶，访问
  {
   node n = st.top();
   func(n->value);
   st.pop();
   root = n->right; //置root为右子树，然后循环到头去访问右子树
  }
 }
}

//非递归，后续遍历
template<class T, class F>
void PostOrderTraverse_Non_Rec(tree_node<T>* root, F func)
{
 typedef tree_node<T>* node;
 stack<node> st;
 node pre=0; //表示最近的前一个访问的节点

 while(root || !st.empty())
 {
  while(root) //一直往左访问
  {
   st.push(root);
   root=root->left;
  }

  //判断是否应该访问栈顶元素,注意这里需要用root访问
  root = st.top();  //这里不用判断st是否为空，因为前面已经判断过了
  //如果右节点为空(此节点无左右孩子)，或者前面访问的节点是其右节点，则轮到自己访问
  if( ! root->right || root->right == pre) 
  {
   func(root->value);
   st.pop(); //弹出已经访问的栈顶
   pre = root;
   root = 0; //这里需要置root为空，因为无法继续往下继续访问，需要弹栈回溯访问节点
  }else{
   //继续访问右子树
   root = root->right; //如果有右子树，则不用弹栈，继续往下访问右子树
  }
 }

}

//层次遍历二叉树
template<class T, class F>
void LevelTraverse(tree_node<T>* root, F func)
{
 if(!root) return; 
 typedef tree_node<T>* node;
 queue<node> _q;
 _q.push(root);
 while(!_q.empty())
 { 
  node n=_q.front();
  func(n->value);
  _q.pop();
  if(n->left) _q.push(n->left);
  if(n->right) _q.push(n->right);
 }
}

//完全二叉树判断
template<class T>
bool judge(tree_node<T>* root)
{
 if(!root) return true; //空树
 typedef tree_node<T>* node;
 queue<node> _q;
 _q.push(root);
 node n;
 while(!_q.empty())
 {
  n=_q.front();
  _q.pop();
  if(n->left && n->right){
   _q.push(n->left);
   _q.push(n->right);
  }else
   break; //第一个缺少左或右孩子的节点，退出循环进行判断
 }

 if(_q.empty())
  return true;
 else
 {
  if(!n->left && n->right)
   return false;
  else
  {
   if(n->left) //如果左孩子不为空，则将其节点压入队列
    _q.push(n->left);

   //对于仅左孩子为空和左右孩子均为空的情况，判断队列里剩余的节点都为叶子节点
   while(!_q.empty())
   {
    node tmp=_q.front();
    _q.pop();
    if(tmp->left || tmp->right) 
     return false;
   }
  }
 }
 return true;
}

//测试
//已知前序，中序，建树，并后序访问打印后序遍历结果,以字符表示节点
tree_node<char>* GenTreeByPreInOrder(const string& preOrderS,const string& inOrderS)
{
 //std::cout<<"pre:"<<preOrderS<<"\npst:"<<inOrderS<<endl<<endl;

 if (!preOrderS.empty() && !inOrderS.empty()) //非空
 {
  char v=preOrderS[0];
  tree_node<char>* nd=new tree_node<char>(0,0);
  nd->value = v;

  int idx = inOrderS.find(v);
  if (idx != string::npos)
  {
   nd->left = GenTreeByPreInOrder(preOrderS.substr(1,idx), inOrderS.substr(0,idx));
   nd->right = GenTreeByPreInOrder(preOrderS.substr(idx+1),inOrderS.substr(idx+1));
  }
  return nd; 
 }

 return 0;
}

//测试
//已知中序和后序，建树，并打印结果
tree_node<char>* GenTreeByInPostOrder(const string& inOrderS, const string& postOrderS)
{
 //cout<<inOrderS<<":"<<postOrderS<<endl;
 if(!inOrderS.empty() && !postOrderS.empty())
 {
  //构造节点
  char v= *(postOrderS.end()-1);
  tree_node<char>* n=new tree_node<char>(0,0);
  n->value = v;

  int idx=inOrderS.find(v);
  if(idx != string::npos)
  {
   n->left = GenTreeByInPostOrder(inOrderS.substr(0,idx),postOrderS.substr(0,idx));
   n->right= GenTreeByInPostOrder(inOrderS.substr(idx+1),postOrderS.substr(idx,postOrderS.length()-idx-1));
  }
  return n;
 }
 //一定要返回空，其实是空指针
 return 0;
}

//测试
template<class T>
void out_tree(tree_node<T>* root)
{
 typedef visit<char> fun;
 cout<<"\n------------\nPre-Order:recursive,non-recursive-v1,non-recursive-v2\n";
 PreOrderTraverse_Rec(root,fun());
 cout<<"\n";
 PreOrderTraverse_Non_Rec_v1(root,fun());
 cout<<"\n";
 PreOrderTraverse_Non_Rec_v2(root,fun());
 cout<<"\n------------\nIn-Order:recursive,non-recursive\n";
 InOrderTraverse_Rec(root,fun());
 cout<<"\n";
 InOrderTraverse_Non_Rec(root,fun());
 cout<<"\n------------\nPost-Order:recursive,non-recursive\n";
 PostOrderTraverse_Rec(root,visit<char>());
 cout<<"\n";
 PostOrderTraverse_Non_Rec(root,visit<char>());
 cout<<"\n++++++++++++++++++++++++\n";
}



int _tmain(int argc, _TCHAR* argv[])
{
 string pre("abdgcefh"),in("dgbaechf"),post("gdbehfca");

 
 cout<<"Original test: pre-order-string:"<<pre<<endl;
 cout<<"Original test: in-order-string:"<<in<<endl;
 cout<<"Original test: post-order-string:"<<post<<endl;

 tree_node<char>* t1=GenTreeByPreInOrder(pre,in);
 out_tree<char>(t1);
 tree_node<char>* t2=GenTreeByInPostOrder(in,post);
 out_tree<char>(t2);
 
 return 0;
}