-
Notifications
You must be signed in to change notification settings - Fork 0
/
4_0.cpp
117 lines (101 loc) · 1.97 KB
/
4_0.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
//
// 4_0.cpp
//
//
// Created by Pengyan Qin on 6/25/15.
//
//
#include <iostream>
#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){}
};
// recursive version
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);
}
}
// DFS_inorder, recursive version
void InOrerPrint(node* root){
if(root == nullptr){
return;
}
InOrerPrint(root->left);
cout << root->data << " ";
InOrerPrint(root->right);
}
//BFS, use queue
void BFS(node* root){
if(root == nullptr)
return;
queue<node*> q;
q.push(root);
while(!q.empty()){
node *tmp = q.front();
q.pop();
cout << tmp->data << " ";
if(tmp->left){
q.push(tmp->left);
}
if(tmp->right){
q.push(tmp->right);
}
}
}
// BFS, print out null
void BFS_null(node* root){
if(root == nullptr){
cout << "null";
return;
}
queue<node*> q;
q.push(root);
cout << root->data << " ";
while(!q.empty()){
node *tmp = q.front();
q.pop();
if(tmp->left){
q.push(tmp->left);
cout << tmp->left->data << " ";
}
else{
cout << "null ";
}
if(tmp->right){
q.push(tmp->right);
cout << tmp->right->data << " ";
}
else{
cout << "null ";
}
}
}
int main(){
node *root = new node(8);
int a[5] = {3, 9, 13, 4, 1};
int num = 5;
for(int i = 0; i < num; ++i){
insert(root, a[i]);
}
InOrerPrint(root);
cout << endl;
BFS(root);
cout << endl;
BFS_null(root);
cout << endl;
delete root;
}