 Want to join our mediation workshop that helps you to study better?

The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
See Our team
Wondering how we keep quality?
Got unsolved questions?

You are here:Open notes-->VTU-->Data-structure-with-C-10CS35-unit-5

# UNIT - 5 TREES � 1

5.1 Introduction

A tree is a finite set of one or more nodes such that: (i) there is a specially designated node called the root;

(ii) the remaining nodes are partitioned into n 0 disjoint sets T1, ...,Tn where each of these sets is a tree. T1, ...,Tn are called the subtrees of the root. A tree structure means that the data is organized so that items of information are related by branches. One very common place where such a structure arises is in the investigation of genealogies.

AbstractDataType

tree{

instances

A set of elements:

(1) empty or having a distinguished root element

(2) each non-root element having exactly one parent element operations

root()

degree()

child(k)

}

Some basic terminology for trees:

 Trees are formed from nodes and edges. Nodes are sometimes called vertices. Edges are sometimes called branches.

 Nodes may have a number of properties including value and label.

 Edges are used to relate nodes to each other. In a tree, this relation is called "parenthood."

 An edge {a,b} between nodes a and b establishes a as the parent of b. Also, b is called a child.

Although edges are usually drawn as simple lines, they are really directed from parent to child. In tree drawings, this is top-to-bottom.

Informal Definition: a tree is a collection of nodes, one of which is distinguished as "root," along with a relation ("parenthood") that is shown by edges.

Formal Definition: This definition is "recursive" in that it defines tree in terms of itself. The definition is also "constructive" in that it describes how to construct a tree.

1. A single node is a tree. It is "root."

2. Suppose N is a node and T1, T2, ..., Tk are trees with roots n1, n2, ...,nk, respectively. We can construct a new tree T by making N the parent of the nodes n1, n2, ..., nk. Then, N is the root of T and T1, T2, ..., Tk are subtrees.

More terminology

 A node is either internal or it is a leaf.

 A leaf is a node that has no children.

 Every node in a tree (except root) has exactly one parent.

 The degree of a node is the number of children it has.

 The degree of a tree is the maximum degree of all of its nodes.

• Children of the same parent are called Siblings

Paths and Levels

Definition: A path is a sequence of nodes n1, n2, ..., nk such that node ni is the parent of node ni+1 for all 1

<= i <= k.

Definition: The length of a path is the number of edges on the path (one less than the number of nodes).

Definition: The descendents of a node are all the nodes that are on some path from the node to any leaf.

Definition: The ancestors of a node are all the nodes that are on the path from the node to the root.

Definition: The depth of a node is the length of the path from root to the node. The depth of a node is

sometimes called its level.

Definition: The height of a node is the length of the longest path from the node to a leaf.

Definition: the height of a tree is the height of its root.

5.2 Binary Trees

Definition: A binary tree is a tree in which each node has degree of exactly 2 and the children of each node are distinguished as "left" and "right." Some of the children of a node may be empty.

Formal Definition: A binary tree is:

1. either empty, or

2. it is a node that has a left and a right subtree, each of which is a binary tree.

Definition: A full binary tree (FBT) is a binary tree in which each node has exactly 2 non-empty children or exactly two empty children, and all the leaves are on the same level. (Note that this definition differs from the text definition).

Definition: A complete binary tree (CBT) is a FBT except, perhaps, that the deepest level may not be completely filled. If not completely filled, it is filled from left-to-right. A FBT is a CBT, but not vice-versa.

5.3 Binary Tree Traversals

There are many operations that we often want to perform on trees. One notion that arises frequently is the idea of traversing a tree or visiting each node in the tree exactly once. A full traversal produces a linear order for the information in a tree. This linear order may be familiar and useful. When traversing a binary tree we want to treat each node and its subtrees in the same fashion. If we let L, D, R stand for moving left, printing the data, and moving right when at a node then there are six possible combinations of traversal: LDR, LRD, DLR, DRL, RDL, and RLD. If we adopt the convention that we traverse left before right then only three traversals remain: LDR, LRD and DLR. To these we assign the names inorder, postorder and preorder because there is a natural correspondence between these traversals and producing the infix, postfix and prefix forms of an expression. We also have Level Order Traversal.

x := root()

if( x ) queue (x)

while( queue not empty ){

x := dequeue()

visit()

i=1; while( i <= degree() ){

queue( child(i) )

}

}

Preorder

procedure preorder(x){

visit(x)

i=1; while( i <= degree() ){

preorder( child(i) )

}

}

Postorder

procedure postorder(x){

i=1; while( i <= degree() ){

postorder( child(i) )

}

visit(x)

}

Inorder

Meaningful just for binary trees.

procedure inorder(x){

if( left_child_for(x) ) { inorder( left_child(x) ) }

visit(x)

if( right_child_for(x) ) { inorder( right_child(x) ) }

}

Level order

x := root()
if( x ) queue (x)
while( queue not empty ){
x := dequeue()
visit()
i=1; while( i <= degree() )
{
queue( child(i))
}

If we look carefully at the linked representation of any binary tree, we notice that there are more null links than actual pointers. As we saw before, there are n + 1 null links and 2n total links. A clever way to make use of these null links has been devised by A. J. Perlis and C. Thornton. Their idea is to replace the null links by pointers, called threads, to other nodes in the tree. If the RCHILD(P) is normally equal to zero, we will replace it by a pointer to the node which would be printed after P when traversing the tree in inorder. A null LCHILD link at node P is replaced by a pointer to the node which immediately precedes node P in inorder. The tree T has 9 nodes and 10 null links which have been replaced by threads. If we traverse T in inorder the nodes will be visited in the order H D I B E A F C G. For example node E has a predecessor thread which points to B and a successor thread which points to A. In the memory representation we must be able to distinguish between threads and normal pointers. This is done by adding two extra one bit fields LBIT and RBIT.

LBIT(P) =1 if LCHILD(P) is a normal pointer

LBIT(P) = 0 if LCHILD(P) is a thread

RBIT(P) = 1 if RCHILD(P) is a normal pointer

RBIT(P) = 0 if RCHILD(P) is a thread

5.5 Heaps.

A heap is a complete tree with an ordering-relation R holding between each node and its descendant. Examples for R: smaller-than, bigger-than

Assumption: In what follows, R is the relation ‗bigger-than�, and the trees have degree 2.

1. Add a node to the tree

2. Move the elements in the path from the root to the new node one position down, if they are smaller than the new element

3. Insert the new element to the vacant node

4. A complete tree of n nodes has depth log n , hence the time complexity is O(log n)

Deleting an Element

1. Delete the value from the root node, and delete the last node while saving its value.

2. As long as the saved value is smaller than a child of the vacant node, move up into the vacant node the largest value of the children.

3. Insert the saved value into the vacant node

4. The time complexity is O(log n)

Initialization:

Brute Force

Given a sequence of n values e1, ..., en, repeatedly use the insertion module on the n given values.

 Level h in a complete tree has at most 2h-1 = O(2n) elements

 Levels 1, ..., h - 1 have 20 + 21 + + 2h-2 = O(2h) elements

 Each element requires O(log n) time. Hence, brute force initialization requires O(n log n) time.

Efficient

Insert the n elements e1, ..., en into a complete tree For each node, starting from the last one and ending at the root, reorganize into a heap the subtree whose root node is given. The reorganization is performed by interchanging the new element with the child of greater value, until the new element is greater than its children.

manjarimattur

## Tool box

Edit this note | Upvote | Down vote | Questions

### Watch more videos from this user Here

Learn how to upload a video over here