Scribd
Upload
3 views14 pages

Lecture 07 - Trees

The document provides an overview of trees, including their properties, definitions, and types such as rooted and binary trees. It explains key terminologies like root, child, parent, and leaf, as well as concepts like path length and tree height. Additionally, it includes exercises related to identifying tree components and constructing binary expression trees.

Uploaded by

dreamy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views14 pages

Lecture 07 - Trees

The document provides an overview of trees, including their properties, definitions, and types such as rooted and binary trees. It explains key terminologies like root, child, parent, and leaf, as well as concepts like path length and tree height. Additionally, it includes exercises related to identifying tree components and constructing binary expression trees.

Uploaded by

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

Trees

Introduction to Trees

Tree is a discrete structure that represents hierarchical


relationships between individual elements or nodes.
Properties of Trees:
▪ There is only one path between each pair of vertices of a tree.
▪ If a graph G there is one and only one path between each pair of vertices G
is a tree.
▪ A tree T with n vertices has n-1 edges.
▪ A graph is a tree if and only if it a minimal connected.
Rooted Trees
If a directed tree has exactly one node or vertex called root whose
incoming degrees is 0 and all other vertices have incoming degree
one, then the tree is called rooted tree.
Path length of a Vertex
The path length of a vertex in a rooted tree is defined to be the number of
edges in the path from the root to the vertex.

The path length of node B is one.

The path length of node E is one.

The path length of node G is three.


Binary Trees
If the outdegree of every node is less than or equal to 2, in a
directed tree than the tree is called a binary tree.
Terminologies
▪ Root: A binary tree has a unique node called the root of the tree.
▪ Left Child: The node to the left of the root is called its left child.
▪ Right Child: The node to the right of the root is called its right child.
▪ Parent: A node having a left child or right child or both are called the parent
of the nodes.
▪ Siblings: Two nodes having the same parent are called siblings.
▪ Leaf: A node with no children is called a leaf. The number of leaves in a
binary tree can vary from one (minimum) to half the number of vertices
(maximum) in a tree.
Terminologies

Left child of P Right child of P


Terminologies
▪ Depth or Height of a tree: The depth or height of a tree is defined as the
maximum number of nodes in a branch of a tree.
▪ Level of a Node: The level of a node is its distance from the root. The level
of root is defined as zero. The level of all other nodes is one more than its
parent node.

Level 0

Level 1

Level 2
Exercise

a) Which node is the root?


b) Which nodes are leaves?
c) What is the height of the tree?
d) Name the parent node of each node.
e) How many levels are there?
Binary Expression Trees

An algebraic expression can be conveniently expressed by its expression


tree. An expression having binary operators can be decomposed into

<left operand or expression> (operator) <right operand or expression>


Example
▪ Construct the binary expression tree for the expression 3 + ((5+9)*2).
Exercise
▪ Construct the binary expressions for the following trees.

a) b)

c)
Exercise

▪ Construct the binary expression trees for the following expressions.


i. 10 * 3
ii. (a/b) + c
iii. 3*((7+5)/2)
iv. (A OR B) AND (C OR D)

You might also like