关于二叉树的非递归的三种遍历要做到熟练。
总结三种非递归遍历方式
前序——中，左，右
1.将根节点直接入栈
- 访问栈顶元素，出栈
- 将当前结点的右孩子和左孩子入栈
循环2，3直到栈空
中序——左，中，右
1.若树不空，则将根节点的所有左孩子入栈
- 取栈顶元素，输出，出栈
- 若当前元素的右孩子不空，入栈
循环1，2，3直到栈空
后序——左，右，中
- 创建pre，指向上一次访问的结点
- pre为空或者pre为current结点的父亲结点，则将当前结点的左孩子入栈。
- 若pre是current的左孩子，则将current的右孩子入栈。
- 否则，输出current结点值，出栈。
循环1，2，3直到栈空
#include<iostream>
#include<stack>
using namespace std;
typedef struct BTNode{
char data;
BTNode * left;
BTNode * right;
}BTNode;
//BTNode * CT(BTNode * root, int value)
//{
//
//}
BTNode * CreateTree(BTNode * root)
{
char e;
cout << "input:" << endl;
cin.get(e);
cin.get();
if (e == '0')
{
root = nullptr;
}
else
{
root = (BTNode *)malloc(sizeof(BTNode));
root->left = root->right = nullptr;
root->data = e;
root->left = CreateTree(root->left); //创建左子树
root->right = CreateTree(root->right); //创建右子树
}
return root;
}
//递归遍历
void preorder(BTNode * root)//先序
{
if (root)
{
cout << root->data << endl;
preorder(root->left);
preorder(root->right);
}
}
void inorder(BTNode * root)//中序
{
if (root)
{
inorder(root->left);
cout << root->data << endl;
inorder(root->right);
}
}
void postorder(BTNode * root)//后序
{
if (root)
{
postorder(root->left);
postorder(root->right);
cout << root->data << endl;
}
}
//非递归方法
void preOrder(BTNode * root)//先序
{
stack <BTNode *> s;
if (root == nullptr)
return;
BTNode * current = root;
s.push(root);//根结点入栈
while (!s.empty())
{
current = s.top();
cout << current->data << endl;
s.pop();
if (current->right)//分别将当前结点的右孩子和左孩子入栈。
s.push(current->right);
if (current->left)
s.push(current->left);
}
}
void freeTree(BTNode * root)//释放二叉树
{
if (root)
{
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
//利用栈实现，中序遍历非递归算法
//思想：将当前指针的所有左孩子的左孩子都入栈，
//然后出栈，输出当前值
//最后，将current指针移到右孩子
//回去循环
void inOrder(BTNode * root)
{
stack<BTNode *> s;
BTNode * current = root;
//s.push(current);
while (!s.empty() || current)
{
while (current)//将当前结点的所有左孩子入栈
{
s.push(current);
current = current->left;
}
if (!s.empty())
{
current = s.top();
s.pop();
cout << current->data << endl;//输出当前元素
current = current->right;//将当前指针移动到输出结点的右子树
}
}
}
void afterOrder(BTNode * root)
{
stack<BTNode *> s;
BTNode * current =root, *pre = nullptr;//pre指针指向前一个输出或者访问的结点
int flag;
if (root == nullptr)
return;
s.push(root);
while (!s.empty())
{
current = s.top();
if (pre == nullptr || pre->left == current || pre->right == current)//若pre指向当前栈顶元素的父亲节点或者当前结点为空的时候，左孩子入栈
{
if (current->left)
s.push(current->left);
//else if (current->right)
// s.push(current->right);//这个情况是面对左孩子为空
}
else if (pre == current->left)
{
if (current->right)
s.push(current->right);
}
else
{
cout << current->data << endl;
s.pop();
}
pre = current;
}
}
int main(void)
{
char pre[6] = { 'A', 'B', 'C', 'D', 'E', 'F' };
char in[6] = { 'C', 'B', 'A', 'E', 'D', 'F' };
BTNode * root;
root = CreateTree(nullptr);
cout << "preorder" << endl;
preorder(root);
cout << "preOrder" << endl;
preOrder(root);
cout << "inorder" << endl;
inorder(root);
cout << "inOrder" << endl;
inOrder(root);
cout << "postorder" << endl;
postorder(root);
cout << "afterorder" << endl;
afterOrder(root);
cout << root << endl;
freeTree(root);
cout << root << endl;
system("pause");
return 0;
}
注意：使用free（p），释放p指的内存后，p指针的值不是一个空指针，在VS2013中p的值与释放前的值相同。。只是告诉编辑器这块内存不能使用了
后序非递归参考博客
https://www.cnblogs.com/llhthinker/p/4747962.html
该博客中还利用两个栈来实现后序非递归遍历。
