從上向下遍歷二叉樹
樹的層次遍歷
圖的廣度遍歷
首先是要定義二叉樹節點的結構體
建立二叉樹
層次遍歷，需要一個隊列輔助
建立一棵二叉樹
遞歸的前序、中序、后序遍歷
層次遍歷
http://www.shnenglu.com/jake1036/archive/2011/05/17/146537.html
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 struct node
6 {
7 int data;
8 node* left;
9 node* right;
10 };
11
12 void addNode(int item, node*& root)
13 {
14 if (root == 0)
15 {
16 root = new node;
17 root->data = item;
18 root->left = 0;
19 root->right = 0;
20 return;
21 }
22 else
23 {
24 node* p = root, * p2;
25 while (p != 0)
26 {
27 p2 = p;
28 if (item < p->data)
29 {
30 p = p->left;
31 }
32 else
33 {
34 p = p->right;
35 }
36 }
37 node* q = new node;
38 q->data = item;
39 q->left = 0;
40 q->right = 0;
41 if (p2->data > q->data)
42 {
43 p2->left = q;
44 }
45 else
46 {
47 p2->right = q;
48 }
49 }
50 }
51
52 void preOrder(node* root)
53 {
54 if (root != 0)
55 {
56 cout << root->data << ' ';
57 preOrder(root->left);
58 preOrder(root->right);
59 }
60 }
61
62 void inOrder(node* root)
63 {
64 if (root != 0)
65 {
66 inOrder(root->left);
67 cout << root->data << ' ';
68 inOrder(root->right);
69 }
70 }
71
72 void postOrder(node* root)
73 {
74 if (root != 0)
75 {
76 postOrder(root->left);
77 postOrder(root->right);
78 cout << root->data << ' ';
79 }
80 }
81
82 void levelOrder(node* root)
83 {
84 if (root != 0)
85 {
86 queue<node*> q;
87 node* t;
88 q.push(root);
89 while (!q.empty())
90 {
91 t = q.front();
92 q.pop();
93 cout << t-> data << ' ';
94 if (t->left != 0)
95 {
96 q.push(t->left);
97 }
98 if (t->right != 0)
99 {
100 q.push(t->right);
101 }
102 }
103 }
104 }
105
106 int main()
107 {
108 int a[] = {5, 2, 7, 4, 9, 8, 3, 6, 1};
109 node* root = 0;
110 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
111 {
112 // cout << i << endl;
113 addNode(a[i], root);
114 }
115 preOrder(root);
116 cout << endl;
117 inOrder(root);
118 cout << endl;
119 postOrder(root);
120 cout << endl;
121 levelOrder(root);
122 cout << endl;
123 return 0;
124 }
posted on 2011-07-22 15:44
unixfy 閱讀(165)
評論(0) 編輯 收藏 引用