Adding binary tree algorithms

1 files changed, 110 insertions, 9 deletions

diff --git a/C++/BinaryTree.cpp b/C++/BinaryTree.cpp
index 68ebefa..b752365 100644
--- a/C++/BinaryTree.cpp
+++ b/C++/BinaryTree.cpp
@@ -20,7 +20,14 @@ void addElement(treeNode*&, tree_t&);
 void deallocateTree(treeNode*&);
 void printTree(treeNode*);
 void deleteFromRoot(treeNode*&, tree_t&);
+void deleteRoot(treeNode*&);
+void deleteLeftMost(treeNode*&, tree_t&);
 int treeHeight(treeNode*);
+int max(int&, int&);
+bool isBalanced(treeNode*);
+int abs(int&);
+void rotateRight(treeNode*&);
+void rotateLeft(treeNode*&);
 
 int main() {
 	treeNode* firstTree = NULL;
@@ -35,9 +42,38 @@ int main() {
 		addElement(firstTree, newElement);
 	}
 
-	cout << "printing tree: " << endl;
+	cout << endl << "printing tree: " << endl;
+
+	printTree(firstTree);
+
+	cout << endl << "head root node: " << firstTree->element << endl;
+	//cout << endl << "which item would you want to delete?" << endl;
+	//cin >> newElement;
+
+	//deleteFromRoot(firstTree, newElement);
+
+	//cout << endl << "printing tree again:" << endl;
+
+	//printTree(firstTree);
+
+	cout << endl << "Height of tree: " << treeHeight(firstTree) << endl;
+
+	cout << endl << "Balanced Tree: " << isBalanced(firstTree) << endl;
+
+	cout << endl << "Rotate right: " << endl;
+
+	rotateLeft(firstTree);
+
+	printTree(firstTree);
+
+	cout << endl << "Height of tree: " << treeHeight(firstTree) << endl;
+	cout << endl << "Balanced Tree: " << isBalanced(firstTree) << endl;	
+
+	cout << endl << "new head root node: " << firstTree->element << endl;
 	
 	deallocateTree(firstTree);
+
+	cout << endl << "successfully deallocated tree..." << endl;
 	return 0;
 }
 
@@ -63,25 +99,90 @@ void deallocateTree(treeNode* &hdTree) {
 void printTree(treeNode* hdTree) {
 	if(hdTree != NULL) {
 		printTree(hdTree->left);
-		cout << hdTree->element;
+		cout << hdTree->element << endl;
 		printTree(hdTree->right);
 	}
 }
 
 void deleteFromRoot(treeNode* &hdTree, tree_t &el) {
-	if(el < hdTree->element) {
-		deleteFromRoot(hdTree->left, el);
-	} else if(el > hdTree->element) {
-		deleteFromRoot(hdTree->right, el);
+	if(hdTree != NULL) {
+		if(hdTree->element == el) {
+			deleteRoot(hdTree);
+		} else if(hdTree->element > el) {
+			deleteFromRoot(hdTree->left, el);
+		} else {
+			deleteFromRoot(hdTree->right, el);
+		}
+	}
+}
+
+void deleteRoot(treeNode* &hdTree) {
+	treeNode* tmpPointer;
+	tree_t leftMost;
+	if(hdTree->right == NULL) {
+		tmpPointer = hdTree->left;
+		delete hdTree;
+		hdTree = tmpPointer;
+	} else {
+		deleteLeftMost(hdTree, leftMost);
+		hdTree->element = leftMost;
+	}
+}
+
+void deleteLeftMost(treeNode* &hdTree, tree_t &leftMost) {
+	if(hdTree->left == NULL) {
+		leftMost = hdTree->element;
+		deleteRoot(hdTree);
 	} else {
-		// Do something
+		deleteLeftMost(hdTree->left, leftMost);
 	}
 }
 
 int treeHeight(treeNode* hdTree) {
-	// Do something
+	if(hdTree == NULL) {
+		return 0;
+	}
+	return 1 + max(treeHeight(hdTree->left), treeHeight(hdTree->right));
 }
 
-bool elementInTree(treeNode* hdTree, tree_t &el) {
+int max(int &a, int &b) {
+	return (a >= b) ? a: b;
+}
+
+bool isBalanced(treeNode* hdTree) {
+	int lh, rh;
+	if(hdTree == NULL) {
+		return true;
+	}
+
+	lh = treeHeight(hdTree->left);
+	rh = treeHeight(hdTree->right);
+
+	int diff = lh - rh;
+
+	if(abs(diff) <= 1 && isBalanced(hdTree->left) && isBalanced(hdTree->right)) {
+		return true;
+	}
+	return false;
+}
+
+int abs(int &a) {
+	if(a > 0) {
+		return a;
+	}
+	return (-1)*a;
+}
+
+void rotateRight(treeNode* &hdTree) {
+	treeNode* tmpTree = hdTree;
+	hdTree = hdTree->left;
+	tmpTree->left = hdTree->right;
+	hdTree->right = tmpTree;
+}
 
+void rotateLeft(treeNode* &hdTree) {
+	treeNode* tmpTree = hdTree;
+	hdTree = hdTree->right;
+	tmpTree->right = hdTree->left;
+	hdTree->left = tmpTree;
 }