24-01-2013, 02:33 PM
Trees
Trees.ppt (Size: 1.11 MB / Downloads: 22)
Introduction
we have seen sequential and linked representation of linear data structure, array, stack, queue falls in this category.
This chapter defines nonlinear data structure called a tree.
This structure is mainly used to represent data containing a hierarchical relationship between elements, eg., records, family trees and table of contents.
Binary Tree
Binary tree is a special type of tree in which every node or vertex has either no children or one children or two children.
A binary tree is an important class of tree data structure in which a node can have at most two children.
Child of a node in binary tree on left is called “left subtree” and node on right is called “right subtree”.
Application of binary tree
Binary trees are used to represent non linear data structure.
Binary trees plays virtual role in software application.
One of the best application of binary tree is in the searching algorithm.
Binary trees are used in decision making, artificial intelligence, compilers, expression evaluation etc.
Tree terminology
Node – a node stands for item of information & branches to other node.
Root –
1)It is starting node to use or go through the binary tree.
2)This is the important node of any tree.
3)This node does not have parent.
4)It is the first node in hierarchical arrangement.
Array Representation
Note – the previous formula will work only for almost complete binary tree or complete binary tree. Any binary tree can be converted to almost complete binary tree by showing dummy nodes.
Linked List Representation
The node structure of linked list has 3 parts:
Data: It stores the information of the node of the tree
Left child: Pointer to the left child
Right child: Pointer to the right child