二叉树的中序非递归算法
中序遍历非递归算法介绍
自己用栈来模拟这个过程
1.遇到根结点根结点入栈,遍历左子树
2.如果当前的P指针为NULL,弹栈,遍历右子树
当栈和P都为空的时候结束遍历
算法示意图
伪代码实现
真正代码实现
STL永远的神
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef struct BiNode {
char data;//数据域
struct BiNode *lchild, *rchild; //左孩子右孩子
} BiNode, *BiTree;
/*
前序建立二叉树
*/
void CreateBitree(BiTree &T) {
char ch;
cin >> ch;
if (ch != '#') {
T = new BiNode;
T->data = ch; //写入根结点
CreateBitree(T->lchild);//建立左子树
CreateBitree(T->rchild);//建立右子树
} else {
T = NULL;
return;
}
}
/*
递归中序遍历
*/
void LDR(BiTree T) {
if (T != NULL) {
LDR(T->lchild);//先访问左子树
cout << T->data; //打印根结点
LDR(T->rchild);//访问右子树
} else {
return;
}
}
/*
非递归中序遍历
*/
void InOrderTraverse(BiTree T) {
stack <BiTree> s;//使用STL的栈
BiTree p = T; //让p指向根结点
while (p != NULL || s.empty() == false) { //当p不为空和栈不为空的时候进行循环
if (p != NULL) {
s.push(p);//如果根结点不为空,把根节点放入栈当中
p = p->lchild; //让p指向自己的右孩子
} else { //如果p为空
//先对栈顶元素出栈
cout << s.top()->data; //打印栈顶元素
p = s.top()->rchild; //让p指向栈顶元素指针的右孩子
s.pop();//弹出栈顶元素
}
}
}
signed main () {
BiTree root = NULL;
CreateBitree(root);
cout << "正在进行递归中序遍历\n";
LDR(root);
cout << '\n';
cout << "正在进行非递归中序遍历\n";
InOrderTraverse(root);
cout << '\n';
return 0;
}
/*
abc##de#g##f###
*/