ceng2001_week9

Trees and Tree Algorithms
Data Structures and Algorithms

Week 9
Erdem Türk, PhD

Fall 2024
Tree example: Taxonomy of some
animals
All Life
Click
Unix directory structure (top)
<html xmlns="http://www.w3.org/1999/xhtml"
xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=utf-8" />
<title>simple</title>
</head>
<body>
<h1>A simple web page</h1>
<ul>
<li>List item one</li>
<li>List item two</li>
</ul>
<h2><a href="http://www.cs.luther.edu">Luther CS </a><h2>
</body>
</html>
Web site HTML

Terminology
a
x k
Node:
z r
A node is a fundamental part of a tree. It
can have a name, which we call the “key.”
A node may also have additional

information. We call this additional
information the “payload.” While the
payload information is not central to many
tree algorithms, it is often critical in
applications that make use of trees.
Terminology
Edge:
An edge is another fundamental part of a

tree.
An edge connects two nodes to show that
there is a relationship between them.
Every node (except the root) is connected

by exactly one incoming edge from
another node. Each node may have several
outgoing edges.
Terminology
Root:
The root of the tree is the only node in the
tree that has no incoming edges.
Terminology
a
x k
Path:
z r
A path is an ordered list of nodes that are
connected by edges.
For example the path a > x > r is the way

from the root node a to the node r in the
tree to the left
Terminology
a
x k
Children:
z r
The set of nodes c that have incoming
edges from the same node to are said to
be the children of that node.
For example the children of node x in the

tree to left are z and r
Terminology
a
x k
Parent:
z r
A node is the parent of all the nodes it
connects to with outgoing edges.
To left, the parent of z and r is x, also note

that x is a child of a and a is a parent of x
Terminology
a
x k
Sibling:
z r
Nodes in the tree that are children of the
same parent are said to be siblings.
The nodes z and r are siblings in the tree

to the left
Terminology
a
x k
Subtree:
z r A subtree is a set of nodes and edges
comprised of a parent and all the
descendants of that parent.
A subtree can be a part of a bigger tree.
In the tree to the left x, z, and r form one

subtree.
Note that k is also a subtree by itself.

Terminology
a
x k
Leaf Node
z r
A leaf node is a node that has no children.
All the leaf nodes of the tree to the left are

z, r and k.
Terminology
Level:
a
0 Level
1 x k The level of a node n is the number
of edges on the path from the root
2 z r
node to n.
Height:
The height of a tree is equal to the

maximum level of any node in the
tree.
The height of the tree to left is 2
Definition one of a tree:
A tree consists of a set of nodes and a set of edges
that connect pairs of nodes. A tree has the
following properties:
1. One node of the tree is designated as the root

node.
2. Every node n, except the root node, is
connected by an edge from exactly one other
node p, where p is the parent of n.
3. A unique path traverses from the root to each
node.
4. If each node in the tree has a maximum of two
children, we say that the tree is a binary tree.
This illustrates a tree
that fits definition
one. The arrowheads
on the edges
indicate the direction
of the connection.
Recursive Definition of a tree:
1. A tree is either empty or consists of a root
and zero or more subtrees, each of which is
also a tree.
2. The root of each subtree is connected to the
root of the parent tree by an edge.
This figure illustrates this recursive definition
of a tree.
Using the recursive definition of a tree, we
know that the tree in this figure
has at least four nodes, since
each of the triangles representing
a subtree must have a root.
It may have many
more nodes than
that, but we do
not know unless we
look deeper into
the tree.
There are many ways to represent
a tree in a
diagram:http://en.wikipedia.org/wiki/Tree_structure#Represe
nting_trees
• node link diagrams

• Nested Sets
• Layered "icicle" diagrams
• outline
• Nested parentheses
• Radial Trees
Tree Implementations in Python
Binary List implementation of a tree
Recursive view: [ key, left subtree, right subtree ]
Each tree or sub tree (t) consist of a list
with three elements:
t[0] is the node key
t[1] is the left sub tree or [] for no child
on left
t[2] is the right sub tree or [] for no child
on right
Example
t = ["a",
["b", # a left
["d", [], []], # b left
["e", [], []] # b right
],
["c", [], []] # a right
]
or ['a', ['b', ['d', [], []], ['e', [], []]], ['c', [], []]]
functions to work with tree list
def Bintree(r): return [r, [], []]
def insertLeft(root, newBranch):

t = root[1] # get current left
root[1] = [newBranch, t, []]
return root
def insertRight(root,newBranch):
t = root[2] # get current right
root[2] = [newBranch, [], t]
return root
def getRootVal(root): return root[0]
def setRootVal(root,newVal): root[0] = newVal
def getLeftChild(root): return root[1]
def getRightChild(root): return root[2]

def insertLeft(root, newBranch):
t = root[1] # get current left
root[1] = [newBranch, t, []]
return root
1
1
5 2
t = Bintree(1)
insertLeft(t,5)
insertRight(t,2)
insertLeft(getRightChild(t),9)
Implement as linked structure in Class
class BinaryTree: def getRightChild(self): return self.rightChild
def __init__(self,rootObj):
self.key = rootObj def getLeftChild(self): return self.leftChild
self.leftChild = None
self.rightChild = None def setRootVal(self,obj): self.key = obj
def insertLeft(self,newNode): def getRootVal(self): return self.key

oldLeft = self.leftChild
self.leftChild = BinaryTree(newNode)
self.leftChild.leftChild = oldLeft
def insertRight(self,newNode):
oldright = self.rightChild
self.rightChild = BinaryTree(newNode)
self.rightChild.rightChild = oldright
do this
How to do it:
# a
# / \
# b c
# \ / \
# d e f
r = BinaryTree('a')
r.insertLeft('b')
r.getLeftChild().insertRight('d')
r.insertRight('f')
r.insertRight('c')
r.getRightChild().insertLeft('e')
Parse Tree
You can use parse tree for structured
languages like english or math
Figure 2:
Parse Tree for ((7+3)∗(5−2))
doing math expression parse tree:
In the rest of this section we are
going to examine parse trees in
more detail. In particular we will
look at
• How to build a parse tree from a

fully parenthesized
mathematical expression.
• How to evaluate the expression
stored in a parse tree.
• How to recover the original
A Simplified Parse Tree for mathematical expression from a
((7+3)∗(5−2)) parse tree.
Breaking into tokens
• We will be input fully parenthesized
expressions
• We need to break it into the following tokens:
1. Left parentheses: (
2. or right parentheses: )
3. operators: + - * /
4. operands: a number such as 109
What we know if
we examine some trees
• A left ( will mark a new tree
• A right ) will mark the finish of
and operand – operator - operand
• The leafs of the tree will be operands
• The parent of two leaf operands will be a
operator
• a subtree will be a operand for a parent
operator
Using the information from above we can define four rules
as follows:
1. If the current token is a '(', add a new node as the left

child of the current node, and descend to the left child.
2. If the current token is in the list ['+','-','/','*'], set the
root value of the current node to the operator
represented by the current token. Add a new node as
the right child of the current node and descend to the
right child.
3. If the current token is a number, set the root value of
the current node to the number and return to the
parent.
4. If the current token is a ')', go to the parent of the
current node.
Examine step by step operation
for this expression parsed into tokens:
['(', '3', '+', '(', '4', '*', '5' ,')',')']
or as an list
( 3 + ( 4 * 5 ) )
Now let's follow the rules one token at a time

( 3 + ( 4 * 5 ) )
^
Start, create an empty tree, with one node
If the current token is a '(', add a new node as the left child of
the current node, and descend to the left child.
1
( 3 + ( 4 * 5 ) )
^
If the current token is a number, set the root value of the current
node to the number and return to the parent.
2
( 3 + ( 4 * 5 ) )
^
If the current token is in the list ['+','-','/','*'], set the root value of
the current node to the operator represented by the current
token. Add a new node as the right child of the current node and
descend to the right child.
3
( 3 + ( 4 * 5 ) )
^
If the current token is a '(', add a new node as the left child of
the current node, and descend to the left child.
4
( 3 + ( 4 * 5 ) )
^
6
( 3 + ( 4 * 5 ) )
^
7
( 3 + ( 4 * 5 ) )
^
If the current token is in the list ['+','-','/','*'], set the root value of
the current node to the operator represented by the current
token. Add a new node as the right child of the current node and
descend to the right child.
8
( 3 + ( 4 * 5 ) )
If the current token is a ')', go to the parent of the current node.

We apply this rule for the last two ) tokens and we end up with
this
3 *
4 5
9-10
Check out the code for building Parse tree
evaluate it, recall we can replace
subtrees with the result as shown:
30
Evaluation: how to recurse
• base case, look for both children being a leaf
( leaf is a node that has no children)
For leaf, we just return the value
• For other non leaf nodes, we need to perform
the operator on the two child subtree values
user of operator python module
• Note we are going to use the operator module
to access the methods for add, subtract (sub),
multiply (mul) and divide (truediv), and
because functions can be stored in variables,
we will store the correct function in a
dictionary that maps the token to the correct
operator python function
opers = {
'+':operator.add, '-':operator.sub,
'*':operator.mul, '/':operator.truediv}
Check out the code for evaluation of parse tree
Tree Traversal
Way to visit all the nodes in Tree
• There are three systematic ways to visit all the
nodes of a binary tree:
1. preorder – root > left > right
2. inorder – left > root > right
3. postorder – left > right > root
Remember math expressions
• this is similar to math expressions we already
covered
• prefix, infix, and postfix expressions
• It exactly corresponds to these terms if we are
looking a an expression tree structure
+
1 2
+ 1 2 is a prefix visit nodes +
expression + then 1 then 2
is preorder 1 2
1 + 2 is a infix visit nodes +

expression 1 then + then 2
is inorder 1 2
1 2 + is a postfix visit nodes +

expression 1 then 2 then +
is postorder 1 2
applying each traversal to a bigger tree
• The previous slide show you the order for each kind of
traversal, if the child is a sub tree, it is traversed in the
same way.
• We will show you the code for each kind of traversal in
the next slides
• Keep in mind that we will be doing something with
each node when we traverse. In the cases that follow
we will just be printing them as we traverse them
• But in other problems you may be doing something
else like searching, summing, or something else
depending on the problem.
Two ways to write the code
def preorder(tree):
if tree: # do nothing if from leaf as function
print(tree.getRootVal())
preorder(tree.getLeftChild())
outside
preorder(tree.getRightChild()) of Tree class
def preorder(self):
print(self.key)
as method
if self.leftChild: # do if not leaf
self.left.preorder() inside
if self.rightChild: # do if not leaf of Tree class
self.right.preorder()
preorder sample
root > left child > right child
numbers show
the order 1
of traversal
visits
2 7
3 4 8
5 6
inorder sample
left child > root > right child
numbers show
the order 6
of traversal
visits
2 7
1 4 8
3 5
postorder sample
left child > right child > root
numbers show
the order 8
of traversal
visits
5 7
1 4 6
2 3
postorder traversal code
def postorder(tree):
if tree != None: # do nothing if from leaf
postorder(tree.getLeftChild())
postorder(tree.getRightChild())
use postorder to eval expression tree
opers = { '+':operator.add, '-':operator.sub,

'*':operator.mul, '/':operator.truediv }
def postordereval(tree):
if tree:
left= postordereval(tree.getLeftChild())
right= postordereval(tree.getRightChild())
if left and right: # do if not leaf
return opers[ tree.getRootVal()] (left, right)
else: # else this is a leaf, return value
return tree.getRootVal()
inorder
def inorder(tree):
if tree != None:
inorder(tree.getLeftChild())
inorder(tree.getRightChild())
expression tree as string
• This returns the expression from the
expression tree as a string
def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal

ceng2001_week9

Uploaded by

Copyright:

Available Formats

ceng2001_week9

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ceng2001_week9

Uploaded by

Copyright:

Available Formats

Trees and Tree Algorithms

Data Structures and Algorithms

Erdem Türk, PhD

Web site HTML

A node may also have additional

An edge is another fundamental part of a

Every node (except the root) is connected

For example the path a > x > r is the way

For example the children of node x in the

To left, the parent of z and r is x, also note

The nodes z and r are siblings in the tree

A subtree can be a part of a bigger tree.

In the tree to the left x, z, and r form one

Note that k is also a subtree by itself.

All the leaf nodes of the tree to the left are

The height of a tree is equal to the

1. One node of the tree is designated as the root

• node link diagrams

def insertLeft(root, newBranch):

def getRootVal(root): return root[0]

def setRootVal(root,newVal): root[0] = newVal

def getLeftChild(root): return root[1]

def getRightChild(root): return root[2]

def insertLeft(self,newNode): def getRootVal(self): return self.key

• How to build a parse tree from a

1. If the current token is a '(', add a new node as the left

Now let's follow the rules one token at a time

If the current token is a ')', go to the parent of the current node.

1 + 2 is a infix visit nodes +

1 2 + is a postfix visit nodes +

opers = { '+':operator.add, '-':operator.sub,

You might also like