Scribd
Upload
37 views

Introduction To Trees

The document provides definitions and examples of different types of trees including binary trees, labeled trees, unlabeled trees, rooted trees, binary search trees, spanning trees, and minimum spanning trees.

Uploaded by

Ahmad Akhtar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
37 views

Introduction To Trees

The document provides definitions and examples of different types of trees including binary trees, labeled trees, unlabeled trees, rooted trees, binary search trees, spanning trees, and minimum spanning trees.

Uploaded by

Ahmad Akhtar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

Introduction to Trees

Tree is a discrete structure that represents hierarchical relationships between individual


elements or nodes. A tree in which a parent has no more than two children is called a binary
tree.

Definition − A Tree is a connected acyclic undirected graph. There is a unique path between
every pair of vertices in G. A tree with N number of vertices contains (N−1) number of edges.
The vertex which is of 0 degree is called root of the tree. The vertex which is of 1 degree is
called leaf node of the tree and the degree of an internal node is at least 2.

Example − The following is an example of a tree −

Labeled Trees
Definition − A labeled tree is a tree the vertices of which are assigned unique numbers from 1
to n. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding
points of the two trees have the same labels.
Example

Unlabeled Trees
Definition − An unlabeled tree is a tree the vertices of which are not assigned any numbers.
Example

Rooted Tree
A rooted tree G is a connected acyclic graph with a special node that is called the root of the
tree and every edge directly or indirectly originates from the root. An ordered rooted tree is a
rooted tree where the children of each internal vertex are ordered. If every internal vertex of a
rooted tree has not more than m children. If every internal vertex of a rooted tree has exactly m
children, it is called a full m-ary tree. If m=2, the rooted tree is called a binary tree.
Binary Search Tree

Binary Search tree is a binary tree which satisfies the following property −

 X in left sub-tree of vertex V,Value(X)≤Value(V)


 Y in right sub-tree of vertex V,Value(Y)≥Value(V)
So, the value of all the vertices of the left sub-tree of an internal node V are less than or equal
to V and the value of all the vertices of the right sub-tree of the internal node V are greater than
or equal to V. The number of links from the root node to the deepest node is the height of the
Binary Search Tree.
Example
 Spanning Trees
A spanning tree of a connected undirected graph G is a tree that minimally includes all of the
vertices of G. A graph may have many spanning trees.

Example

Minimum Spanning Tree


A spanning tree with assigned weight less than or equal to the weight of every possible
spanning tree of a weighted, connected and undirected graph G it is called minimum spanning
tree (MST). The weight of a spanning tree is the sum of all the weights assigned to each edge of
the spanning tree.
Example

Solution

Here we start with the vertex ‘a’ and proceed.


This is the minimal spanning tree and its total weight is (1+2+3+5+9)=20

You might also like