数据结构之二叉树的递归遍历和非递归遍历

一、二叉树
在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
二、二叉树的遍历

前序遍历（DLR）
前序遍历也叫做先根遍历，可记做根左右。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
  （1）访问根结点
  （2）前序遍历左子树
  （3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。

中序遍历（LDR）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
后序遍历（LRD）
后序遍历也叫做后根遍历，可记做左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。

输入abc###de##f##验证

#include<iostream>
#include<cstdio>
#include<stack>
#define false 0
#define ok 1
#define stack_size 100
using namespace std;
typedef struct bitnode{
  char data;
  struct bitnode *lchild,*rchild;
}bitnode,*bitree;
//创建一个二叉树（以先序建立）
int creatbitree(bitree &t){
  char ch;
  if(cin>>ch&&ch=='#'){
  t=NULL;
  return false;
}
  else{
    t=(bitree)malloc(sizeof(bitnode));
    t->data=ch;
    creatbitree(t->lchild);
    creatbitree(t->rchild);
  }
  return ok;
}
void visit(char data){
  cout<<data<<" ";
}
//递归运算三种遍历
int prebitree(bitree &t){
  if(t){
    visit(t->data);
    prebitree(t->lchild);
    prebitree(t->rchild);
  }
  return ok;
}//先序递归遍历
int midbitree(bitree &t){
    if(t){
      midbitree(t->lchild);
      visit(t->data);
      midbitree(t->rchild);
    }
    return ok;
}//中序递归遍历
int houbitree(bitree &t){
  if(t){
    houbitree(t->lchild);
    houbitree(t->rchild);
    visit(t->data);
  }
  return ok;
}//后序递归遍历
int pre_bitree(bitree t){
  stack<bitree>stack;
  bitree p=t;
  while(p||!stack.empty()){
      if(p!=NULL){
        cout<<p->data<<" ";//先输出根结点
        stack.push(p);//
        p=p->lchild;
      }
      else{
        p=stack.top();
        stack.pop();
        p=p->rchild;
      }
}
return ok;
}
int mid_bitree(bitree t){
  stack<bitree>stack;
  bitree p=t;
  while(p||!stack.empty()){
    if(p!=NULL){
      stack.push(p);//先让根结点进栈。
      p=p->lchild;//然后让左子树进栈
    }
    else{
      p=stack.top();//获得栈顶元素
      stack.pop();//删除栈顶元素
      cout<<p->data<<" ";//输出栈顶元素
      p=p->rchild;//让右子树进栈
    }
  }
  return ok;
  //这一部分看图就可以理解
}
int hou_bitree(bitree t){
  stack<bitree>stack;
  bitree e,previsit;//e表示可移动的结点，pre表示已将访问过的上一个结点
  e=t;
  while(e){
    stack.push(e);//根节点进栈
    e=e->lchild;//左子树进栈
  }
  while(e||!stack.empty()){
    e=stack.top();
    stack.pop();
    if(e->rchild==NULL||e->rchild==previsit){
      cout<<e->data<<" ";
      previsit=e;//这个标记很重要，最后重复利用他
    }
    else{
      stack.push(e);//因为前面删除了一次根节点，所以根节点再次进栈
      e=e->rchild;//让右子树进栈
      while(e){
        stack.push(e);
        e=e->lchild;//让右子树中的左子树进栈
      }
    }
  }
  return ok;
}
int main(int argc, char const *argv[]) {
  bitree t;
  creatbitree(t);
  prebitree(t);
  cout<<"_____________________________"<<endl;
  midbitree(t);
  cout<<"_____________________________"<<endl;
  houbitree(t);
  cout<<"_____________________________"<<endl;
  pre_bitree(t);
  cout<<"_____________________________"<<endl;
  mid_bitree(t);
  cout<<"_____________________________"<<endl;
  hou_bitree(t);
  cout<<"_____________________________"<<endl;
  cout<<endl;
  return 0;
}