在网上看了一些用非递归实现先序中序后序遍历二叉树的代码,都很混乱,while、if各种组合嵌套使用,逻辑十分不清晰,把我也搞懵了。想了大半天,写了大半天,突然开了窍,实际上二叉树的这三种遍历在逻辑上是十分清晰的,所以才可以用递归实现的那么简洁。既然逻辑如此清晰,那么用非递归实现也应该是清晰的。
自认为自己的代码比网上搜到的那些都清晰得多,好理解得多。
稍微解释一下:
先序遍历。将根节点入栈,考察当前节点(即栈顶节点),先访问当前节点,然后将其出栈(已经访问过,不再需要保留),然后先将其右孩子入栈,再将其左孩子入栈(这个顺序是为了让左孩子位于右孩子上面,以便左孩子的访问先于右孩子;当然如果某个孩子为空,就不用入栈了)。如果栈非空就重复上述过程直到栈空为止,结束算法。
中序遍历。将根节点入栈,考察当前节点(即栈顶节点),如果其左孩子未被访问过(有标记),则将其左孩子入栈,否则访问当前节点并将其出栈,再将右孩子入栈。如果栈非空就重复上述过程直到栈空为止,结束算法。
后序遍历。将根节点入栈,考察当前节点(即栈顶节点),如果其左孩子未被访问过,则将其左孩子入栈,否则如果其右孩子未被访问过,则将其右孩子入栈,如果都已经访问过,则访问其自身,并将其出栈。如果栈非空就重复上述过程直到栈空为止,结束算法。
其实,这只不过是保证了先序中序后序三种遍历的定义。对于先序,保证任意一个节点先于其左右孩子被访问,还要保证其左孩子先于右孩子被访问。对于中序,保证任意一个节点,其左孩子先于它被访问,右孩子晚于它被访问。对于后序,保证任意一个节点的左孩子右孩子都先于它被访问,其中左孩子先于右孩子被访问。如是而已。
代码里应该体现得比较清楚。这里不光给出了非递归版本,也给出了递归版本。
view plaincopy to clipboardprint?
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode
{
int data;
TreeNode* left;
TreeNode* right;
int flag;
};
typedef TreeNode *TreePtr;
TreePtr CreateTree()
{
TreePtr root = new TreeNode;
cout<<"input the data :\n";
int n;
cin>>n;
if (n == -1)
{
return NULL;
}
else
{
root->data = n;
root->flag = 0;
root->left = CreateTree();
root->right = CreateTree();
}
return root;
}
void PreOrderRecursion(TreePtr p)
{
if (p == NULL)
{
return;
}
cout<<p->data<<" ";
PreOrderRecursion(p->left);
PreOrderRecursion(p->right);
}
void InOrderRecursion(TreePtr p)
{
if (p == NULL)
{
return;
}
InOrderRecursion(p->left);
cout<<p->data<<" ";
InOrderRecursion(p->right);
}
void PostOrderRecursion(TreePtr p)
{
if (p == NULL)
{
return;
}
PostOrderRecursion(p->left);
PostOrderRecursion(p->right);
cout<<p->data<<" ";
}
void PreOrderNoRecursion(TreePtr p)
{
cout<<"PreOrderNoRecursion\n";
stack<TreeNode> stk;
TreeNode t = *p;
stk.push(t);
while (!stk.empty())
{
t = stk.top();
stk.pop();
cout<<t.data<<" ";
if (t.right != NULL)
{
stk.push((*t.right));
}
if (t.left != NULL)
{
stk.push((*t.left));
}
}
}
void InOrderNoRecursion(TreePtr p)
{
cout<<"InOrderNoRecursion\n";
stack<TreeNode> stk;
TreeNode t = *p;
stk.push(t);
while (!stk.empty())
{
if (stk.top().flag == 0)
{
stk.top().flag++;
if (stk.top().left != NULL)
{
stk.push(*(stk.top().left));
}
}
else
{
t = stk.top();
stk.pop();
cout<<t.data<<" ";
if (t.right != NULL)
{
stk.push(*(t.right));
}
}
}
}
void PostOrderNoRecursion(TreePtr p)
{
cout<<"PostOrderNoRecursion\n";
stack<TreeNode> stk;
TreeNode t = *p;
stk.push(t);
while (!stk.empty())
{
if (stk.top().flag == 0)
{
stk.top().flag++;
if (stk.top().left != NULL)
{
stk.push(*(stk.top().left));
}
}
else if (stk.top().flag == 1)
{
stk.top().flag++;
if (stk.top().right != NULL)
{
stk.push(*(stk.top().right));
}
}
else
{
cout<<stk.top().data<<" ";
stk.pop();
}
}
}
int main()
{
TreePtr t = CreateTree();
cout<<"PreOrderRecursion\n";
PreOrderRecursion(t);
cout<<"\n";
cout<<"InOrderRecursion\n";
InOrderRecursion(t);
cout<<"\n";
cout<<"PostOrderRecursion\n";
PostOrderRecursion(t);
cout<<"\n";
PreOrderNoRecursion(t);
cout<<"\n";
InOrderNoRecursion(t);
cout<<"\n";
PostOrderNoRecursion(t);
cout<<"\n";
}
分享到:
相关推荐
数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
二叉树的先序中序后序遍历 有递归与非递归两中做法
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
数据结构中关于二叉树的遍历,非递归算法数上未给出
从键盘输入二叉树的各结点... 2 )分别实现先序、中序、后序递归遍历二叉树 3 )输出二叉树的高度 4 )输出二叉树的按层次遍历序列 5 )输出二叉树的先序非递归遍历下的结点访问次序 6 )以菜单方式运行
建立二叉树,以括号表示法输出二叉树,求二叉树的先序遍历,中序遍历,后序遍历输出~~~
二叉树先序、中序、后序遍历(递归、非递归算法) 其中自己已经开发了栈!
//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include “stdafx.h”#include<iostream>#include<string>#include <stack>using namespace std;template<class>struct BiNode{ T data; struct...
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
遍历二叉树 MFC 先序 中序 后序 非递归 实现创建并遍历二叉树
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
二叉树先序、中序、后序三种遍历的非递归算法
采用二叉链表存储先序建立二叉树,非递归中序遍历二叉树算法实现
二叉树先序中序后序三种遍历的非递归算法.doc
二叉树先序,中序,后序遍历非递归实现 二叉树先序,中序,后序遍历非递归实现
本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,...
二叉树.非递归算法.先序遍历.中序遍历.后序遍历.doc