forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinaryTree.java
More file actions
192 lines (171 loc) · 4.36 KB
/
Copy pathBinaryTree.java
File metadata and controls
192 lines (171 loc) · 4.36 KB
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
//A binary tree is a data structure in which an element has two successors(children)
//The left child is usually smaller than the parent, and the right child is usually bigger
class Node{
public int data;
public Node left;
public Node right;
public Node parent;
public Node(int value){
data = value;
left = null;
right = null;
parent = null;
}
}
class Tree{
private Node root;
public Tree(){
root = null;
}
//Returns the node if it finds it, otherwise returns the parent
public Node find(int key){
Node current = root;
Node last = root;
while(current != null){
last = current;
if(key < current.data)
current = current.left;
else if(key > current.data)
current = current.right;
//If you find the value return it
else
return current;
}
return last;
}
//Inserts the given value
public void put(int value){
Node newNode = new Node(value);
if(root == null)
root = newNode;
else{
//This will return the soon to be parent of the value you're inserting
Node parent = find(value);
//This if/else assigns the new node to be either the left or right child of the parent
if(value < parent.data){
parent.left = newNode;
parent.left.parent = parent;
return;
}
else{
parent.right = newNode;
parent.right.parent = parent;
return;
}
}
}
//Deletes the given value
public boolean remove(int value){
//temp is the node to be deleted
Node temp = find(value);
//If the value doesn't exist
if(temp.data != value)
return false;
//No children
if(temp.right == null && temp.left == null){
if(temp == root)
root = null;
//This if/else assigns the new node to be either the left or right child of the parent
else if(temp.parent.data < temp.data)
temp.parent.right = null;
else
temp.parent.left = null;
return true;
}
//Two children
else if(temp.left != null && temp.right != null){
Node succesor = findSuccesor(temp);
//The left tree of temp is made the left tree of the successor
succesor.left = temp.left;
succesor.left.parent = succesor;
//If the successor has a right child, the child's grandparent is it's new parent
if(succesor.right != null && succesor.parent != temp){
succesor.right.parent = succesor.parent;
succesor.parent.left = succesor.right;
succesor.right = temp.right;
succesor.right.parent = succesor;
}
if(temp == root){
succesor.parent = null;
root = succesor;
return true;
}
//If you're not deleting the root
else{
succesor.parent = temp.parent;
//This if/else assigns the new node to be either the left or right child of the parent
if(temp.parent.data < temp.data)
temp.parent.right = succesor;
else
temp.parent.left = succesor;
return true;
}
}
//One child
else{
//If it has a right child
if(temp.right != null){
if(temp == root){
root = temp.right; return true;}
temp.right.parent = temp.parent;
//Assigns temp to left or right child
if(temp.data < temp.parent.data)
temp.parent.left = temp.right;
else
temp.parent.right = temp.right;
return true;
}
//If it has a left child
else{
if(temp == root){
root = temp.left; return true;}
temp.left.parent = temp.parent;
//Assigns temp to left or right side
if(temp.data < temp.parent.data)
temp.parent.left = temp.left;
else
temp.parent.right = temp.left;
return true;
}
}
}
//Move right once and go left down the tree as far as you can
public Node findSuccesor(Node n){
if(n.right == null)
return n;
Node current = n.right;
Node parent = n.right;
while(current != null){
parent = current;
current = current.left;
}
return parent;
}
public Node getRoot(){
return root;
}
//Prints leftChild - root - rightChild
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.left);
System.out.print(localRoot.data + " ");
inOrder(localRoot.right);
}
}
//Prints root - leftChild - rightChild
public void preOrder(Node localRoot){
if(localRoot != null){
System.out.print(localRoot.data + " ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}
//Prints rightChild - leftChild - root
public void postOrder(Node localRoot){
if(localRoot != null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data + " ");
}
}
}