From 050fcedf124b15f4f94cadbed73d8d95c354d7b6 Mon Sep 17 00:00:00 2001 From: zedarider Date: Sun, 13 Mar 2016 22:41:56 +0000 Subject: Adding binary tree algorithms --- C++/.#BinaryTree.cpp | 1 + C++/BinaryTree | Bin 0 -> 12480 bytes C++/BinaryTree.cpp | 119 +++++++++++++++++++++++++++++++++++++++++++++++---- C++/BinaryTrees.pdf | Bin 0 -> 1385527 bytes C++/rec | Bin 0 -> 9968 bytes C++/rec.cpp | 24 +++++++++++ 6 files changed, 135 insertions(+), 9 deletions(-) create mode 120000 C++/.#BinaryTree.cpp create mode 100755 C++/BinaryTree create mode 100644 C++/BinaryTrees.pdf create mode 100755 C++/rec create mode 100644 C++/rec.cpp diff --git a/C++/.#BinaryTree.cpp b/C++/.#BinaryTree.cpp new file mode 120000 index 0000000..caeba0d --- /dev/null +++ b/C++/.#BinaryTree.cpp @@ -0,0 +1 @@ +yannherklotz@Yann-Arch.1096:1457904846 \ No newline at end of file diff --git a/C++/BinaryTree b/C++/BinaryTree new file mode 100755 index 0000000..247641a Binary files /dev/null and b/C++/BinaryTree differ 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; } diff --git a/C++/BinaryTrees.pdf b/C++/BinaryTrees.pdf new file mode 100644 index 0000000..dfc5e11 Binary files /dev/null and b/C++/BinaryTrees.pdf differ diff --git a/C++/rec b/C++/rec new file mode 100755 index 0000000..d2ed520 Binary files /dev/null and b/C++/rec differ diff --git a/C++/rec.cpp b/C++/rec.cpp new file mode 100644 index 0000000..9ec892e --- /dev/null +++ b/C++/rec.cpp @@ -0,0 +1,24 @@ +#include + +using namespace std; + +void returnDigits(int&); + +int main(int argc, char** argv) { + int n; + cout << "input a number to seperate:" << endl; + cin >> n; + returnDigits(n); + return 0; +} + +void returnDigits(int &n) { + if(n > 10) { + int d = n % 10; + n /= 10; + returnDigits(n); + cout << d << endl; + } else { + cout << n << endl; + } +} -- cgit