Monday, 12 January 2015

Binary Search tree in C++(BST) with examples:

Binary Search tree in Cpp(BST) with examples:

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.

The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees”.

Empty tree: A null pointer represents a binary tree with no elements -- the empty tree.
The formal recursive definition is: a binary tree is either empty, or is made of a single node,

Where the left and right pointers (recursive definition ahead) each point to a binary tree.
They differentiate only with one feature that is the organization of the data.

Here is the small example that helps us to understand the binary tree
A binary tree is a tree that is limited such that each node has only two children.



Binary Tree
 Definitions:

If n1 is the root of a binary tree and n2 is the root of its left or right tree, then n1 is the parent of n2 and n2 is the left of n1.

A node that has no children is called a leaf, here the leaf nodes are n4, n5, n6
The nodes are siblings if they are left and right children of the same parent.

The level of a node in a binary tree:
The root of the tree has level 0
The level of any other node in the tree is one more than the level of its parent.

Structure of the binary tree:

root = NULL; // empty tree

Each node of a binary tree has both left and right sub trees which can be reached with pointers:
Struct T_node{

int data;

struct T_node *stL_child;

struct T_node *stR_child;

};

 
Binary Trees Traversal:

Three are three possible tree traversals orderings available, those are shown below:
•Preorder

•Inorder

•Postorder


These names are chosen according to the step at which the root node is visited.

Preorder traversal:
The node is visited before its left and right sub trees.

Inorder traversal:
The root is visited first between the subt rees.

Post order traversal:
The root is visited last after both sub trees.

Example:
4
/ \
2 5
/ \
1 3

Produces the output "1 2 3 4 5". This is known as an "inorder" traversal of the tree.
Preorder: 4 2 1 5 3

Inorder: 1 2 3 4 5

Postorder: 1 3 2 5 4


Finding the maximum value in a binary tree:

Compute the "maxDepth" of a tree -- the number of nodes along
the longest path from the root node down to the farthest leaf node.

int FindMaxDepth(struct node* stNode) {

if (stNode==NULL) {    
    return(0);
}

else {
// compute the depth of each subtree

int lDepth = FindMaxDepth(stNode->left);

int rDepth = FindMaxDepth(stNode->right);

// use the larger one

if (lDepth > rDepth)

 return(lDepth + 1);

 else

 return(rDepth + 1);

}

}


How to add all values in a Binary Tree:
int add(struct node* stNode) {

if (stNode == NULL)

return 0;

else

return (stNode ->data + add(stNode ->left_child)+

add(stNode ->right_child));

}


No comments: