Scribd
Upload
13 views21 pages

CH 7

Chapter 7 discusses the concept of trees in graph theory, defining a tree as a connected, undirected, acyclic graph and introducing related terms such as rooted trees, leaves, and internal nodes. It outlines properties of trees, including the relationship between vertices and edges, and describes various tree traversal methods: pre-order, in-order, and post-order. Additionally, the chapter explains how arithmetic expressions can be represented as rooted trees and provides examples of infix, prefix, and postfix notations.

Uploaded by

munshijubair7
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
13 views21 pages

CH 7

Chapter 7 discusses the concept of trees in graph theory, defining a tree as a connected, undirected, acyclic graph and introducing related terms such as rooted trees, leaves, and internal nodes. It outlines properties of trees, including the relationship between vertices and edges, and describes various tree traversal methods: pre-order, in-order, and post-order. Additionally, the chapter explains how arithmetic expressions can be represented as rooted trees and provides examples of infix, prefix, and postfix notations.

Uploaded by

munshijubair7
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/ 21

10-Nov-2024

Chapter 7
Trees
Definition

► A tree is a connected undirected acyclic (with no cycle)


simple graph
► A collection of trees is called forest.
Theorem

1. An undirected graph is a tree iff there is a unique


simple path between any two vertices.

2. A simple graph G = (V, E) is a tree iff |E| = |V| - 1


Definition

► A rooted tree is a tree in which one vertex is specified


as the root & every edge is drawn away from the root

root
root
Definition

root Level 0

Level 1
parent
Height=3
Level 2
vertex

Level 3
children
Definition

► Root: a vertex with no parent


► Leaf: a vertex with no children
► Internal node: vertex with children
► Descendants: all children and children of
children
► Ancestors: parent and parents of parents
► Siblings: vertices with the same parent
► Height = number of levels - 1
Definition

► An m-ary tree is a rooted tree where the number of


children of any internal vertex ≤ m
► A full m-ary tree is an m-ary tree where the number of
children of any internal vertex = m

► if m=2, we call it binary tree


3-ary tree Full 3-ary tree
Definition

► In an ordered rooted tree the children are ordered.


► For example, in an ordered binary tree, a vertex may
have left child and right child

root

Left child Right child

Left child Right child


Properties

► Any tree of size n has n-1 edges

► Any full m-ary tree with i internal vertices has m i + 1 vertices

► Any m-ary tree with height h has at most mh leaves.


Properties

A full m-ary tree with


► n vertices has i =(n-1)/m internal
and
l = ((m-1)n+1)/m leaves . Notice that
n=l+i
► i internal has n=mi+1 vertices and
l= (m-1)i+1 leaves
► l leaves has n=(ml -1)/(m-1)
Tree Traversal
Tree Traversal

► Away for visiting ordered rooted trees


Pre-order

► Visit x, T1 in preorder, T2 in preorder, T3 in preorder


....and so on

T T T T
1 2 3 4
In-order

► Visit T1 in inorder, x, T2 in inorder, T3 in inorder


....and so on

T T T T
1 2 3 4
Post-order

► Visit T1 in post-order, T2 in post-order, T3 in post-order


.... etc, and then x.

T T T T
1 2 3 4
Pre-order : a b e f g h i j c d
In-order : e b f h g i j a c d
Post-order : e f h i j g b c d a
Example

a
► Pre-order:
a, b, e, f, g, h, i, j, c, d
b c d
► In-order:
e, b, f, h, g, i, j, a, c, d
e g
f
► Post-order:
e, f, h, i, j, g, b, c, d, a

h i j
Tree that represents
expressions
► Any arithmetic expression can be represented by a
rooted tree

► (x+1)^2-(3/2)

^ /

+ 2 3 2

x 1
Ambiguous expressions

x+y*z
= (x + y) * z ?
= x + (y * z) ?

► Parentheses have to be used to avoid ambiguity


Infix, prefix, & postfix

Any arithmetic expression can be written in an unambiguous form


► Prefix form: an pre-order traversal of the expression’s rooted tree
► Infix form: an in-order traversal of the expression’s rooted tree
► Postfix form: an post-order traversal of the expression’s rooted tree
Example

► Consider the expression (x+1)^2-(3/2)


► Infix form: x+1^2-3/2
► Prefix: -^+x12/32 -
► Postfix: x1+2^32/-
^ /

+ 2 3 2

x 1

You might also like