中序遍历思想

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

图1遍历的顺序为：GDHBAEICF。

算法实现

【递归算法】

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

#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 InOrderTraverse(BiTree T)
{
  if (T)
  {
    InOrderTraverse(T->lchild);
    DisplayElem(T);
    InOrderTraverse(T->rchild);
  }
}

int main()
{
  BiTree Tree;
  CreateBiTree(&Tree);
  std::cout << "中序遍历" << std::endl;
  InOrderTraverse(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 InOrderTraverse(BiTree T)
{
  BiTNode* top = T;
  std::stack<BiTNode*> sta;
  while (top || !sta.empty())
  {
    if (top)
    {
      sta.push(top);/*根结点和左孩子入栈*/
      top = top->lchild;
    }
    else
    {
      top = sta.top();
      sta.pop();/*左孩子出栈*/
      DisplayElem(top);
      top = top->rchild;/*开始遍历右孩子*/
    }
  }
}
/*主函数*/
int main()
{
  BiTree Tree;
  CreateBiTree(&Tree);
  std::cout << "中序遍历" << std::endl;
  InOrderTraverse(Tree);
  std::cout << std::endl;
  return 0;
}

从中序遍历的代码中可以看出，重点是将根结点和左孩子结点压栈出栈。

完整代码

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