{"id":1075,"date":"2017-03-23T08:28:59","date_gmt":"2017-03-23T15:28:59","guid":{"rendered":"http:\/\/somethingk.com\/main\/?p=1075"},"modified":"2017-03-28T07:08:04","modified_gmt":"2017-03-28T14:08:04","slug":"binary-search-trees-simple-class-in-c","status":"publish","type":"post","link":"http:\/\/somethingk.com\/main\/binary-search-trees-simple-class-in-c\/","title":{"rendered":"Binary Search Trees! Simple Class in C++"},"content":{"rendered":"<section id=\"text-4\" class=\"widget boka-widget widget_text amr_widget\">\t\t\t<div class=\"textwidget\"><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\r\n<ins class=\"adsbygoogle\"\r\n     style=\"display:block; text-align:center;\"\r\n     data-ad-layout=\"in-article\"\r\n     data-ad-format=\"fluid\"\r\n     data-ad-client=\"ca-pub-7619916617995509\"\r\n     data-ad-slot=\"9102150708\"><\/ins>\r\n<script>\r\n     (adsbygoogle = window.adsbygoogle || []).push({});\r\n<\/script><\/div>\n\t\t<\/section>\n<p>Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.<\/p>\n<p>This class also uses the Node.h talked about in this earlier <a href=\"http:\/\/somethingk.com\/main\/?p=1003\">post<\/a>. You&#8217;ll notice that I really like to use recursion, I think this is cleaner than looping.<\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-1076\" data-id=\"1076\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/1075?snippet=8b8b00e8ef&#038;id=1076\" data-fullscreen=\"http:\/\/somethingk.com\/main\/code-snippets\/simple-binary-tree-class-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Simple Binary Tree Class in C++\">#include &lt;assert.h&gt;\r\n#include &quot;Node.h&quot;\r\nusing namespace std;\r\n\r\nclass Bst\r\n{\r\n    public:\r\n\r\n        \/\/constructor for when a head Node is provided and when it is not\r\n        Bst() {\r\n            root = nullptr;\r\n        }\r\n\r\n        Bst(Node *np) {\r\n            root = np;\r\n        }\r\n\r\n        \/\/destroy the tree, we need to go through and destroy each node\r\n        ~Bst() {\r\n            destroyTree(root);\r\n        }\r\n\r\n        \/\/get the number of nodes in the tree\r\n        int size() {\r\n            return size(root);\r\n        }\r\n\r\n        \/\/erase a value in the tree\r\n        void erase(int item) {\r\n            erase(item, root);\r\n        }\r\n\r\n        \/\/insert a Node in the tree\r\n        void insert(int item) {\r\n            insert(item, root);\r\n        }\r\n\r\n    private:\r\n\r\n        Node* root;\r\n\r\n        \/\/Go through each branch and recursively destroy all Nodes\r\n        void destroyTree(Node*&amp; n) {\r\n            if (n != nullptr) {\r\n                destroyTree(n-&gt;left);\r\n                destroyTree(n-&gt;right);\r\n                delete n;\r\n            }\r\n        }\r\n\r\n        \/\/For each Node return the number of left and right nodes\r\n        \/\/Add it up recursively to get the total size\r\n        int size(Node* n) {\r\n            if (n != nullptr) {\r\n                int left = size(n-&gt;left);\r\n                int right = size(n-&gt;right);\r\n                int self = 1;\r\n                return left + self + right;\r\n            }\r\n            return 0;\r\n        }\r\n\r\n        \/\/Find the minimum Node value\r\n        Node* findMin(Node* n){\r\n            assert(n != nullptr);\r\n            if (n-&gt;left != nullptr) {\r\n                return findMin(n-&gt;left);\r\n            }\r\n            return n;\r\n        }\r\n\r\n        \/\/this one is a beast\r\n        \/\/look through all the nodes recursively\r\n        \/\/once you find the node value there are numerous cases we need to look for\r\n        \/\/If the current node does not have left and right nodes, just delete it\r\n        \/\/If it does have a left or right node, set the child to the parent\r\n        \/\/If it has both left and right, we need to work some magic. First we find\r\n        \/\/the smallest value and set the node we want to delete to that value (removing it)\r\n        void erase(int item, Node*&amp; n) {\r\n            if (n != nullptr) {\r\n                if (item == n-&gt;data) {\r\n                    if (n-&gt;right == nullptr &amp;&amp; n-&gt;left == nullptr) {\r\n                        delete n;\r\n                        n = nullptr;\r\n                    } else if (n-&gt;right == nullptr) {\r\n                        Node* temp = n;\r\n                        n = n-&gt;left;\r\n                        delete n;\r\n                    } else if (n-&gt;left == nullptr){\r\n                        Node* temp = n;\r\n                        n = n-&gt;right;\r\n                        delete n;\r\n                    } else {\r\n                        Node *temp = findMin(n-&gt;right);\r\n                        n-&gt;data = temp-&gt;data;\r\n                        erase(item, n-&gt;right);\r\n                    }\r\n                } else if (item &lt; n-&gt;data) {\r\n                    erase(item, n-&gt;left);\r\n                } else {\r\n                    erase(item, n-&gt;right);\r\n                } \r\n            }\r\n        }\r\n\r\n        \/\/look through all the nodes\r\n        \/\/insert the node on the correct node, it will be added to the left if the value is less\r\n        \/\/added to the right if the value is greater\r\n        void insert(int item, Node*&amp; n) {\r\n            if (n != nullptr) {\r\n                if (item &lt; n-&gt;data) {\r\n                    insert(item, n-&gt;left);\r\n                } else {\r\n                    insert(item, n-&gt;right);\r\n                }\r\n            } else {\r\n                n = new Node(item);\r\n            }\r\n        }\r\n};\r\n<\/pre>\n\t\t\t<\/div>\n<p>Let me know if you have any improvements or comments!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals. This class also uses the Node.h talked about in this earlier post. You&#8217;ll notice that I really like to use recursion, I think this is cleaner than looping. Let me [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[177],"tags":[581,497,539,303,540,541,508,505,509],"class_list":["post-1075","post","type-post","status-publish","format-standard","hentry","category-development","tag-binary-search-tree","tag-binary-tree","tag-bst","tag-c","tag-class","tag-erase","tag-insert","tag-simple","tag-size"],"_links":{"self":[{"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1075","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/comments?post=1075"}],"version-history":[{"count":2,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1075\/revisions"}],"predecessor-version":[{"id":1114,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1075\/revisions\/1114"}],"wp:attachment":[{"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/media?parent=1075"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/categories?post=1075"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/tags?post=1075"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}