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

Non-recursive algorithm to traverse a tree in preorder, Write the non-recur...

Write the non-recursive algorithm to traverse a tree in preorder.    The Non- Recursive algorithm for preorder traversal is as follows: Initially  push NULL onto stack and

Java, Ask consider the file name cars.text each line in the file contains i...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Explain the concept of hidden lines and surface removal, Explain the concep...

Explain the concept of hidden lines The problem of hidden lines or surfaces was implicit even in 2-D graphics, but we did not mention it there, because what was intended to be

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Define approximating smooth surfaces with polygon nets, Approximating smoot...

Approximating smooth surfaces with Polygon nets Networks of polygons are used to represent smooth surfaces. They are, of course, only an approximation to the true surface, but

Program, What is a first-in-first-out data structure ? Write algorithms to...

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Program to manipulate the data structure, Data Structure and Methods: ...

Data Structure and Methods: Build an array structure to accomodate at least 10 elements. Provide routines for the following: An initializer. A routine to populate (

Traversing a binary search tree, Binary Search Tree let three types of trav...

Binary Search Tree let three types of traversals by its nodes. They are: Pre Order Traversal In Order Traversal Post Order Traversal In Pre Order Traversal, we ca

Breadth-first search, Breadth-first search starts at a given vertex h, whic...

Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go to all the vertices that are at the distance of one edge away. When we go there, we

Data structure for representing numbers, Your first task will be to come up...

Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative

Write Your Message!

Captcha
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