C++算法二叉树中序遍历

非递归中序遍历二叉树思路（借助栈实现）：
1、依次将所有左子节点压栈，直至为空；
2、弹出栈顶元素，访问栈顶，将栈顶的右子节点压栈，返回步骤1；
3、直至栈空。
（**递归的本质也是通过函数栈来实现代码的简化，故二叉树的递归遍历思路一样。一般的，递归算法大部分可以通过栈或者循环实现非递归化 **）

一、定义二叉树结构体

#include "stdafx.h"
#include "iostream"
#include <stack>
#include <algorithm>
using namespace std;
#define TElemType int
// 二叉树结构体定义
struct BiTree
{TElemType data;//数据域struct BiTree *lchild, *rchild;//左右孩子指针
};

二、初始化二叉树

void CreateBiTree(BiTree *T)
{// 搁外边分配空间，防止出作用域内存被释放// T = new BiTree;(T)->data = 1;(T)->lchild = new BiTree;(T)->rchild = new BiTree;(T)->lchild->data = 2;(T)->lchild->lchild = new BiTree;(T)->lchild->rchild = new BiTree;(T)->lchild->rchild->data = 5;(T)->lchild->rchild->lchild = NULL;(T)->lchild->rchild->rchild = NULL;(T)->rchild->data = 3;(T)->rchild->lchild = new BiTree;(T)->rchild->lchild->data = 6;(T)->rchild->lchild->lchild = NULL;(T)->rchild->lchild->rchild = NULL;(T)->rchild->rchild = new BiTree;(T)->rchild->rchild->data = 7;(T)->rchild->rchild->lchild = NULL;(T)->rchild->rchild->rchild = NULL;(T)->lchild->lchild->data = 4;(T)->lchild->lchild->lchild = NULL;(T)->lchild->lchild->rchild = NULL;
}

中序遍历递归法：

void PreOrderTraverse(BiTree *T)
{if (T) {PreOrderTraverse(T->lchild);//访问该结点的左孩子// 操作节点方法，这里只做读取输出用cout << T->data << endl;PreOrderTraverse(T->rchild);//访问该结点的右孩子}//如果结点为空，返回上一层return;
}

中序遍历非递归算法1：

void InOrderTraverse1(BiTree *Tree)
{std::stack<BiTree*> treeStack;//定义一个顺序栈BiTree *p = NULL;//临时指针treeStack.push(Tree);while (!treeStack.empty()){//栈内不为空，程序继续运行while ((p = treeStack.top()) && p){//取栈顶元素，且不能为NULLtreeStack.push(p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈}treeStack.pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈if (!treeStack.empty()) {p = treeStack.top();//取栈顶元素treeStack.pop();//栈顶元素弹栈cout << p->data << endl;treeStack.push(p->rchild);//将p指向的结点的右孩子进栈}}
}

//中序遍历非递归算法2：

void InOrderTraverse2(BiTree *Tree)
{std::stack<BiTree*> treeStack;//定义一个顺序栈BiTree *p = NULL;//临时指针p = Tree;//当p为NULL或者栈为空时，表明树遍历完成while (p || !treeStack.empty()){//如果p不为NULL，将其压栈并遍历其左子树if (p){treeStack.push(p);p = p->lchild;}//如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树else{p = treeStack.top();treeStack.pop();cout << p->data << endl;p = p->rchild;}}
}

主函数实现：

int _tmain(int argc, _TCHAR* argv[])
{BiTree *tree = new BiTree;CreateBiTree(tree);// 非递归遍历InOrderTraverse1(tree);InOrderTraverse2(tree);// 递归遍历PreOrderTraverse(tree);system("pause");delete tree;tree = NULL;return 0;
}