二叉树中序遍历非递归算法实现详解

二叉树是数据结构中的经典结构，也是应用很广泛的结构之一。二叉树具有一些特定的性质，如 n0 = n2+1，在一些应用中，常常要求在树中查找具有某些特征的节点，或者对树中节点进行处理，即遍历二叉树的问题，其递归算法非常容易实现，非递归算法也有两种思路，本文将在程序中实现笔者认为容易识记的一种方法。

输入序列二叉树：

程序实现：

#include <iostream>
#include <stack>


using std::cin;
using std::cout;
using std::endl;
using std::stack;


// 定义二叉树结构, BiTree 为指针类型
typedef struct BiTreeNode{
int data;
struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;


// &T 必须，可以试试去掉的后果 
// 输入为先序序列的顺序，如图 输入序列为： 1 2 0 0 3 4 6 0 0 7 0 0 5 0 8 0 0
// 0 - 表示 NULL，这里为了测试而设置的
BiTree fn_CreateBiTree(BiTree &T)
{
int data;
cin>>data;

if(data==0)T=NULL; // 遇到值为0的，将其置为NULL，表示为空
else{
if(!(T = (BiTree)new BiTreeNode))exit(0);
T->data=data;
fn_CreateBiTree(T->lchild);
fn_CreateBiTree(T->rchild);
}
return(T);
}


// 先序遍历 递归实现
void fn_PreOrderTraverse(BiTree T)
{
if(T)
{
if(T->data)
{
cout<<T->data<<'\t';
fn_PreOrderTraverse(T->lchild);
fn_PreOrderTraverse(T->rchild);
}
return;
}
else 
return;
}


// 中序遍历 递归实现
void fn_MidOrderTraverse(BiTree T)
{
if(T)
{
if(T->data)
{
fn_MidOrderTraverse(T->lchild);
cout<<T->data<<'\t';
fn_MidOrderTraverse(T->rchild);
}
return;
}
else 
return;
}


// 中序遍历 非递归
void InOrderTraverse(BiTree T)
{
stack<BiTree> NodeStack; // 需要用到栈
BiTree p; // 遍历的指针变量，类似于游标功能

if(T)  // 非空二叉树
{
p = T;
while(p || !NodeStack.empty())// 若p不为空，或者栈非空，则进入循环
{                               // 初始p非空，栈为空
if(p)
{
NodeStack.push(p);      // 将非空节点入栈，向左孩子遍历
p=p->lchild;
}
else                        // 此时p为空，则p的父节点为栈顶指针，为分支最左的孩子，输出
{
p = NodeStack.top();    // 将p赋值为栈顶指针
cout<<p->data<<'\t';          // 输出分支最左孩子
NodeStack.pop();        // 删除栈顶指针
p = p->rchild;          // 将p赋值给其右孩子，继续遍历其右孩子分支
}
}
}
else
return;
}


void main(void)
{
BiTree T;
cout<<"输入二叉树序列，创建二叉树："<<endl;
T = fn_CreateBiTree(T);
cout<<endl;
cout<<"输出先序遍历-递归算法："<<endl;
fn_PreOrderTraverse(T);
cout<<endl;
cout<<"输出中序遍历-递归算法："<<endl;
fn_MidOrderTraverse(T);
cout<<endl;
cout<<"输出中序遍历-非递归算法："<<endl;
InOrderTraverse(T);
cout<<endl;
}

程序运行结果：