Binary Tree:
A binary tree is a tree in which each
node can have maximum two children. Thus
each node can have no child, one child
or two children. The pointers help us to
identify whether it is a left child or a right child.
1.
The root of the tree has level
0
2.
The level of any other node in
the tree is one more than the level of
its parent.
Full Binary Tree
How many nodes?
Level0 : 1 node ( height 1)
Level 1: 2 nodes ( height 2)
Level 3 : 4 nodes (height 3)
Level 3: 8 nodes (height 4)
Total number of nodes
n = 2^h – 1 ( maximum)
h = log ( n+1)
Implementation
•A binary tree has a natural implementation
in linked storage. A tree is referenced with a pointer to its root . Recursive
definition of a binary tree .A binary tree is either Empty, or A node (called
root) together with two binary trees (called left subtree and the right subtree
of the root)
Each node of a binary tree has both left
and right subtrees which can be reached
with pointers:
struct tree_node{
int data;
struct tree_node *left_child;
struct tree_node *right_child;
};
Traversal
of Binary Trees
·
Inorder
·
PreOrder
·
PostOrder
·
With inorder
traversal the order is left-child, root node, right-child
·
With preorder
traversal the order is root node, left child , right child.
·
With postorder
traversal the order is left child, right child, root node.
InOrder:
void inorder(struct tree_node *p)
{
if (p !=NULL)
{
inorder(p->left_child);
printf(“%d\n”, p->data);
inorder(p->right_child);
}
}
PreOrder:
void preOrder(struct tree_node *p)
{
if (p !=NULL)
{
printf(“%d\n”, p->data);
preOrder(p->left_child);
preOrder(p->right_child);
}
}
PostOrder:
void postOrder(struct tree_node *p)
{
if (p !=NULL)
{
postOrder(p->left_child);
postOrder(p->right_child);
printf(“%d\n”, p->data);
}
}
Finding
Maximum value in a given tree p :
It’s a recursion function. Idea is to find
the maximum value between left sub tree, right sub tree and root.
Maximum Between 2 number :
Public int maximum(int a, int b)
{
return
(a>b?a:b) ;
}
int findMax (struct tree_node *p)
{
int node_data,
leftmax, rightmax, max;
max = -1
//assume all
values in the tree are positive integers
If (p != NULL)
{
node_data = p -> data;
leftmax =
findMax(p -> left_child);
rightmax = findMax(p->right_child);
//find the largest of the tree values.
max =
maximum((node_data,leftmax),rightmax)
}
return max;
}
Finding
sum of values of all the nodes of a tree:
To find the sum, add to the value of the
current node, the sum of values of all nodes of left subtree and the sum
of values of all nodes in right subtree.
Int sumOfAllNode(struct *p)
{
int sum =0;
if(p!=null)
{
sum = sum +
p->data + sumOfAllNode(p->right) +
sumOfAllNode(p->left);
}
return sum;
}
Depth Of a
Node :
The depth
of a node is the number of edges from the root node to node.
A root node will have a depth of 0.
A root node will have a depth of 0.
Heigh Of a
node :
The height
of a node is the logest number of edges from the node to a leaf.
A leaf node will have a height of 0.
A leaf node will have a height of 0.
Height
of a Binary Tree:
public int heightOfBinaryTree(Node node) {
if (node == null) {
return 0;
}
else {
return 1 + Math.max(heightOfBinaryTree(node.left),
heightOfBinaryTree(node.right));
}
}
Depth
Of a Node: (level of a node)
public int depthOfNode(Node node, int data,int depth) {
if (node == null) {
return 0;
}
else if(node.data == data)
return depth;
else {
return Math.max(DepthOfNode(node.left, depth + 1),
depthOfNode(node.right, depth + 1));
}
}
Complete Binary Tree:
It a special kind of binary tree.
Application of trees:
·
Class hierarchy in
Java
·
File system
·
Storing hierarchies
in organizations
