Last active
June 25, 2016 08:45
-
-
Save Williammer/935d733256bec20421de to your computer and use it in GitHub Desktop.
Binary Search Tree Impl and Binary Search related algorithm.
PreOrder: Traverse from Root to left sub-tree, then right sub-tree.
InOrder: from smallest to largest item,which means it started from left-most leaf.
PostOrder: leafs->left subRoot-> rightLeafs-> right subRoot --> Root
??Order: Traverse from Root to each sub-root(left then right).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct Node{ | |
int data; | |
Node *left, *right; | |
}; | |
void preOrderPrint(Node *root) | |
{ | |
print(root->name); //record root | |
if (root->left != NULL) preOrderPrint(root->left); //traverse left if exists | |
if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists | |
} | |
void inOrderPrint(Node *root) | |
{ | |
if (root.left != NULL) inOrderPrint(root->left); //traverse left if exists | |
print(root->name); //record root | |
if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists | |
} | |
void postOrderPrint(Node *root) | |
{ | |
if (root->left != NULL) postOrderPrint(root->left); //traverse left if exists | |
if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists | |
print(root->name); //record root | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function Node(data, left, right) { | |
this.data = data; | |
this.left = left; | |
this.right = right; | |
this.show = show; | |
} | |
function show() { | |
return this.data; | |
} | |
function BST() { | |
this.root = null; | |
this.insert = insert; | |
this.inOrder = inOrder; | |
this.preOrder = preOrder; | |
this.postOrder = postOrder; | |
this.getmin = getmin; | |
this.getmax = getmax; | |
this.find = find; | |
this.remove = remove; | |
this.removeNode = removeNode; | |
this.getSmallest = getSmallest; | |
} | |
function insert(data) { | |
var n = new Node(data, null, null); | |
if (this.root == null) { | |
this.root = n; | |
} else { | |
var current = this.root; | |
var parent; | |
while (true) { | |
parent = current; | |
if (data < current.data) { | |
current = current.left; | |
if (current == null) { | |
parent.left = n; | |
break; | |
} | |
} else { | |
current = current.right; | |
if (current == null) { | |
parent.right = n; | |
break; | |
} | |
} | |
} | |
} | |
} | |
function inOrder(node) { | |
if (!(node == null)) { | |
inOrder(node.left); | |
putstr(node.show() + " "); | |
inOrder(node.right); | |
} | |
} | |
function preOrder(node) { | |
if (!(node == null)) { | |
putstr(node.show() + " "); | |
preOrder(node.left); | |
preOrder(node.right); | |
} | |
} | |
function postOrder(node) { | |
if (!(node == null)) { | |
postOrder(node.left); | |
postOrder(node.right); | |
putstr(node.show() + " "); | |
} | |
} | |
function getmin() { | |
var current = this.root; | |
print("debug: " + current.data); | |
while (!(current.left == null)) { | |
current = current.left; | |
} | |
return current.data; | |
} | |
function getmax() { | |
var current = this.root; | |
while (!(current.right == null)) { | |
current = current.right; | |
} | |
return current.data; | |
} | |
function find(data) { | |
var current = this.root; | |
while (current.data != data) { | |
if (data < current.data) { | |
current = current.left; | |
} else { | |
current = current.right; | |
} | |
if (current == null) { | |
return null; | |
} | |
} | |
return current; | |
} | |
function getSmallest(node) { | |
if (node.left == null) { | |
return node; | |
} else { | |
return getSmallest(node.left); | |
} | |
} | |
function remove(data) { | |
this.root = removeNode(this.root, data); | |
} | |
function removeNode(node, data) { | |
if (node == null) { | |
return null; | |
} | |
// Reusable find function for recursion | |
if (data == node.data) { | |
// node has no children | |
if (node.left == null && node.right == null) { | |
return null; | |
} | |
// node has no left child | |
if (node.left == null) { | |
return node.right; | |
} | |
// node has no right child | |
if (node.right == null) { | |
return node.left; | |
} | |
// node has two children | |
var tempNode = getSmallest(node.right); | |
node.data = tempNode.data; | |
node.right = removeNode(node.right, tempNode.data); | |
return node; | |
} else if (data < node.data) { | |
// to find and update in leftsubtree | |
node.left = removeNode(node.left, data); | |
return node; // root node | |
} else { | |
// to find and update in rightsubtree | |
node.right = removeNode(node.right, data); | |
return node; // root node | |
} | |
} | |
var nums = new BST(); | |
nums.insert(23); | |
nums.insert(45); | |
nums.insert(16); | |
nums.insert(37); | |
nums.insert(3); | |
nums.insert(99); | |
nums.insert(22); | |
/*print("Inorder traversal: "); | |
inOrder(nums.root); | |
print("\n"); | |
print("Preorder traversal: "); | |
preOrder(nums.root); | |
print("\n"); | |
print("Postorder traversal: "); | |
postOrder(nums.root); | |
print("\n"); | |
var min = nums.getmin(); | |
print("The minimum value of the BST is: " + min); | |
var max = nums.getmax(); | |
print("The maximum value of the BST is: " + max); | |
inOrder(nums.root); | |
print("\n"); | |
putstr("Enter a value to search for: "); | |
var value = parseInt(readline()); | |
var found = nums.find(value); | |
if (found != null) { | |
print("Found " + value + " in the BST."); | |
} | |
else { | |
print(value + " was not found in the BST."); | |
}*/ | |
inOrder(nums.root); | |
print("\n"); | |
var num = parseInt(readline()); | |
nums.remove(num); | |
inOrder(nums.root); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function Node(data, left, right) { | |
this.data = data; | |
this.left = left; | |
this.right = right; | |
this.show = show; | |
} | |
function show() { | |
return this.data; | |
} | |
function BST() { | |
this.root = null; | |
this.insert = insert; | |
this.inOrder = inOrder; | |
this.preOrder = preOrder; | |
this.postOrder = postOrder; | |
this.getmin = getmin; | |
this.getmax = getmax; | |
this.find = find; | |
this.remove = remove; | |
this.removeNode = removeNode; | |
this.getSmallest = getSmallest; | |
// exercises: | |
this.getNodeNumber = getNodeNumber; | |
this.getEdgeNumber = getEdgeNumber; | |
} | |
function insert(data) { | |
var n = new Node(data, null, null); | |
if (this.root == null) { | |
this.root = n; | |
} else { | |
var current = this.root; | |
var parent; | |
while (true) { | |
parent = current; | |
if (data < current.data) { | |
current = current.left; | |
if (current == null) { | |
parent.left = n; | |
break; | |
} | |
} else { | |
current = current.right; | |
if (current == null) { | |
parent.right = n; | |
break; | |
} | |
} | |
} | |
} | |
} | |
function inOrder(node) { | |
if (!(node == null)) { | |
inOrder(node.left); | |
putstr(node.show() + " "); | |
inOrder(node.right); | |
} | |
} | |
function preOrder(node) { | |
if (!(node == null)) { | |
putstr(node.show() + " "); | |
preOrder(node.left); | |
preOrder(node.right); | |
} | |
} | |
function postOrder(node) { | |
if (!(node == null)) { | |
postOrder(node.left); | |
postOrder(node.right); | |
putstr(node.show() + " "); | |
} | |
} | |
function getmin() { | |
var current = this.root; | |
print("debug: " + current.data); | |
while (!(current.left == null)) { | |
current = current.left; | |
} | |
return current.data; | |
} | |
function getmax() { | |
var current = this.root; | |
while (!(current.right == null)) { | |
current = current.right; | |
} | |
return current.data; | |
} | |
function find(data) { | |
var current = this.root; | |
while (current.data != data) { | |
if (data < current.data) { | |
current = current.left; | |
} else { | |
current = current.right; | |
} | |
if (current == null) { | |
return null; | |
} | |
} | |
return current; | |
} | |
function getSmallest(node) { | |
if (node.left == null) { | |
return node; | |
} else { | |
return getSmallest(node.left); | |
} | |
} | |
function remove(data) { | |
this.root = removeNode(this.root, data); | |
} | |
function removeNode(node, data) { | |
if (node == null) { | |
return null; | |
} | |
// Reusable find function for recursion | |
if (data == node.data) { | |
// node has no children | |
if (node.left == null && node.right == null) { | |
return null; | |
} | |
// node has no left child | |
if (node.left == null) { | |
return node.right; | |
} | |
// node has no right child | |
if (node.right == null) { | |
return node.left; | |
} | |
// node has two children | |
var tempNode = getSmallest(node.right); | |
node.data = tempNode.data; | |
node.right = removeNode(node.right, tempNode.data); | |
return node; | |
} else if (data < node.data) { | |
// to find and update in leftsubtree | |
node.left = removeNode(node.left, data); | |
return node; // root node | |
} else { | |
// to find and update in rightsubtree | |
node.right = removeNode(node.right, data); | |
return node; // root node | |
} | |
} | |
function getNodeNumber() { | |
var count = 0, | |
node = this.root; | |
(function addCount(node) { | |
if (node != null) { | |
count++; | |
addCount(node.left); | |
addCount(node.right); | |
} | |
})(node); | |
return count; | |
} | |
function getEdgeNumber() { | |
var nodeCount = this.getNodeNumber(); | |
return nodeCount > 0 ? nodeCount - 1 : 0; | |
} | |
// test------------------------------------------------------------ | |
var nums = new BST(); | |
nums.insert(23); | |
nums.insert(45); | |
nums.insert(16); | |
nums.insert(37); | |
nums.insert(3); | |
nums.insert(99); | |
nums.insert(22); | |
nums.getNodeNumber(); // 7 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment