top mobile game developers forum
Mobile Game Developer Forums

Binary Trees Algorithm (C++)

Binary Trees Algorithm (C++)
cstcoder
Posted : Thu, 13 Apr 2017 22:18:51 - [#1]


Group:  Moderator  
Rank:   Bronze Member
Joined:  6/29/2016
Posts:   23
Rubies:  993 
Location:  Vancouver
By cstcoder 2017-04-13

1.Basic Concepts



The binary tree is a fundamental data structure for rapidly storing sorted data and rapidly retrieving stored data. A binary tree is composed of parent nodes, or leaves, each of which stores data and also links to up to two other child nodes (leaves).
For example, a binary tree of integers could be made up of objects of the following type:
Code:
struct TreeNode
{
    int key;
    TreeNode *left;
    TreeNode *right;
};
Typedef struct TreeNode node;


The left and right pointers in a TreeNode can be NULL or can point to other objects of type TreeNode. A node that points to another node is said to be the parent of that node, and the node it points to is called a child. In the picture at the top, node 3 is the parent of node 6, and nodes 4 and 5 are children of node 2. Not every linked structure made up of tree nodes is a binary tree. A binary tree must have the following properties: There is exactly one node in the tree which has no parent. This node is called the root of the tree. Every other node in the tree has exactly one parent. Finally, there can be no loops in a binary tree. That is, it is not possible to follow a chain of pointers starting at some node and arriving back at the same node.
A node that has no children is called a leaf. A leaf node can be recognized by the fact that both the left and right pointers in the node are NULL. In the standard picture of a binary tree, the root node is shown at the top and the leaf nodes at the bottom -- which doesn't show much respect with the analogy to real trees. But at least you can see the branching, tree-like structure that gives a binary tree its name.
Consider any node in a binary tree. Look at that node together with all its descendents (that is, its children, the children of its children, and so on). This set of nodes forms a binary tree, which is called a subtree of the original tree. For example, in the picture, nodes 2, 4, and 5 form a subtree. This subtree is called the left subtreeof the root. Similarly, nodes 3 and 6 make up the right subtree of the root. We can consider any non-empty binary tree to be made up of a root node, a left subtree, and a right subtree. Either or both of the subtrees can be empty. This is a recursive definition, matching the recursive definition of the TreeNode class. So it should not be a surprise that recursive functions are often used to process trees.
Consider the problem of counting the nodes in a binary tree. As an exercise, you might try to come up with a non-recursive algorithm to do the counting. The heart of problem is keeping track of which nodes remain to be counted. It's not so easy to do this, and in fact it's not even possible without using an auxiliary data structure. With recursion, however, the algorithm is almost trivial. Either the tree is empty or it consists of a root and two subtrees. If the tree is empty, the number of nodes is zero. (This is the base case of the recursion.) Otherwise, use recursion to count the nodes in each subtree. Add the results from the subtrees together, and add one to count the root. This gives the total number of nodes in the tree. Written out in C++:
Code:
int countNodes( TreeNode *root ) {
    // Count the nodes in the binary tree to which
    // root points, and return the answer.
    if ( root == NULL )
        return 0;  // The tree is empty.  It contains no nodes.
    else {
        int count = 1;   // Start by counting the root.
        // Add the number of nodes in the left subtree
        count += countNodes(root->left); 
       
        // Add the number of nodes in the right subtree
        count += countNodes(root->right);

        return count;  // Return the total.
     }
} // end countNodes()

Or, consider the problem of printing the items in a binary tree. If the tree is empty, there is nothing to do. If the tree is non-empty, then it consists of a root and two subtrees. Print the item in the root and use recursion to print the items in the subtrees. Here is a function that prints all the items on one line of output:
Code:
void preorderPrint( TreeNode *root ) {
    // Print all the items in the tree to which root points.
    // The item in the root is printed first, followed by the
    // items in the left subtree and then the items in the
    // right subtree.
    if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
        cout << root->item << " ";      // Print the root item.
        preorderPrint( root->left );    // Print items in left subtree.
        preorderPrint( root->right );   // Print items in right subtree.
    }
} // end preorderPrint()

This routine is called "preorderPrint" because it uses a preorder traversal of the tree. In a preorder traversal, the root node of the tree is processed first, then the left subtree is traversed, then the right subtree. In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed. And in an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed. Printing functions that use postorder and inorder traversal differ from preorderPrint only in the placement of the statement that outputs the root item:
Code:
void postorderPrint( TreeNode *root ) {
    /*
     * Print all the items in the tree to which root points.
     * The items in the left subtree are printed first, followed
     * by the items in the right subtree and then the item in the
     * root node.
     */
    if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
        postorderPrint( root->left );    // Print items in left subtree.
        postorderPrint( root->right );   // Print items in right subtree.
        cout << root->item << " ";       // Print the root item.
    }
} // end postorderPrint()

void inorderPrint( TreeNode *root ) {
    // Print all the items in the tree to which root points.
    // The items in the left subtree are printed first, followed
    // by the item in the root node, followed by the items in
    // the right subtree.
    if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
        inorderPrint( root->left );    // Print items in left subtree.
        cout << root->item << " ";     // Print the root item.
        inorderPrint( root->right );   // Print items in right subtree.
    }
} // end inorderPrint()

Each of these functions can be applied to the binary tree shown in the illustration at the beginning of this section. The order in which the items are printed differs in each case:
preorderPrint outputs: 1 2 4 5 3 6
postorderPrint outputs: 4 5 2 6 3 1
inorderPrint outputs: 4 2 5 1 3 6

In preorderPrint, for example, the item at the root of the tree, 1, is output before anything else. But the preorder printing also applies to each of the subtrees of the root. The root item of the left subtree, 2, is printed before the other items in that subtree, 4 and 5. As for the right subtree of the root, 3 is output before 6. A preorder traversal applies at all levels in the tree. The other two traversal orders can be analyzed similarly.
There’re 3 cases to remove a node from a tree:
-Node is a terminal node: In this case, if the node is a left child of its parent, then the left pointer of its parent is set to NULL. Otherwise if the node is a right child of its parent, then the right pointer of its parent is set to NULL
-Node has only one child: In this case, the appropriate pointer of its parent is set to child node.
-Node has two children: Choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R. As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree.



Suppose the node 75 to be removed from the tree

2.Binary Tree Class
The struct has the ability to store the key_value and contains the two child nodes which define the node as part of a tree. In fact, the node itself is very similar to the node in a linked list. A basic knowledge of the code for a linked list will be very helpful in understanding the techniques of binary trees. Essentially, pointers are necessary to allow the arbitrary creation of new nodes in the tree.
It is most logical to create a binary tree class to encapsulate the workings of the tree into a single area, and also making it reusable. The class will contain functions to insert data into the tree and to search for data. Due to the use of pointers, it will be necessary to include a function to delete the tree in order to conserve memory after the program has finished.
Code:
#include <iostream>
#include <cstdlib>
using namespace std;

class BTree {
private:
    typedef struct TreeNode {
        int key;
        TreeNode* left;
        TreeNode* right;
    } node;
    node* root;

    void destroyTree(node* leaf);
    void insert(int key, node* leaf);
    void remove(int key, node* leaf);
    node *search(int key, node* leaf);
   
public:
    BTree();
    ~BTree();
       
    bool isEmpty() const { return root==NULL; }
    void printInorder();
    void inorder(node*);
    void printPreorder();
    void preorder(node*);
    void printPostorder();
    void postorder(node*);
    void destroyTree();
    void insert(int);
    void remove(int);
    node *search(int);
};


The insert,remove and search functions that are public members of the class are designed to allow the user of the class to use the class without dealing with the underlying design. The insert,remove and search functions which will be called recursively are the ones which contain two parameters, allowing them to travel down the tree. The destroy_tree function without arguments is a front for the destroy_tree function which will recursively destroy the tree, node by node, from the bottom up.
The code for the class would look similar to the following:
Code:
BTree::Btree() {
    root = NULL;
}


It is necessary to initialize root to NULL for the later functions to be able to recognize that it does not exist.
Code:
BTree::~BTree() {
  destroyTree();
}

void BTree::destroyTree() {
  destroy_tree(root);
}

The destroyTree function will set off the recursive function destroyTree shown below which will actually delete all nodes of the tree.
Code:
void BTree::destroyTree(node *leaf) {
    if(leaf!=NULL) {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
        delete leaf;
    }
}

The function destroy_tree goes to the bottom of each part of the tree, that is, searching while there is a non-null node, deletes that leaf, and then it works its way back up. The function deletes the leftmost node, then the right child node from the leftmost node's parent node, then it deletes the parent node, then works its way back to deleting the other child node of the parent of the node it just deleted, and it continues this deletion working its way up to the node of the tree upon which delete_tree was originally called. Note that it is necessary to delete all the child nodes to avoid wasting memory.
Code:
void BTree::insert(int key, node *leaf) {
    if(key< leaf->key) {
        if(leaf->left!=NULL)
            insert(key, leaf->left);
        else {
            leaf->left=new node;
            leaf->left->key=key;
            leaf->left->left=NULL;    //Sets the left child of the child node to null
            leaf->left->right=NULL;   //Sets the right child of the child node to null
        } 
    } else if(key>=leaf->key) {
        if(leaf->right!=NULL)
            insert(key, leaf->right);
        else {
            leaf->right=new node;
            leaf->right->key =key;
            leaf->right->left=NULL;  //Sets the left child of the child node to null
            leaf->right->right=NULL; //Sets the right child of the child node to null
        }
    }
}

The case where the root node is still NULL will be taken care of by the insert function that is nonrecursive and available to non-members of the class. The insert function searches, moving down the tree of children nodes, following the prescribed rules, left for a lower value to be inserted and right for a greater value, until it finds an empty node which it creates using the 'new' keyword and initializes with the key value while setting the new node's child node pointers to NULL. After creating the new node, the insert function will no longer call itself.
Code:
void BTree::insert(int key) {
    if(root != NULL)
        insert(key, root);
    else {
        root=new node;
        root->key=key;
        root->left=NULL;
        root->right=NULL;
    }
}

The public version of the insert function takes care of the case where the root has not been initialized by allocating the memory for it and setting both child nodes to NULL and setting the key_value to the value to be inserted. If the root node already exists, insert is called with the root node as the initial node of the function, and the recursive insert function takes over.
Code:
void BTree::remove(int key, node* leaf) {
    //Locate the element
    bool found = false;

    if(isEmpty()) {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
   
    node* curr;
    node* parent;
    curr = leaf;
   
    while(curr != NULL) {
        if(curr->key== key) {
            found = true;
            break;
        } else {
            parent = curr;
            if(key>curr->key) curr = curr->right;
            else curr = curr->left;
        }
    }

    if(!found) {
        cout<<" Data not found! "<<endl;
        return;
    }

    // 3 cases :
    // 1. Remove a leaf node
    // 2. Remove a node with a single child
    // 3. Remove a node with 2 children

    //1. Leaf node
    if( curr->left == NULL && curr->right == NULL) {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
        delete curr;
        return;
    }

    //2.Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
        && curr->right == NULL)) {
        if(curr->left == NULL && curr->right != NULL) { //right child
            if(parent->left == curr) {
                parent->left = curr->right;
                delete curr;
            } else {
                parent->right = curr->right;
                delete curr;
            }
       } else { // left child present, no right child
           if(parent->left == curr) {
               parent->left = curr->left;
               delete curr;
           } else {
               parent->right = curr->left;
               delete curr;
           }
       }

       return;
    }

    //3. Node with 2 children
    // replace node with smallest value (successor) in right subtree
    if (curr->left != NULL && curr->right != NULL) {
        node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL)) {// right child has no children
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        } else { // right child has children
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element
            if((curr->right)->left != NULL) {
                node* lcurr;
                node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;

                while(lcurr->left != NULL) {
                    lcurrp = lcurr;
                    lcurr = lcurr->left;
                }

                curr->key = lcurr->key;
                delete lcurr;
                lcurrp->left = NULL;
            } else {
                node* lcurr;
                lcurr = curr->right;
                curr->key = lcurr->data;
                curr->right = lcurr->right;
                delete lcurr;
            }
        }

        return;
    }
}

This remove function considers 3 cases: the node to be removed is a leaf, a node with only one child, or has 2 both sides children. The public remove function is as below:
Code:
void BTree::remove(int key) {
    if(root != NULL)
        remove(key,root);
}
node *BTree::search(int key, node *leaf) {
    if(leaf != NULL) {
        if(key==leaf->key_value)
            return leaf;
        if(key<leaf->key_value)
            return search(key, leaf->left);
        else
            return search(key, leaf->right);
    }
    else return NULL;
}

The search function shown above recursively moves down the tree until it either reaches a node with a key value equal to the value for which the function is searching or until the function reaches an uninitialized node, meaning that the value being searched for is not stored in the binary tree. It returns a pointer to the node to the previous instance of the function which called it, handing the pointer back up to the search function accessible outside the class.
Code:
node *BTree::search(int key) {
    return search(key, root);
}


The public version of the search function is used to set off the search recursion at the root node, keeping it from being necessary for the user to have access to the root node.
Code:
//main function
int main() {
    BTree b;
    int ch,tmp,tmp1;
    while(1) {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. In-Order Traversal "<<endl;
       cout<<" 3. Pre-Order Traversal "<<endl;
       cout<<" 4. Post-Order Traversal "<<endl;
       cout<<" 5. Removal "<<endl;
       cout<<" 6. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;

       switch(ch) {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<<endl;
                    cout<<" In-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.printInorder();
                    break;
           case 3 : cout<<endl;
                    cout<<" Pre-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.printPreorder();
                    break;
           case 4 : cout<<endl;
                    cout<<" Post-Order Traversal "<<endl;
                    cout<<" --------------------"<<endl;
                    b.printPostorder();
                    break;
           case 5 : cout<<" Enter data to be deleted : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 6 :
                    return 0;
                   
       }
    }
}


3.Binary Search
3.1 Divide in Half
A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.
3.2 Performance
The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element. Probably the only faster kind of search uses hashing, a topic that isn't covered in these notes.
This performance comes at a price - the array must be sorted first (Array.Sort(sortedArray);
). Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches. (Array reverse: Array.Reverse(sortedArray) )

3.3 Implementation

Code:
int binarySearch(int sortedArray[], int first, int last, int key) {
   // Searches sortedArray[first]..sortedArray[last] for key. 
   // returns: index of the matching element if it finds key,
   // otherwise  -(index where it could be inserted)-1.
   // parameters:
   //   sortedArray in  array of sorted (ascending) values.
   //   first, last in  lower and upper subscript bounds
   //   key         in  value to search for.
   // returns:
   //   index of key, or -insertion_position -1 if key is not
   //               in the array. This value can easily be
   //               transformed into the position to insert it.
   
   while (first <= last) {
       int mid = (first + last) / 2;  // compute mid point.
       if (key > sortedArray[mid])
           first = mid + 1;  // repeat search in top half.
       else if (key < sortedArray[mid])
           last = mid - 1; // repeat search in bottom half.
       else
           return mid;     // found it. return position /////
   }

   return -1;    // failed to find key
}


4. Related Data Structure: Linked List
Finish the code to sort a linked list in ascending order.
Code:
Typedef struct _Node {
    int key;
    Node* next;
}Node;

int number;
Node* head, lnode, curr, curr1;
Node* create() {
    Cout<<"Input the number of node to be created: "<<endl;
    scanf("%d", &number );
    head->next = NULL;  // Empty list
    lnode = head;      // Point to the head of the list

    // CREATE A LINKED LIST
    for (i = 0; i < number ; i++) {
        lnode->next = (struct node* ) malloc(sizeof(struct node));
        lnode = lnode->next;
        cout<<"Input the first node:”<<i+1<<endl;
        scanf("%d", &lnode->key);
        lnode->next = NULL;
    }

    return lnode;
   // END OF CREATION
}

void sort(Node* head) {
    // SORTING THE LINK LIST START FROM HERE
    curr = head;  //curr = *head if sort prototype is void sort(Node** head)
    for(; curr->next != NULL; curr = curr->next) {
        for(curr1 = curr->next; curr1 != NULL; curr1 = curr1->next) {
            if(curr->key > curr1->key) {
                int temp = curr->key;
                curr->key = curr1->key;
                curr1->key = temp;
            }
        }
    }
    // END OF SORTING
}
// Display the list

void display(Node* head) {
    curr = head->next;
    cout << ” After sorting the list is as follows:” << endl;

    while (curr) {
        cout << curr->key;
        curr = curr->next;
    }
}



You never know till you have tried
Zambie
Posted : Fri, 14 Apr 2017 09:56:01 - [#2]


Rank:    New Member
Joined:  11/5/2016
Posts:   19
Rubies:  30 
Helpful for interviews - Thanks for sharing! :D
siley
Posted : Fri, 11 Aug 2017 19:25:53 - [#3]


Rank:    New Member
Joined:  8/24/2016
Posts:   13
Rubies:  17 
Location:  Toronto
Boo hoo! Angel Bookmarked. +1 :D :X :PApplause


Forum Jump
You may not post new threads in this forum.
You may not reply to threads in this forum.
You may not delete your posts in this forum.
You may not edit your posts in this forum.
You may not create polls in this forum.
You may not vote in polls in this forum.
Main Forum RSS : RSS
This page was generated in 0.771 seconds
Home | Top Mobile Games | Developer Resource | Forum Rules | Sitemap | Downloads | Contact Us | About Us
Copyright ©2017 - Apphex Forums  Powered by: cstcode v1.0.5