using System;
using System.Collections.Generic;
public class Node {
public Node left = null;
public Node right = null;
public int value = 0;
public Node(int value) {
this.value = value;
}
}
class BinarySearchTree {
public Node root = null;
static void Main() {
Console.WriteLine("Hello World!");
BinarySearchTree bst = new BinarySearchTree();
Console.WriteLine("bst = " + bst.ToString());
bst.Insert(60);
bst.Insert(30);
bst.Insert(72);
bst.Insert(14);
bst.Insert(1);
bst.Insert(51);
bst.Insert(38);
bst.Insert(55);
bst.Insert(54);
bst.Insert(38);
bst.Insert(44);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(51);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(14);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(30);
Console.WriteLine("bst = " + bst.ToString());
bst.BreadthFirstSearch();
bst.BreadthFirstSearchRecursive();
}
public BinarySearchTree() {
}
public string ToString() {
string s = "{";
if (this.root != null) {
s += NodeToString(this.root);
}
s += "}";
return s;
}
public string NodeToString(Node n) {
string s = "" + n.value;
if (n.left != null || n.right != null) {
s += "(";
}
if (n.left != null) {
s += NodeToString(n.left);
}
if (n.left != null || n.right != null) {
s += ",";
}
if (n.right != null) {
s += NodeToString(n.right);
}
if (n.left != null || n.right != null) {
s += ")";
}
return s;
}
public void Insert(int value) {
Node item = new Node(value);
if (this.root == null) {
this.root = item;
} else {
InsertAsChild(this.root, item);
}
}
public void InsertAsChild(Node parent, Node child) {
if (child.value < parent.value) {
if (parent.left == null) {
parent.left = child;
} else {
InsertAsChild(parent.left, child);
}
} else if (child.value > parent.value) {
if (parent.right == null) {
parent.right = child;
} else {
InsertAsChild(parent.right, child);
}
}
}
public Node Lookup(int value) {
if (this.root != null) {
return LookupChild(this.root, value);
}
return null;
}
public Node LookupChild(Node parent, int value) {
if (parent == null || parent.value == value) {
return parent;
}
if (value < parent.value) {
return LookupChild(parent.left, value);
}
if (value > parent.value) {
return LookupChild(parent.right, value);
}
return null;
}
public void Remove(int value) {
if (this.root != null) {
Node current = this.root;
Node prev = null;
bool wasPrevLeft = false;
Node found = null;
while (current != null) {
if (found != null) {
if (current.left != null) {
if (wasPrevLeft) {
prev.left = current.left;
} else {
prev.right = current.left;
}
current.left.left = found.left;
current.left.right = found.right;
current.left = null;
return;
} else {
if (wasPrevLeft) {
prev.left = current;
} else {
prev.right = current;
}
current.left = found.left;
return;
}
} else if (value == current.value) {
found = current;
if (found.right == null) {
if (wasPrevLeft) {
prev.left = found.left;
} else {
prev.right = found.left;
}
return;
} else if (found.left == null) {
if (wasPrevLeft) {
prev.left = found.right;
} else {
prev.right = found.right;
}
return;
} else {
current = current.right;
}
} else if (value < current.value) {
prev = current;
wasPrevLeft = true;
current = current.left;
} else if (value > current.value) {
prev = current;
wasPrevLeft = false;
current = current.right;
}
}
}
}
public void RemoveChild(Node parent, int value) {
// if (parent.left != null) {
// if (parent.left.value == value) {
// this.root = null;
// } else {
// RemoveChild(this.root, value);
// }
// }
// if (parent.value == value) {
// }
// if (value < parent.value) {
// return LookupChild(parent.left, value);
// }
// if (value > parent.value) {
// return LookupChild(parent.right, value);
// }
}
public void BreadthFirstSearch(/*int value*/) {
Node current = this.root;
List<int> list = new List<int> ();
Queue<Node> queue = new Queue<Node> ();
queue.Enqueue(current);
while (queue.Count > 0) {
current = queue.Dequeue();
list.Add(current.value);
if (current.left != null) {
queue.Enqueue(current.left);
}
if (current.right != null) {
queue.Enqueue(current.right);
}
}
string s = "BFS: {";
int count = 0;
foreach (int v in list) {
if (count > 0) {
s += ", ";
}
s += "" + v;
count++;
}
s += "}";
Console.WriteLine(s);
}
public void BreadthFirstSearchRecursive(/*int value*/) {
Node current = this.root;
List<int> list = new List<int> ();
Queue<Node> queue = new Queue<Node> ();
queue.Enqueue(current);
list = BFSR(queue, list);
string s = "BFS: {";
int count = 0;
foreach (int v in list) {
if (count > 0) {
s += ", ";
}
s += "" + v;
count++;
}
s += "}";
Console.WriteLine(s);
}
public List<int> BFSR(Queue<Node> queue, List<int> list) {
if (queue.Count == 0) {
return list;
}
Node current = queue.Dequeue();
list.Add(current.value);
if (current.left != null) {
queue.Enqueue(current.left);
}
if (current.right != null) {
queue.Enqueue(current.right);
}
return BFSR(queue, list);
}
}
