亚洲在线不卡,国产亚洲一区二区三区在线观看,欧美日韩国产一区

二叉樹前序，中序，后序遍歷的非遞歸實現（c++版）

1. 二叉樹后序非遞歸遍歷：

#include <stack>
2

#include <iostream>
3

using namespace std;
4

template <class T>
6

class TreeNode
7

{
8

public:
9

T data;
10

TreeNode<T> *left; //left child
11

TreeNode<T> *right; //right child
12

TreeNode():left(NULL),right(NULL)
14

{
15

}
16

TreeNode(const T& t):data(t),left(NULL), right(NULL)
18

{
19

}
20

TreeNode(const T& t, TreeNode<T*> left, TreeNode<T*> right):data(t),left(left), right(right)
22

{
23

}
24

};
25

/**purpose: 對二叉樹進行后序遍歷（非遞歸算法）
27

TreeNode<T> *root :the root of the binary tree
28

*/
29

template <class T>
30

void postOrder(TreeNode<T> *root)
31

{
32

stack<TreeNode<T>*> st;
33

TreeNode<T> *p = root;
34

TreeNode<T> *pre = NULL;//pre表示最近一次訪問的結點
35

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

}
56

else
57

{
58

p = p->right;
59

}
61

}//end of while(p || st.size()!=0)
62

}
64

2.二叉樹前序非遞歸遍歷：

template <class T>
2

void PreOrder(TreeNode<T> *root)const
3

{
4

stack<TreeNode<T>*> st;
5

TreeNode<T>* p=root;
6

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

p=st.top(); //將父結點出棧，對右子樹訪問
17

st.pop();
18

p=p->right;
19

}
21

}

3.二叉樹中序非遞歸遍歷：

void 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

}
18

}

posted on 2010-10-22 19:05 oliver 閱讀(1625) 評論(1) 編輯收藏引用所屬分類: DataStructure

# re: 二叉樹前序，中序，后序遍歷的非遞歸實現（c++版） 2012-11-22 23:11 missgya

二叉樹前序，中序，后序遍歷的非遞歸實現（c++版）

評論

導航

統計

常用鏈接

留言簿

隨筆檔案

文章分類

文章檔案

個人專欄

技術網站

搜索

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理