TREE

CONTENTS

▪ The tree structure

▪ The binary tree
▪ Expression tree

Data Structures and Algorithms 2 FIT – HNUE 2021

 TREE STRUCTURE

Data Structures and Algorithms 3 FIT – HNUE 2020

 TREE STRUCTURE

• A tree structure consists of nodes and edges that organize data in a

hierarchical fashion(nonlinear fashion).
• The data elements are stored in nodes and pairs of nodes are
connected by edges.

Data Structures and Algorithms 4 FIT – HNUE 2021

 DEFINITION OF TREE

• a tree as a set of nodes that either is empty or has a node called the
root that is connected by edges to zero or more subtrees to form a
hierarchical structure. Each subtree is itself by definition a tree.

Data Structures and Algorithms 5 FIT – HNUE 2021

 TERMINOLOGY

• Root: The topmost node of the tree.

• Path: The nodes encountered when following the edges from a starting
node to a destination form a path.

Data Structures and Algorithms 6 FIT – HNUE 2021

 TERMINOLOGY

• Every node, except the root, has a parent node, which is identified by
the incoming edge.
• The children of a node are identified by the outgoing edges.
• Nodes that have at least one child are known as interior nodes while
nodes that have no children are known as leaf nodes.

Data Structures and Algorithms 7 FIT – HNUE 2021

 TERMINOLOGY

• Every node can be the root of its own subtree,

which consists of a subset of nodes and edges
of the larger tree.
• All of the nodes in a subtree are descendants
of the subtree's root.
• The ancestors of a node include the parent of
the node, its grandparent, its great-grandparent,
and so on all the way up to the root.

Data Structures and Algorithms 8 FIT – HNUE 2021

 BINARY TREE

Data Structures and Algorithms 9 FIT – HNUE 2020

 DEFINITION

• A binary tree is a tree in which each node can have at most two
children. One child is identified as the left child and the other as the
right child.

Data Structures and Algorithms 10 FIT – HNUE 2021

 TERMINOLOGY

• The nodes in a binary tree are organized into levels with the root node
at level 0, its children at level 1, the children of level one nodes are at
level 2, and so on.
• The depth of a node is its distance from the root. A node's depth
corresponds to the level it occupies.
• The height of a binary tree is is the length of the path from the root to
the deepest node in the tree. It is the maximum level among all the
nodes in the tree.
• The width of a binary tree is the number of nodes on the level
containing the most nodes.

Data Structures and Algorithms 11 FIT – HNUE 2021

 FULL BINARY TREE

• A full binary tree is a binary tree in which each interior node contains
two children.

Data Structures and Algorithms 12 FIT – HNUE 2021

 PERFECT BINARY TREE

• A perfect binary tree is a full binary tree in which all leaf nodes are at
the same level.

Data Structures and Algorithms 13 FIT – HNUE 2021

 COMPLETE BINARY TREE

• A binary tree of height h is a complete binary tree if it is a perfect

binary tree down to height h - 1 and the nodes on the lowest level ll the
available slots from left to right leaving no gaps.

Data Structures and Algorithms 14 FIT – HNUE 2021

 IMPLEMENTATION

• Binary trees are commonly implemented as a dynamic structure in the

same fashion as linked lists.

Data Structures and Algorithms 15 FIT – HNUE 2021

 TREE TRAVERSALS

• traversal iterates through a collection, one item at a time, in order to

access or visit each item.
• Three:
• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

Data Structures and Algorithms 16 FIT – HNUE 2021

 PREORDER TRAVERSAL

• Idea:
• If the tree is None, nothing to do
• Else
• Visit the root node.
• Traverse the left subtree
• Traverse the right subtree.

• Function:

Result: A, B, D, E, H, C, F, G, I, J.

Data Structures and Algorithms 17 FIT – HNUE 2021

 INORDER TRAVERSAL

• Idea:
• If the tree is None, nothing to do
• Else
• Traverse the left subtree
• Visit the root node.
• Traverse the right subtree.

• Function:

Result: D, B, H, E, A, F, C, I, G, J.

Data Structures and Algorithms 18 FIT – HNUE 2021

 POSTORDER TRAVERSAL

• Idea:
• If the tree is None, nothing to do
• Else
• Traverse the left subtree
• Traverse the right subtree.
• Visit the root node.
• Function:

Result: D, H, E, B, F, I, J, G, C, A.

Data Structures and Algorithms 19 FIT – HNUE 2021

 EXPRESSION TREES

Data Structures and Algorithms 20 FIT – HNUE 2020

 DEFINITION

• An expression tree is a binary tree in which the operators are stored

in the interior nodes and the operands (the variables or constant
values) are stored in the leaves.
• The structure of the expression tree is based on the order in which
the operators are evaluated.
• The operator in each internal node is evaluated after both its left and
right subtrees have been evaluated. Thus, the lower an operator is in
a subtree, the earlier it will be evaluated.

Data Structures and Algorithms 21 FIT – HNUE 2021

 EXPRESSION TREE ABSTRACT DATA TYPE

Data Structures and Algorithms 22 FIT – HNUE 2021

 USING EXPRESSION TREE ADT

Data Structures and Algorithms 23 FIT – HNUE 2021

 IMPLEMENTATION

Data Structures and Algorithms 24 FIT – HNUE 2021

 STRING REPRESENTATION

• Idea

Data Structures and Algorithms 25 FIT – HNUE 2021

 STRING REPRESENTATION

Data Structures and Algorithms 26 FIT – HNUE 2021

 TREE EVALUATION

• Idea:

Data Structures and Algorithms 27 FIT – HNUE 2021

 TREE EVALUATION

Data Structures and Algorithms 28 FIT – HNUE 2021

 TREE CONSTRUCTION

• Idea

Data Structures and Algorithms 29 FIT – HNUE 2021

 TREE CONSTRUCTION

Data Structures and Algorithms 30 FIT – HNUE 2021