From 685f772c4b0376656c8d95fe8725de9adea3890f Mon Sep 17 00:00:00 2001
From: zedarider <ymherklotz@gmail.com>
Date: Mon, 14 Mar 2016 22:09:03 +0000
Subject: Improving binary trees

---
 C++/BinaryTree.cpp | 92 +++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 70 insertions(+), 22 deletions(-)

(limited to 'C++/BinaryTree.cpp')

diff --git a/C++/BinaryTree.cpp b/C++/BinaryTree.cpp
index b752365..216fc5d 100644
--- a/C++/BinaryTree.cpp
+++ b/C++/BinaryTree.cpp
@@ -3,6 +3,7 @@
 using namespace std;
 
 typedef int tree_t;
+typedef int link_t;
 
 struct treeNode {
 	tree_t element;
@@ -16,6 +17,16 @@ struct treeNode {
 	}
 };
 
+struct linkNode {
+	link_t element;
+	linkNode* next;
+
+	linkNode(link_t el) {
+		element = el;
+		next = NULL;
+	}
+};
+
 void addElement(treeNode*&, tree_t&);
 void deallocateTree(treeNode*&);
 void printTree(treeNode*);
@@ -28,9 +39,14 @@ bool isBalanced(treeNode*);
 int abs(int&);
 void rotateRight(treeNode*&);
 void rotateLeft(treeNode*&);
+int largestElement(treeNode*);
+void createList(treeNode*, linkNode*&);
+void printList(linkNode*);
+void deallocateList(linkNode*&);
 
 int main() {
 	treeNode* firstTree = NULL;
+	linkNode* firstList = NULL;
 	tree_t newElement;
 	int n;	
 
@@ -43,37 +59,36 @@ int main() {
 	}
 
 	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 << "largest Element in tree: " << largestElement(firstTree);
 
-	cout << endl << "Rotate right: " << endl;
+	//cout << endl << "Rotate left: " << endl;
+	//rotateLeft(firstTree);
+	//printTree(firstTree);
 
+	cout << endl << "Trying to balance tree: " << endl;
+	rotateRight(firstTree->right);
 	rotateLeft(firstTree);
-
-	printTree(firstTree);
-
+	
 	cout << endl << "Height of tree: " << treeHeight(firstTree) << endl;
-	cout << endl << "Balanced Tree: " << isBalanced(firstTree) << endl;	
+	cout << endl << "Balanced Tree: " << isBalanced(firstTree) << endl;
+	cout << endl << "New head root node: " << firstTree->element << endl;
+
+	//cout << endl << "Rotating back right..." << endl;
+	//rotateRight(firstTree);
 
-	cout << endl << "new head root node: " << firstTree->element << endl;
+	cout << endl << "Creating linked list: " << endl;
+	createList(firstTree, firstList);
+	printList(firstList);
 	
 	deallocateTree(firstTree);
+	deallocateList(firstList);
 
-	cout << endl << "successfully deallocated tree..." << endl;
+	cout << endl << "successfully deallocated tree and list..." << endl;
 	return 0;
 }
 
@@ -140,7 +155,7 @@ void deleteLeftMost(treeNode* &hdTree, tree_t &leftMost) {
 
 int treeHeight(treeNode* hdTree) {
 	if(hdTree == NULL) {
-		return 0;
+		return -1;
 	}
 	return 1 + max(treeHeight(hdTree->left), treeHeight(hdTree->right));
 }
@@ -154,12 +169,9 @@ bool isBalanced(treeNode* hdTree) {
 	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;
 	}
@@ -186,3 +198,39 @@ void rotateLeft(treeNode* &hdTree) {
 	tmpTree->right = hdTree->left;
 	hdTree->left = tmpTree;
 }
+
+int largestElement(treeNode* hdTree) {
+	if(hdTree->right == NULL) {
+		return hdTree->element;
+	}
+	return largestElement(hdTree->right);
+}
+
+void createList(treeNode* hdTree, linkNode* &hdList) {
+	if(hdTree != NULL) {
+		createList(hdTree->left, hdList);
+		linkNode* newElement = new linkNode(hdTree->element);
+		newElement->next = hdList;
+		hdList = newElement;
+		createList(hdTree->right, hdList);
+	}
+}
+
+void printList(linkNode* hdList) {
+	if(hdList != NULL) {
+		if(hdList->next == NULL) {
+			cout << hdList->element << endl;
+		} else {
+			cout << hdList->element << " -> ";
+		}
+		printList(hdList->next);
+	}
+}
+
+void deallocateList(linkNode* &hdList) {
+	if(hdList != NULL) {
+		linkNode* tmp = hdList->next;
+		delete hdList;
+		deallocateList(tmp);
+	}
+}
-- 
cgit