二叉树前序，中序，后序遍历的非递归实现（c++版）

1. 二叉树后序非递归遍历：

 1#include <stack>
 2#include <iostream>
 3using namespace std;
 4
 5template <class T>
 6class TreeNode
 7{
 8  public:
 9    T data;
10    TreeNode<T> *left; //left child
11    TreeNode<T> *right; //right child
12 
13    TreeNode():left(NULL),right(NULL)
14    {
15    }
16
17    TreeNode(const T& t):data(t),left(NULL), right(NULL)
18    {
19    }
20
21    TreeNode(const T& t, TreeNode<T*> left, TreeNode<T*> right):data(t),left(left), right(right)
22    {
23    }
24};
25
26/**purpose: 对二叉树进行后序遍历（非递归算法）
27 TreeNode<T> *root :the root of the binary tree
28  */
29template <class T>
30void postOrder(TreeNode<T> *root)
31{
32  stack<TreeNode<T>*> st;
33  TreeNode<T> *p = root;
34  TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点
35 
36  while(p || st.size()!=0)
37  {
38    //沿着左孩子方向走到最左下 。
39    while(p)
40    {
41      st.push(p);
42      p = p->left;
43    }
44    //get the top element of the stack
45    p = st.top();
46    //如果p没有右孩子或者其右孩子刚刚被访问过，则访问p节点，并从栈中删除
47   if(p->right == NULL || p->right == pre)
48    {
49      //visit this element and then pop it
50      cout << "visit: " << p->data << endl;
51      st.pop();
52      pre = p; //标记最近被访问的节点
53      p = NULL; //这样，接下来可以访问父节点
54     
55    }
56   else
57   {
58     p = p->right;
59    
60   }
61  }//end of while(p || st.size()!=0)
62
63}
64
65


2.二叉树前序非递归遍历：

 1template <class T>
 2void PreOrder(TreeNode<T> *root)const
 3{
 4    stack<TreeNode<T>*> st;
 5    TreeNode<T>* p=root;
 6
 7    while (!st.empty()||p!=NULL)
 8    {
 9        while(p)   //沿左子树到底，访问途中结点并压栈保存
10        {
11            cout<<"visit:"<<p->data<<endl;
12            st.push(p);
13            p=p->left;
14        }
15
16        p=st.top(); //将父结点出栈，对右子树访问
17        st.pop();
18        p=p->right;        
19
20    }
21
22
23}

3.二叉树中序非递归遍历：
 

 1void InOrder(TreeNode<T>*root)const
 2{
 3    stack<TreeNode<T>*> st;
 4    TreeNode<T>* p=root;
 5    while (!st.empty()||p!=NULL)
 6    {
 7        while(p)//沿左子树到底，将途中结点压栈保存，不访问
 8        {
 9            st.push(p);
10            p=p->left;
11        }
12        p=st.top();
13        cout<<"visit:"<<p->data<<endl; //此时访问，实现中序
14        st.pop();
15        p=p->right;
16
17    }
18
19}

posted on 2010-10-22 19:05 oliver 阅读(1556) 评论(1)  编辑 收藏 引用 所属分类: DataStructure

评论

# re: 二叉树前序，中序，后序遍历的非递归实现（c++版） 2012-11-22 23:11 missgya

看了这么多，发现阁下的后序遍历写得最漂亮。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年4月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

个人专栏

技术网站

搜索

最新评论

阅读排行榜

评论排行榜