Rooted tree, Data Structure & Algorithms

Assignment Help:

It does not have any cycles (circuits, or closed paths), which would imply the existence of more than one path among two nodes. It is the most general kind of tree, and might be converted in the more familiar form though designating a node as the root. We can represent a tree like a construction containing nodes, and edges that represent a relationship among two nodes. In Figure, we will assume most common tree called rooted tree. A rooted tress has a single root node that has no parents.

349_rooted tree.png

Figure: A rooted tree

In more formal way, we can define tree T like a finite set of one or more nodes such that there is one designated node r called as the root of T, and the remaining nodes into (T - { r } ) are partitioned in n > 0 disjoint subsets T1, T2, ..., Tk  each of is a tree, and whose roots r1 , r2 , ..., rk , respectively, are children of r. The general tree is a generic tree which has one root node, and each node in the tree can have limitless number of child nodes. One popular employ of this kind of tree is a Family Tree.

A tree is an example of a more general category called graph.

  • A tree contains nodes connected by edges.
  • A root is node without parent.
  • Leaves are nodes having no children.
  • The root is at level 1. The child nodes of root are at level 2. The child nodes of nodes at level 2 are at level 3 and so forth.
  • The depth (height) of any Binary tree is equivalent to the number of levels in it.
  • Branching factor describe the maximum number of children to any node. Thus, a branching factor of 2 means a binary tree.
  • Breadth described the number of nodes at a level.
  • In a tree the depth of a node M is the length of the path from the root of the tree to M.
  • In a Binary tree a node has at most 2 children. The given are the properties of a Tree.

Full Tree: A tree having all the leaves at the similar level, and all the non-leaves having the similar degree

  • Level h of a full tree contains dh-1 nodes.
  • The first h levels of full tree have 1 + d + d2 + d3 + d4 + ....... + dh-1 = (dh -1)/(d - 1) nodes where d refer to the degree of nodes.
  • The number of edges = the number of nodes - 1 (Why? Because, an edge represents the relationship among a child & a parent, and every node has a parent except the root.
  • A tree of height h & degree d has at most d h - 1 element.

Related Discussions:- Rooted tree

Explain the theory of computational complexity, Explain the theory of compu...

Explain the theory of computational complexity A  problem's  intractability  remains  the  similar  for  all  principal  models  of   computations    and   all reasonable inpu

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Determine about the post conditions assertion, Determine about the Post con...

Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

Define big omega notation, Define Big Omega notation Big Omega notatio...

Define Big Omega notation Big Omega notation (?) : The lower bound for the function 'f' is given by the big omega notation (?). Considering 'g' to be a function from the non-n

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Bubble sort, Q. The reason bubble sort algorithm is inefficient is that it ...

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

The best average behaviour, The best average behaviour is shown by  Qui...

The best average behaviour is shown by  Quick Sort

Singly linked list , The two pointers per number of a doubly linked list pr...

The two pointers per number of a doubly linked list prepare programming quite easy. Singly linked lists as like the lean sisters of doubly linked lists. We need SItem to consider t

Write Your Message!

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd