后序遍历思想

二叉树后序遍历的思想是： 1） 访问左子树；2） 访问右子树；3） 访问根结点。

图1遍历的顺序为：GHDBIEFCA。

算法实现

【递归算法】

二叉树的后序遍历采用的是递归思想：

#include <iostream>
#include <string>
#define ElemType char
typedef struct BiTNode
{
  ElemType data;	//数据域
  struct BiTNode* lchild, * rchild;		//左右孩子指针
}BiTNode, * BiTree;
//构建树的函数
void CreateBiTree(BiTree* Tree)
{
  *Tree = (BiTNode*)malloc(sizeof(BiTNode));
  /*第一层*/
  (*Tree)->data = 'A';
  (*Tree)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  /*第二层*/
  (*Tree)->lchild->data = 'B';
  (*Tree)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->lchild->rchild = NULL;
  (*Tree)->rchild->data = 'C';
  (*Tree)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  /*第三层*/
  (*Tree)->lchild->lchild->data = 'D';
  (*Tree)->lchild->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->lchild->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->lchild->data = 'E';
  (*Tree)->rchild->lchild->lchild = NULL;
  (*Tree)->rchild->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->rchild->data = 'F';
  (*Tree)->rchild->rchild->lchild = NULL;
  (*Tree)->rchild->rchild->rchild = NULL;
  /*第四层*/
  (*Tree)->lchild->lchild->lchild->data = 'G';
  (*Tree)->lchild->lchild->lchild->lchild = NULL;
  (*Tree)->lchild->lchild->lchild->rchild = NULL;
  (*Tree)->lchild->lchild->rchild->data = 'H';
  (*Tree)->lchild->lchild->rchild->lchild = NULL;
  (*Tree)->lchild->lchild->rchild->rchild = NULL;
  (*Tree)->rchild->lchild->rchild->data = 'I';
  (*Tree)->rchild->lchild->rchild->lchild = NULL;
  (*Tree)->rchild->lchild->rchild->rchild = NULL;
}
//模拟操作结点元素的函数，输出结点本身的数值
void DisplayElem(BiTNode* elem)
{
  std::cout << elem->data << " ";
}
/*后序遍历*/
void ProOrderTraverse(BiTree T)
{
  if (T)
  {
    ProOrderTraverse(T->lchild);
    ProOrderTraverse(T->rchild);
    DisplayElem(T);
  }
}
/*主函数*/
int main()
{
  BiTree Tree;
  CreateBiTree(&Tree);
  std::cout << "后序遍历" << std::endl;
  ProOrderTraverse(Tree);
  std::cout << std::endl;
  return 0;
}

【非递归算法】

递归的实现过程是依靠栈存储结构，因此可以申请一块内存模拟递归的过程。后序非递归遍历中，访问根（子根）结点有两种情况

• 遍历完左子树，需要遍历右子树，需要从栈中访问最顶上的根（子根）结点从而得到右子树的指针。
• 遍历完右子树，需要访问根（子根）结点。

基于这个特性，我们需要区分，到底这个根结点，是访问完了左子树还是右子树，所以需要添加一个变量帮助辨认。

#include <iostream>
#include <string>
#include <stack>
#define ElemType char
typedef struct BiTNode
{
  ElemType data;	//数据域
  struct BiTNode* lchild, * rchild;		//左右孩子指针
}BiTNode, * BiTree;
//构建树的函数
void CreateBiTree(BiTree* Tree)
{
  *Tree = (BiTNode*)malloc(sizeof(BiTNode));
  /*第一层*/
  (*Tree)->data = 'A';
  (*Tree)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  /*第二层*/
  (*Tree)->lchild->data = 'B';
  (*Tree)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->lchild->rchild = NULL;
  (*Tree)->rchild->data = 'C';
  (*Tree)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  /*第三层*/
  (*Tree)->lchild->lchild->data = 'D';
  (*Tree)->lchild->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->lchild->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->lchild->data = 'E';
  (*Tree)->rchild->lchild->lchild = NULL;
  (*Tree)->rchild->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
  (*Tree)->rchild->rchild->data = 'F';
  (*Tree)->rchild->rchild->lchild = NULL;
  (*Tree)->rchild->rchild->rchild = NULL;
  /*第四层*/
  (*Tree)->lchild->lchild->lchild->data = 'G';
  (*Tree)->lchild->lchild->lchild->lchild = NULL;
  (*Tree)->lchild->lchild->lchild->rchild = NULL;
  (*Tree)->lchild->lchild->rchild->data = 'H';
  (*Tree)->lchild->lchild->rchild->lchild = NULL;
  (*Tree)->lchild->lchild->rchild->rchild = NULL;
  (*Tree)->rchild->lchild->rchild->data = 'I';
  (*Tree)->rchild->lchild->rchild->lchild = NULL;
  (*Tree)->rchild->lchild->rchild->rchild = NULL;
}
//模拟操作结点元素的函数，输出结点本身的数值
void DisplayElem(BiTNode* elem)
{
  std::cout << elem->data << " ";
}
/*后序遍历*/
void ProOrderTraverse(BiTree T)
{
  std::stack<BiTNode*> sta;
  BiTNode* top = T;
  BiTNode* vis = nullptr;/*临时变量，记录上一个访问到的结点，因为从右边访问根结点，
  																		必定是右子树已经遍历结束，此时上一个访问的结点必定是右子树的根结点*/
  while (top || !sta.empty())
  {
    if (top)
    {
      sta.push(top);
      top = top->lchild;
    }
    else
    {
      top = sta.top();//只读取根结点，不对栈内结点进行操作
      if (top->rchild && top->rchild != vis)//没有对右子树进行操作过
      {
        top = top->rchild;
        sta.push(top);
        top = top->lchild;
      }
      else
      {
        sta.pop();
        DisplayElem(top);//对top进行访问，可以进行打印等操作
        vis = top;//记录当前访问的是p结点
        top = nullptr;//把p置空，进入下一次循环，直到栈内无元素，且p为空时遍历完成
      }
    }
  }
}
/*主函数*/
int main()
{
  BiTree Tree;
  CreateBiTree(&Tree);
  std::cout << "后序遍历" << std::endl;
  ProOrderTraverse(Tree);
  std::cout << std::endl;
  return 0;
}

完整代码

GitHub: https://github.com/MrYuxiangZhu/DataStructure/tree/master/06.%20Tree