Chapter 8
Tree
Dr. Ameera Jaradat
[email protected]
Data Structures and Algorithms in Python
© 2013 Goodrich, Tamassia, Goldwasser
Linear vs nonlinear structure
• So far we have seen linear structures
– The data elements are sequentially connected in a Single level.
– lists, vectors, arrays, stacks, queues.
• Non-linear structure:
– Data elements are arranged in Multiple levels, there exists a
relationship between the data elements.
– Trees (hierarchical structure), Graph.
Tree Terminology
• Tree data structure is a collection of
data (Node) which is organized in
Edge
hierarchical structure recursively.
A
node
• Edge : the connecting link between
any two nodes. B C
D E F G H
• Tree is a connected Graph with no
cycles.
• In a tree, if we have N number of
nodes then we must have N - 1 I J E
number of links.
A Tree with 10 nodes and 9 edges
Root : top element
Root
• Every tree must have
only one root node. A
B C
• the root node is the
origin of the tree D E F G H
data structure.
I J E
Child
• CHILD Node: the node
which is descendant of
any node is called as . A
• In a tree, any parent
node can have any C
B
number of child nodes.
• In a tree, all the nodes
except root are child D E F G H
nodes.
I J E
• Each element has 0 or
more children
Parent
• PARENT NODE: the
node which is a A
predecessor of any
node. B C
• A node which has a
child / children. D E F G H
• Also internal nodes
I J E
• Except the root, each
element has a parent
Leaf
A
• LEAF Node: the
node which does B C
not have a child.
D E F G H
• External node.
I J K
Siblings
A
• SIBLINGS : nodes
which belong to B C
same Parent.
D E F G H
I J E
Degree
A
• Node DEGREE : the C
B
total number of
children of a node
D E F G H
• Degree of Tree:The
I J K
highest degree of a
node among all the
Degree of A = 2
nodes in a tree. Degree of B = 3
Degree of H = 0
Degree of Tree = 3
Level
Each step from top to bottom is called as a Level and the Level
count starts with '0' and incremented by one at each level
– root node is at Level 0
– children of root are at Level 1
– the children of the nodes which are at Level 1 will be at Level 2
and so on.
A Level 0
B C Level 1
G H
D E F Level 2
I J K Level 3
Path
• PATH between that two Nodes: the sequence of Nodes
and Edges from one node to another
• Length of a Path is total number of edges in that path.
Path length = 3
Path length = 2
HEIGHT
• Height of Node X: the longest path (number of edges) from leaf
node to node X.
• Height of the tree = Height of Root .
• height of all leaf nodes = 0.
Depth
• Depth of Node X: the total number of edges (path length) from the
root node to node X.
• Depth of the tree: longest path from root node to a leaf node in the
Tree.
• depth of the root node is '0'.
Depth = Level
Height of the tree
= Height of Root
= Depth of Tree
= number of last level
SUB TREE
• each child from a node forms a subtree recursively.
Ancestors
Ancestor node of a node is any node in the path from that node
to the root node (including the root node).
Ancestor of B is {A} B C
Ancestor of E is {B, A} D E F G H
I J K Ancestor of K is {G,C,A}
Descendants
Descendants of a node are all the nodes in the subtree rooted at that node.
A
Descendants of B
{D,E,F,I,J}
Descendants of C
B C {G,H,K}
Descendants of D {} E F G H
D
Descendants of E
{I,J}
I J K Descendants of G
{K}
Forest
• A forest is a set of disjoint trees.
Thanks for listening
Next :
BINARY TREE
