Unbalanced binary trees degenerating like big arrays or lists and an access of any element can be in worst case a complexity of:
That means that in worst case a searching to any element walk trough the whole tree.
1 | #ifndef tree_h
|
2 | #define tree_h
|
3 | #include "node.h"
|
4 |
|
5 | class tree {
|
6 | private:
|
7 |     struct node *root;
|
8 |     
|
9 |     struct node *append_node(int);
|
10 |     struct node *insert_node(struct node *, int);
|
11 |     
|
12 |     static unsigned height(const node *node);
|
13 |     static unsigned width(const node *node);
|
14 |     
|
15 |     struct node *min_value_node(struct node *);
|
16 |     struct node *delete_node(struct node *, int);
|
17 |
|
18 |     void print_preorder(struct node *);
|
19 |     void print_inorder(struct node *);
|
20 |     void print_postorder(struct node *);
|
21 |     
|
22 |     static std::string format_label(const node *node);
|
23 |     static void dump_spaces(std::ostream &out, unsigned count);
|
24 |     static void dump_line(std::ostream &out, const node *node, unsigned line);
|
25 |     static void dump_node(std::ostream &out, const node *node);
|
26 |     
|
27 |     void delete_tree(struct node *node);
|
28 | public:
|
29 |     tree();
|
30 |     ~tree();
|
31 |     void insert(int new_node);
|
32 |     void delete_node(int);
|
33 |     void print_height();
|
34 |     void print_width();
|
35 |     void print_preorder();
|
36 |     void print_inorder();
|
37 |     void print_postorder();
|
38 |     void print_tree();
|
39 | };
|
40 |
|
41 | #endif |
1 | #ifndef insert_h
|
2 | #define insert_h
|
3 |
|
4 | struct node *tree::append_node(int new_data) {
|
5 |     struct node *new_node = new struct node;
|
6 |     new_node->data = new_data;
|
7 |     new_node->left = NULL;
|
8 |     new_node->right = NULL;
|
9 |     return new_node;
|
10 | }
|
11 |
|
12 | struct node *tree::insert_node(struct node *new_node, int new_data) {
|
13 |     if(new_node == NULL) return append_node(new_data);
|
14 |     if(new_node->data > new_data) new_node->left = insert_node(new_node->left, new_data);
|
15 |     else new_node->right = insert_node(new_node->right, new_data);
|
16 |     
|
17 |     return new_node;
|
18 | }
|
19 |
|
20 | void tree::insert(int new_data) {
|
21 |     root = insert_node(root,new_data);
|
22 | }
|
23 |
|
24 | #endif |
1 | #ifndef deletenode_h
|
2 | #define deletenode_h
|
3 |
|
4 | /* Given a non-empty binary search tree, return the node with minimum
|
5 | key value found in that tree. Note that the entire tree does not
|
6 | need to be searched. */
|
7 | struct node *tree::min_value_node(struct node *wanted_node) {
|
8 |     struct node *current = wanted_node;
|
9 |     
|
10 |     //loop down to find the leftmost leaf
|
11 |     while(current->left != NULL) {
|
12 |         current = current->left;
|
13 |     }
|
14 |     return current;
|
15 | }
|
16 | /* Given a binary search tree and a key, this function deletes the key
|
17 | and returns the new root */
|
18 | struct node *tree::delete_node(struct node *root_ref, int wanted_data) {
|
19 |     // base case
|
20 |     if(root_ref == NULL) return root_ref;
|
21 |     
|
22 |     // If the key to be deleted is smaller than the root's key, // then it lies in left subtree
|
23 |     if(wanted_data < root_ref->data) root_ref->left = delete_node(root_ref->left, wanted_data);
|
24 |     
|
25 |     // If the key to be deleted is greater than the root's key, // then it lies in right subtree
|
26 |     else if(wanted_data > root_ref->data) root_ref->right = delete_node(root_ref->right, wanted_data);
|
27 |     
|
28 |     // if key is same as root's key, then This is the node // to be deleted
|
29 |     else {
|
30 |         if(root_ref->left == NULL) {
|
31 |             struct node *temp = root_ref->right;
|
32 |             delete root_ref;
|
33 |             return temp;
|
34 |         }
|
35 |         else if(root_ref->right == NULL) {
|
36 |             struct node *temp = root_ref->left;
|
37 |             delete root_ref;
|
38 |             return temp;
|
39 |         }
|
40 |         
|
41 |         // node with two children: Get the inorder successor (smallest // in the right subtree)
|
42 |         struct node *temp = min_value_node(root_ref->right);
|
43 |         
|
44 |         // Copy the inorder successor's content to this node
|
45 |         root_ref->data = temp->data;
|
46 |         
|
47 |         // Delete the inorder successor
|
48 |         root_ref->right = delete_node(root_ref->right, temp->data);
|
49 |     }
|
50 |     return root_ref;
|
51 | }
|
52 |
|
53 | void tree::delete_node(int wanted_data) {
|
54 |     delete_node(root, wanted_data);
|
55 | }
|
56 |
|
57 | #endif |
1 | #ifndef treeoutput_h
|
2 | #define treeoutput_h
|
3 | #include <iostream>
|
4 | #include <sstream>
|
5 | #include <string>
|
6 |
|
7 | std::string tree::format_label(const node *node) {
|
8 |     if(node) {
|
9 |         std::ostringstream out;
|
10 |         out << node->data;
|
11 |         return out.str();
|
12 |     }
|
13 |     else return "";
|
14 | }
|
15 |
|
16 | void tree::dump_spaces(std::ostream &out, unsigned count) {
|
17 |     for(unsigned i = 0; i < count; ++i) {
|
18 |         out.put(' ');
|
19 |     }
|
20 | }
|
21 |
|
22 | void tree::dump_line(std::ostream &out, const node *node, unsigned line){
|
23 |     if(!node) return;
|
24 |     if(line == 1) {
|
25 |         //output root
|
26 |         dump_spaces(out, width(node->left));
|
27 |         out << format_label(node);
|
28 |         dump_spaces(out, width(node->right));
|
29 |     }
|
30 |     else {
|
31 |         //the roots are one level down and the line number is changed of both subtrees
|
32 |         dump_line(out, node->left, line-1);
|
33 |         dump_spaces(out, format_label(node).length());
|
34 |         dump_line(out, node->right, line-1);
|
35 |     }
|
36 | }
|
37 |
|
38 | void tree::dump_node(std::ostream &out, const node *node) {
|
39 |     for(unsigned line = 1, h = height(node); line <= h; ++line) {
|
40 |         dump_line(out, node, line);
|
41 |         out.put('\n');
|
42 |     }
|
43 |     out.flush();
|
44 | }
|
45 |
|
46 | void tree::print_tree() {
|
47 |     dump_node(std::cout, root);
|
48 | }
|
49 |
|
50 | #endif |
1 | #ifndef print_h
|
2 | #define print_h
|
3 |
|
4 | void tree::print_preorder(struct node *tree_ref) {
|
5 |     if(tree_ref == NULL) return;
|
6 |     else {
|
7 |         std::cout << tree_ref->data << " ";
|
8 |         print_preorder(tree_ref->left);
|
9 |         print_preorder(tree_ref->right);
|
10 |     }
|
11 | }
|
12 |
|
13 | void tree::print_preorder() {
|
14 |     print_preorder(root);
|
15 | }
|
16 |
|
17 | void tree::print_inorder(struct node *tree_ref) {
|
18 |     if(tree_ref == NULL) return;
|
19 |     else {
|
20 |         print_inorder(tree_ref->left);
|
21 |         std::cout << tree_ref->data << " ";
|
22 |         print_inorder(tree_ref->right);
|
23 |     }
|
24 | }
|
25 |
|
26 | void tree::print_inorder() {
|
27 |     print_inorder(root);
|
28 | }
|
29 |
|
30 | void tree::print_postorder(struct node *tree_ref) {
|
31 |     if(tree_ref == NULL) return;
|
32 |     else {
|
33 |         print_postorder(tree_ref->left);
|
34 |         print_postorder(tree_ref->right);
|
35 |         std::cout << tree_ref->data << " ";
|
36 |     }
|
37 | }
|
38 |
|
39 | void tree::print_postorder() {
|
40 |     print_postorder(root);
|
41 | }
|
42 |
|
43 | void tree::print_height() {
|
44 |     std::cout << "height: " << height(root) << std::endl;
|
45 | }
|
46 |
|
47 | void tree::print_width() {
|
48 |     std::cout << "width: " << width(root) << std::endl;
|
49 | }
|
50 |
|
51 | #endif |
1 | #include <iostream>
|
2 | #include "tree.h"
|
3 | #include "treesystem.h"
|
4 | #include "insert.h"
|
5 | #include "deleteNode.h"
|
6 | #include "height.h"
|
7 | #include "width.h"
|
8 | #include "print.h"
|
9 | #include "treeoutput.h"
|
10 |
|
11 | int main(int argc, char **argv) {
|
12 |     tree *new_tree = new tree;
|
13 |     
|
14 |     //insert into unbalanced
|
15 |     //for(int i = 1; i < 21; i++)
|
16 |         //new_tree->insert(i);
|
17 |     
|
18 |     //insert into tree balanced
|
19 |     new_tree->insert(9);
|
20 |     new_tree->insert(5);
|
21 |     new_tree->insert(7);
|
22 |     new_tree->insert(4);
|
23 |     //new_tree->insert(2);
|
24 |     //new_tree->insert(1);
|
25 |     new_tree->insert(3);
|
26 |     new_tree->insert(6);
|
27 |     new_tree->insert(8);
|
28 |     new_tree->insert(14);
|
29 |     new_tree->insert(11);
|
30 |     new_tree->insert(16);
|
31 |     new_tree->insert(13);
|
32 |     new_tree->insert(10);
|
33 |     new_tree->insert(17);
|
34 |     new_tree->insert(15);
|
35 |     
|
36 |     //print out in order (recursive)
|
37 |     std::cout << "Tree inorder:" << std::endl;
|
38 |     new_tree->print_inorder();
|
39 |     
|
40 |     //delete node
|
41 |     //new_tree->delete_node(11);
|
42 |     
|
43 |     //print out binary tree
|
44 |     std::cout << std::endl;
|
45 |     std::cout << "Binary tree:" << std::endl;
|
46 |     new_tree->print_tree();
|
47 |     
|
48 |     //delete tree
|
49 |     delete new_tree;
|
50 |     
|
51 |     return 0;
|
52 | } |