forked from uva-cs/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinarySearchTree.cpp.html
145 lines (127 loc) · 17.2 KB
/
BinarySearchTree.cpp.html
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="GNU source-highlight
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite">
<title>BinarySearchTree.cpp</title>
</head>
<body style="background-color:white">
<pre><b><span style="color:#000080">#include</span></b> <span style="color:#FF0000">"BinarySearchTree.h"</span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><string></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000"><iostream></span>
<b><span style="color:#000080">#include</span></b> <span style="color:#FF0000">"BinaryNode.h"</span>
<b><span style="color:#0000FF">using</span></b> <b><span style="color:#0000FF">namespace</span></b> std<span style="color:#990000">;</span>
BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">BinarySearchTree</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
root <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
BinarySearchTree<span style="color:#990000">::~</span><b><span style="color:#000000">BinarySearchTree</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">delete</span></b> root<span style="color:#990000">;</span>
root <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// insert finds a position for x in the tree and places it there.</span></i>
<span style="color:#009900">void</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">insert</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> x<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// YOUR IMPLEMENTATION GOES HERE</span></i>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// remove finds x's position in the tree and removes it.</span></i>
<span style="color:#009900">void</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> x<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
root <span style="color:#990000">=</span> <b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span>root<span style="color:#990000">,</span> x<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// private helper for remove to allow recursion over different nodes. returns</span></i>
<i><span style="color:#9A1900">// a BinaryNode* that is assigned to the original node.</span></i>
BinaryNode<span style="color:#990000">*</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span>BinaryNode<span style="color:#990000">*&</span> n<span style="color:#990000">,</span> <b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> x<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>n <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">return</span></b> NULL<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// first look for x</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>x <span style="color:#990000">==</span> n<span style="color:#990000">-></span>value<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// found</span></i>
<i><span style="color:#9A1900">// no children</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>n<span style="color:#990000">-></span>left <span style="color:#990000">==</span> NULL <span style="color:#990000">&&</span> n<span style="color:#990000">-></span>right <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">delete</span></b> n<span style="color:#990000">;</span>
n <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<b><span style="color:#0000FF">return</span></b> NULL<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// single child</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>n<span style="color:#990000">-></span>left <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
BinaryNode<span style="color:#990000">*</span> temp <span style="color:#990000">=</span> n<span style="color:#990000">-></span>right<span style="color:#990000">;</span>
n<span style="color:#990000">-></span>right <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<b><span style="color:#0000FF">delete</span></b> n<span style="color:#990000">;</span>
n <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<b><span style="color:#0000FF">return</span></b> temp<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>n<span style="color:#990000">-></span>right <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
BinaryNode<span style="color:#990000">*</span> temp <span style="color:#990000">=</span> n<span style="color:#990000">-></span>left<span style="color:#990000">;</span>
n<span style="color:#990000">-></span>left <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<b><span style="color:#0000FF">delete</span></b> n<span style="color:#990000">;</span>
n <span style="color:#990000">=</span> NULL<span style="color:#990000">;</span>
<b><span style="color:#0000FF">return</span></b> temp<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// two children</span></i>
<span style="color:#008080">string</span> sr <span style="color:#990000">=</span> <b><span style="color:#000000">min</span></b><span style="color:#990000">(</span>n<span style="color:#990000">-></span>right<span style="color:#990000">);</span>
n<span style="color:#990000">-></span>value <span style="color:#990000">=</span> sr<span style="color:#990000">;</span>
n<span style="color:#990000">-></span>right <span style="color:#990000">=</span> <b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span>n<span style="color:#990000">-></span>right<span style="color:#990000">,</span> sr<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span> <b><span style="color:#0000FF">else</span></b> <b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>x <span style="color:#990000"><</span> n<span style="color:#990000">-></span>value<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
n<span style="color:#990000">-></span>left <span style="color:#990000">=</span> <b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span>n<span style="color:#990000">-></span>left<span style="color:#990000">,</span> x<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span> <b><span style="color:#0000FF">else</span></b> <span style="color:#FF0000">{</span>
n<span style="color:#990000">-></span>right <span style="color:#990000">=</span> <b><span style="color:#000000">remove</span></b><span style="color:#990000">(</span>n<span style="color:#990000">-></span>right<span style="color:#990000">,</span> x<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">return</span></b> n<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// pathTo finds x in the tree and returns a string representing the path it</span></i>
<i><span style="color:#9A1900">// took to get there.</span></i>
<span style="color:#008080">string</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">pathTo</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> x<span style="color:#990000">)</span> <b><span style="color:#0000FF">const</span></b> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// YOUR IMPLEMENTATION GOES HERE</span></i>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// find determines whether or not x exists in the tree.</span></i>
<span style="color:#009900">bool</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">find</span></b><span style="color:#990000">(</span><b><span style="color:#0000FF">const</span></b> string<span style="color:#990000">&</span> x<span style="color:#990000">)</span> <b><span style="color:#0000FF">const</span></b> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// YOUR IMPLEMENTATION GOES HERE</span></i>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// numNodes returns the total number of nodes in the tree.</span></i>
<span style="color:#009900">int</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">numNodes</span></b><span style="color:#990000">()</span> <b><span style="color:#0000FF">const</span></b> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// YOUR IMPLEMENTATION GOES HERE</span></i>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// min finds the string with the smallest value in a subtree.</span></i>
<span style="color:#008080">string</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">min</span></b><span style="color:#990000">(</span>BinaryNode<span style="color:#990000">*</span> node<span style="color:#990000">)</span> <b><span style="color:#0000FF">const</span></b> <span style="color:#FF0000">{</span>
<i><span style="color:#9A1900">// go to bottom-left node</span></i>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>node<span style="color:#990000">-></span>left <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">return</span></b> node<span style="color:#990000">-></span>value<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#0000FF">return</span></b> <b><span style="color:#000000">min</span></b><span style="color:#990000">(</span>node<span style="color:#990000">-></span>left<span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// Helper function to print branches of the binary tree</span></i>
<span style="color:#009900">void</span> <b><span style="color:#000000">showTrunks</span></b><span style="color:#990000">(</span>Trunk<span style="color:#990000">*</span> p<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>p <span style="color:#990000">==</span> nullptr<span style="color:#990000">)</span> <b><span style="color:#0000FF">return</span></b><span style="color:#990000">;</span>
<b><span style="color:#000000">showTrunks</span></b><span style="color:#990000">(</span>p<span style="color:#990000">-></span>prev<span style="color:#990000">);</span>
cout <span style="color:#990000"><<</span> p<span style="color:#990000">-></span>str<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<span style="color:#009900">void</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">printTree</span></b><span style="color:#990000">()</span> <span style="color:#FF0000">{</span>
<b><span style="color:#000000">printTree</span></b><span style="color:#990000">(</span>root<span style="color:#990000">,</span> NULL<span style="color:#990000">,</span> <b><span style="color:#0000FF">false</span></b><span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
<i><span style="color:#9A1900">// Recursive function to print binary tree</span></i>
<i><span style="color:#9A1900">// It uses inorder traversal</span></i>
<span style="color:#009900">void</span> BinarySearchTree<span style="color:#990000">::</span><b><span style="color:#000000">printTree</span></b><span style="color:#990000">(</span>BinaryNode<span style="color:#990000">*</span> root<span style="color:#990000">,</span> Trunk<span style="color:#990000">*</span> prev<span style="color:#990000">,</span> <span style="color:#009900">bool</span> isRight<span style="color:#990000">)</span> <span style="color:#FF0000">{</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>root <span style="color:#990000">==</span> NULL<span style="color:#990000">)</span> <b><span style="color:#0000FF">return</span></b><span style="color:#990000">;</span>
<span style="color:#008080">string</span> prev_str <span style="color:#990000">=</span> <span style="color:#FF0000">" "</span><span style="color:#990000">;</span>
Trunk<span style="color:#990000">*</span> trunk <span style="color:#990000">=</span> <b><span style="color:#0000FF">new</span></b> <b><span style="color:#000000">Trunk</span></b><span style="color:#990000">(</span>prev<span style="color:#990000">,</span> prev_str<span style="color:#990000">);</span>
<b><span style="color:#000000">printTree</span></b><span style="color:#990000">(</span>root<span style="color:#990000">-></span>right<span style="color:#990000">,</span> trunk<span style="color:#990000">,</span> <b><span style="color:#0000FF">true</span></b><span style="color:#990000">);</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(!</span>prev<span style="color:#990000">)</span>
trunk<span style="color:#990000">-></span>str <span style="color:#990000">=</span> <span style="color:#FF0000">"---"</span><span style="color:#990000">;</span>
<b><span style="color:#0000FF">else</span></b> <b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>isRight<span style="color:#990000">)</span> <span style="color:#FF0000">{</span> <i><span style="color:#9A1900">// github user @willzhang05 pointed out that I forgot to change this from isLeft to isRight on my first commit</span></i>
trunk<span style="color:#990000">-></span>str <span style="color:#990000">=</span> <span style="color:#FF0000">".---"</span><span style="color:#990000">;</span>
prev_str <span style="color:#990000">=</span> <span style="color:#FF0000">" |"</span><span style="color:#990000">;</span>
<span style="color:#FF0000">}</span> <b><span style="color:#0000FF">else</span></b> <span style="color:#FF0000">{</span>
trunk<span style="color:#990000">-></span>str <span style="color:#990000">=</span> <span style="color:#FF0000">"`---"</span><span style="color:#990000">;</span>
prev<span style="color:#990000">-></span>str <span style="color:#990000">=</span> prev_str<span style="color:#990000">;</span>
<span style="color:#FF0000">}</span>
<b><span style="color:#000000">showTrunks</span></b><span style="color:#990000">(</span>trunk<span style="color:#990000">);</span>
cout <span style="color:#990000"><<</span> root<span style="color:#990000">-></span>value <span style="color:#990000"><<</span> endl<span style="color:#990000">;</span>
<b><span style="color:#0000FF">if</span></b> <span style="color:#990000">(</span>prev<span style="color:#990000">)</span> prev<span style="color:#990000">-></span>str <span style="color:#990000">=</span> prev_str<span style="color:#990000">;</span>
trunk<span style="color:#990000">-></span>str <span style="color:#990000">=</span> <span style="color:#FF0000">" |"</span><span style="color:#990000">;</span>
<b><span style="color:#000000">printTree</span></b><span style="color:#990000">(</span>root<span style="color:#990000">-></span>left<span style="color:#990000">,</span> trunk<span style="color:#990000">,</span> <b><span style="color:#0000FF">false</span></b><span style="color:#990000">);</span>
<span style="color:#FF0000">}</span>
</pre>
</body>
</html>