Mobile Game Developer Forums
Welcome, Guest
Apphex Forums
>
New IT Techniques
>
Programming Languages & Tools
Binary Trees Algorithm (C++)
Binary Trees Algorithm (C++)
Previous Thread
·
Next Thread
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 20170413
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, treelike 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 nonempty 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 nonrecursive 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 nonempty, 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 inorder successor node or its inorder predecessor node, R. Replace the value of N with the value of R, then delete R. As with all binary trees, a node's inorder successor is the leftmost child of its right subtree, and a node's inorder predecessor is the rightmost 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 nonnull 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 nonmembers 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. InOrder Traversal "<<endl;
cout<<" 3. PreOrder Traversal "<<endl;
cout<<" 4. PostOrder 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<<" InOrder Traversal "<<endl;
cout<<" "<<endl;
b.printInorder();
break;
case 3 : cout<<endl;
cout<<" PreOrder Traversal "<<endl;
cout<<" "<<endl;
b.printPreorder();
break;
case 4 : cout<<endl;
cout<<" PostOrder 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
Back to top
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
Back to top
siley
Posted :
Fri, 11 Aug 2017 19:25:53 
[#3]
Rank:
New Member
Joined: 8/24/2016
Posts: 13
Rubies: 17
Location: Toronto
Bookmarked. +1 :D :X :P
Back to top
Forum Jump
Announcements
 Releases, Events & Offerings
Mobile Game Development
 Android Game Programming
 iOS Game Programming
 Programming Tutorials & Free Downloads
New IT Techniques
 Breaking into the Game Industry
 Java Development
 Programming Languages & Tools
 Database Development
 Everything Linux/Unix
News and Talk
 Hot Games, Apps & More
 Everything Mobile
 Walkthroughs & Guides
 Ringtone & Wallpaper Downloads
Community Interaction
 Comments, Suggestions & Ideas
 Lounge
 Help Wanted
 Support & Feedback
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 :
This page was generated in 0.799 seconds
Watch this thread
RSS Feed
Email this thread
Print this thread
Threaded
Normal
Home

Top Mobile Games

Developer Resource

Forum Rules

Sitemap

Downloads

Contact Us

About Us
Copyright ©2017 
Apphex Forums
Powered by:
cstcode
v1.0.5