二叉樹的遍歷
·先根 中根 后根
·遞歸 非遞歸
·層序
1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 using namespace std;
5
6 struct node
7 {
8 int item;
9 node* left;
10 node* right;
11 };
12
13 void visit(node* p)
14 {
15 if (p != 0)
16 {
17 cout << p->item << ' ';
18 }
19 }
20
21 node* insert(node*& p, int i)
22 {
23 if (p == 0)
24 {
25 p = new node;
26 p->item = i;
27 p->left = 0;
28 p->right = 0;
29 }
30 else
31 {
32 if (i < p->item)
33 {
34 insert(p->left, i);
35 }
36 else
37 {
38 insert(p->right, i);
39 }
40 }
41 return p;
42 }
43
44 void preOrder(node* root)
45 {
46 if (root != 0)
47 {
48 visit(root);
49 preOrder(root->left);
50 preOrder(root->right);
51 }
52 }
53
54 void preOrderNonrecursive(node* root)
55 {
56 //
57 }
58
59 void inOrder(node* root)
60 {
61 if (root != 0)
62 {
63 inOrder(root->left);
64 visit(root);
65 inOrder(root->right);
66 }
67 }
68
69 void inOrderNonrecursive(node* root)
70 {
71 //
72 }
73
74 void postOrder(node* root)
75 {
76 if (root != 0)
77 {
78 postOrder(root->left);
79 postOrder(root->right);
80 visit(root);
81 }
82 }
83
84 void postOrderNonrecursive(node* root)
85 {
86 //
87 }
88
89 void levelOrder(node* root)
90 {
91 if (root != 0)
92 {
93 queue<node*> q;
94 node* t;
95 q.push(root);
96 while (!q.empty())
97 {
98 t = q.front();
99 cout << t->item << ' ';
100 q.pop();
101 if (t->left != 0)
102 {
103 q.push(t->left);
104 }
105 if (t->right != 0)
106 {
107 q.push(t->right);
108 }
109 }
110 }
111 }
112
113 int main()
114 {
115 int a[] = {3, 4, 2, 1, 5, 6};
116 node* bt = 0;
117 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
118 {
119 cout << i << endl;
120 insert(bt, a[i]);
121 }
122 preOrder(bt);
123 cout << endl;
124 inOrder(bt);
125 cout << endl;
126 postOrder(bt);
127 cout << endl;
128 levelOrder(bt);
129 cout << endl;
130 return 0;
131 }
posted on 2011-07-27 10:59
unixfy 閱讀(128)
評論(0) 編輯 收藏 引用