JavaGian java tutorial and java interview question and answer

JavaGian , Free Online Tutorials, JavaGian provides tutorials and interview questions of all technology like java tutorial, android, java frameworks, javascript, ajax, core java, sql, python, php, c language etc. for beginners and professionals.

Data-Structure Tree Explain Tree?

Explain Tree?

in ,

Tree

  • A Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.
  • The nodes other than the root node are partitioned into the non empty sets where each one of them is to be called sub-tree.
  • Nodes of a tree either maintain a parent-child relationship between them or they are sister nodes.
  • In a general tree, A node can have any number of children nodes but it can have only a single parent.
  • The following image shows a tree, where the node A is the root node of the tree while the other nodes can be seen as the children of A.

Tree 

Basic terminology

  • Root Node :- The root node is the topmost node in the tree hierarchy. In other words, the root node is the one which doesn't have any parent.
  • Sub Tree :- If the root node is not null, the tree T1, T2 and T3 is called sub-trees of the root node.
  • Leaf Node :- The node of tree, which doesn't have any child node, is called leaf node. Leaf node is the bottom most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
  • Path :- The sequence of consecutive edges is called path. In the tree shown in the above image, path to the node E is A→ B → E.
  • Ancestor node :- An ancestor of a node is any predecessor node on a path from root to that node. The root node doesn't have any ancestors. In the tree shown in the above image, the node F have the ancestors, B and A.
  • Degree :- Degree of a node is equal to number of children, a node have. In the tree shown in the above image, the degree of node B is 2. Degree of a leaf node is always 0 while in a complete binary tree, degree of each node is equal to 2.
  • Level Number :- Each node of the tree is assigned a level number in such a way that each node is present at one level higher than its parent. Root node of the tree is always present at level 0.

Static representation of tree

  1. #define MAXNODE 500  
  2. struct treenode {  
  3.     int root;  
  4.     int father;  
  5.     int son;  
  6.     int next;   
  7. }   

Dynamic representation of tree

  1. struct treenode   
  2. {  
  3.     int root;  
  4.     struct treenode *father;   
  5.     struct treenode *son   
  6.     struct treenode *next;   
  7. }  

Types of Tree

The tree data structure can be classified into six different categories.

Tree

General Tree

General Tree stores the elements in a hierarchical order in which the top level element is always present at level 0 as the root element. All the nodes except the root node are present at number of levels. The nodes which are present on the same level are called siblings while the nodes which are present on the different levels exhibit the parent-child relationship among them. A node may contain any number of sub-trees. The tree in which each node contain 3 sub-tree, is called ternary tree.

Forests

Forest can be defined as the set of disjoint trees which can be obtained by deleting the root node and the edges which connects root node to the first level node.

Tree 

Binary Tree

Binary tree is a data structure in which each node can have at most 2 children. The node present at the top most level is called the root node. A node with the 0 children is called leaf node. Binary Trees are used in the applications like expression evaluation and many more. We will discuss binary tree in detail, later in this tutorial.

Binary Search Tree

Binary search tree is an ordered binary tree. All the elements in the left sub-tree are less than the root while elements present in the right sub-tree are greater than or equal to the root node element. Binary search trees are used in most of the applications of computer science domain like searching, sorting, etc.

Expression Tree

Expression trees are used to evaluate the simple arithmetic expressions. Expression tree is basically a binary tree where internal nodes are represented by operators while the leaf nodes are represented by operands. Expression trees are widely used to solve algebraic expressions like (a+b)*(a-b). Consider the following example.
Q. Construct an expression tree by using the following algebraic expression.
(a + b) / (a*b - c) + d

Tree 

Tournament Tree

Tournament tree are used to record the winner of the match in each round being played between two players. Tournament tree can also be called as selection tree or winner tree. External nodes represent the players among which a match is being played while the internal nodes represent the winner of the match played. At the top most level, the winner of the tournament is present as the root node of the tree.
For example, tree .of a chess tournament being played among 4 players is shown as follows. However, the winner in the left sub-tree will play against the winner of right sub-tree.

Labels: ,

.