Unbalanced Binary Tree

Unbalanced binary trees degenerating like big arrays or lists and an access of any element can be in worst case a complexity of:

O(n)

That means that in worst case a searching to any element walk trough the whole tree.

node.h
1#ifndef node_h
2#define node_h
3
4struct node {
5    int data;
6    struct node *left;
7    struct node *right;
8};
9
10#endif
tree.h
1#ifndef tree_h
2#define tree_h
3#include "node.h"
4
5class tree {
6private:
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);
28public:
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
treesystem.h
1#ifndef treesystem_h
2#define treesystem_h
3
4tree::tree() {
5  root = NULL;
6}
7
8void tree::delete_tree(struct node *node) {
9  if(node != NULL) {
10    delete_tree(node->left);
11    delete_tree(node->right);
12    delete node;
13  }
14}
15
16tree::~tree() {
17  delete_tree(root);
18}
19
20#endif
height.h
1#ifndef height_h
2#define height_h
3
4unsigned tree::height(const node *node) {
5    if(!node) return 0;
6    unsigned left_height = 0, right_height = 0;
7 
8    if(node->left) left_height = height(node->left);
9    if(node->right) right_height = height(node->right);
10 
11    // Der höchste Unterbaum bestimmt die Gesamthöhe
12    return std::max(left_height, right_height) + 1;
13}
14
15#endif
width.h
1#ifndef width_h
2#define width_h
3
4unsigned tree::width(const node *node) {
5    if(!node) return 0;
6    unsigned left_width = 0, right_width = 0;
7 
8    if(node->left) left_width = width(node->left);
9    if(node->right) right_width = width(node->right);
10 
11    return left_width + format_label(node).length() + right_width;
12}
13
14#endif
insert.h
1#ifndef insert_h
2#define insert_h
3
4struct 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
12struct 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
20void tree::insert(int new_data) {
21    root = insert_node(root,new_data);
22}
23
24#endif
deleteNode.h
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. */
7struct 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 */
18struct 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
53void tree::delete_node(int wanted_data) {
54    delete_node(root, wanted_data);
55}
56
57#endif
treeoutput.h
1#ifndef treeoutput_h
2#define treeoutput_h
3#include <iostream>
4#include <sstream>
5#include <string>
6
7std::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
16void tree::dump_spaces(std::ostream &out, unsigned count) {
17    for(unsigned i = 0; i < count; ++i) {
18        out.put(' ');
19    }
20}
21
22void 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
38void 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
46void tree::print_tree() {
47    dump_node(std::cout, root);
48}
49
50#endif
print.h
1#ifndef print_h
2#define print_h
3
4void 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
13void tree::print_preorder() {
14    print_preorder(root);
15}
16
17void 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
26void tree::print_inorder() {
27    print_inorder(root);
28}
29
30void 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
39void tree::print_postorder() {
40    print_postorder(root);
41}
42
43void tree::print_height() {
44    std::cout << "height: " << height(root) << std::endl;
45}
46
47void tree::print_width() {
48    std::cout << "width: " << width(root) << std::endl;
49}
50
51#endif
main.cpp
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
11int 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}