-
Notifications
You must be signed in to change notification settings - Fork 0
/
4_4.cpp
133 lines (114 loc) · 2.98 KB
/
4_4.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//
// 4_4.cpp
//
//
// Created by Pengyan Qin on 6/26/15.
//
//
#include <iostream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
struct node{
int data;
node* left;
node* right;
node() {}
node(int data_in):data(data_in), left(nullptr), right(nullptr){}
};
void insert(node* &root, int dat){
if(root == nullptr){
node *n = new node(dat);
root = n;
return;
}
if(dat < root->data){
insert(root->left, dat);
}
else{
insert(root->right, dat);
}
}
// BFT traversal
// use two queue to alternate store different depth of nodes
vector<list<node*> > ll_depty(node* root){
queue<node*> q[2]; // used to store nodes of different depth
int cur = 0;
int prev = 1;
q[cur].push(root);
list<node*> l;
l.push_back(root);
vector<list<node*> > res;
res.push_back(l);
while(!q[cur].empty()){
cur = !cur;
prev = !prev;
l.clear();
while(!q[prev].empty()){
node *tmp = q[prev].front();
q[prev].pop();
if(tmp->left){
l.push_back(tmp->left);
q[cur].push(tmp->left);
}
if(tmp->right){
l.push_back(tmp->right);
q[cur].push(tmp->right);
}
}
res.push_back(l);
}
return res;
}
//don't use queue, since list can use iterator
//take advantage of vector can access by []
vector<list<node*> > ll_depth(node *root){
vector<list<node*> > res;
list<node*> li;
li.push_back(root);
res.push_back(li);
int depth = 0;
while(!res[depth].empty()){
list<node*> l;
for(list<node*>::iterator it = res[depth].begin(); it != res[depth].end(); ++it){
node* n = *it;
if(n->left)
l.push_back(n->left);
if(n->right)
l.push_back(n->right);
}
res.push_back(l);
++depth;
}
return res;
}
/*
the first method use two queues to access different level of nodes
use FIFO property of queue to traverasal nodes(left->right) in each depth
the second method take advantage of vector[] to access different leverl of nodes
use list:iterator to traversal nodes (left->right) in each depth
*/
int main(){
node *root = new node(8);
int a[8] = {11, 3, 18, 9, 6, 13, 4, 1};
int num = 8;
for(int i = 0; i < num; ++i){
insert(root, a[i]);
}
vector<list<node*> > res = ll_depty(root);
vector<list<node*> > res1 = ll_depth(root);
for(int i = 0; i < res.size(); ++i){
for(list<node*>::iterator it = res[i].begin(); it != res[i].end(); ++it){
cout << (*it)->data << " ";
}
cout << endl;
}
for(int i = 0; i < res1.size(); ++i){
for(list<node*>::iterator it = res1[i].begin(); it != res1[i].end(); ++it){
cout << (*it)->data << " ";
}
cout << endl;
}
return 0;
}