Wednesday, 29 November 2017

Tree Data Structure

Define tree data structure?
A tree is a data structure, which represents hierarchical relationship between individual Data items.

Define child and parent of a tree.
The root of each subtree is said to be a child of 'r' and 'r' is the parent of each subtree root.

Define leaf noad in tree?
In a directed tree any node which has out degree o is called a terminal node or a leaf.

What is a Binary tree data structure?
A Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub trees.

What are the applications of binary tree data structure?
a. File index schemes
b. Hierarchical database management system.

What is meant by traversing?
Traversing a tree means processing it in such a way, that each node is visited only once.

What are the different types of traversing?
a. Pre-order traversal-yields prefix form of expression.
b. In-order traversal-yields infix form of expression.
c. Post-order traversal-yields postfix form of expression.

What are the two methods of binary tree implementation?
a. Linear representation.
b. Linked representation.

Define complete binary tree.
It is a complete binary tree only if all levels, except possibly the last level have the maximum number of nodes maximum. A complete binary tree of height 'h' has between 2h and 2h+1 – 1 node

Define binary search tree. Why it is preferred rather than the sorted linear array and linked list?
Binary search tree is a binary tree in which key values of the left sub trees are lesser than the root value and the key values of the right sub tree are always greater than the root value. In linear array or linked list the values are arranged in the form of increasing or decreasing order. If we want to access any element means, we have to traverse the entire list. But if we use Binary Search Tree, the element to be accessed is greater or smaller than the root element means we can traverse either the right or left sub tree and can access the element irrespective of searching the entire tree.

Give various implementations of trees data structure.
a. Linear implementation
b. Linked list implementation

List out the cases involved in deleting a node from a binary search tree.
Case 1: Node to be deleted is a Leaf node.
Case 2: Node to be deleted has one child.
Case:3: Node to be deleted has two children.

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput