Trees are a fundamental data structure.ppt

Trees are a fundamental data structure in computer science, used to represent hierarchical relationships. This tutorial covers several key types of trees.

1. Data Structures & Algorithms
Trees

2. Data Structures & Algorithms
Trees: Basic terminology[1]
•Hierarchical data structure
•Each position in the tree is called a node
•The “top” of the tree is called the root
•The nodes immediately below a node are called its children; nodes with no
children are called leaves (or terminal nodes), or terminal nodes, and the
node above a given node is its parent (or father)
•A node x is ancestor of node y if x is father of y or father of some ancestor
of y. y is called descendent of x. Ancestor of a node is its parent, grand
parent or grand-grand parent or so on….

3. Data Structures & Algorithms
Trees: Basic terminology[2]
•Nodes with the same parent are siblings
•A node plus the collection of nodes beneath it is called a
subtree
•The number of nodes in the longest path from the root to a leaf
is the depth (or height) of the tree
–is the depth 2 or 3?
–depends on the author

4. Data Structures & Algorithms
Root
Node A
Node H
Node B
Node GNode FNode ENode DNode C
Node KNode J
Node L
Node I
Nodes C, H, and I form a subtree
Nodes H and I are siblings
C is H’s parent, H and I are children of C
What is the depth of this tree?

5. Data Structures & Algorithms
Binary Trees
•A commonly used type of tree is a binary tree
•Each node has at most two children
•The “tree” is a conceptual structure
•The data can be stored either in a dynamic linked tree
structure, or in contiguous memory cells (array)
according to a set pattern; in other words,
implementation can be pointer-based or array-based

6. Data Structures & Algorithms
Binary trees
•A tree is called strictly binary tree if every non leaf node has exactly two
children.
•A strictly binary tree having n leaves always contain 2n-1 nodes
•Text book definition of depth of a tree
–Depth of binary tree is maximum level of any leaf in the tree.
–Root of tree is at level 0, and level of any other node in the tree is one more than
the level of its father

7. Data Structures & Algorithms
Binary Trees
•A complete binary tree of level d is the strictly binary tree all of whose
leaves are at level d
•A complete binary tree of level d has 2
l
nodes at each level l where
0<=l<=d
•Total number of nodes (tn) in a complete binary tree of depth d will
be:
1222222
1
0
210




d
d
j
jd
tn
For a binary tree of height h there are O(2
h
) nodes

8. Data Structures & Algorithms
Binary Trees
•For a complete binary tree if number of nodes (tn) are known, then we may
find depth of the binary tree
1-1)(log
1)(log1
12
12
2
2
1
1






tnd
tnd
tn
tn
d
d
A binary tree with nodes n has height O(log
2
n)

9. Data Structures & Algorithms
Binary Trees Storage
•Linked List based implementation
•Array based implementation

10. Data Structures & Algorithms
Binary Tree: as a linked structure
•Each node in the tree consists of:
–The data, or value contained in the element
–A left child pointer (pointer to first child)
–A right child pointer (pointer to second child)

11. Data Structures & Algorithms
Binary Tree: as a linked structure
•A root pointer points to the root node
–Follow pointers to find every other element in the tree
•Add and remove nodes by manipulating pointers
•Leaf nodes have child pointers set to null

12. Data Structures & Algorithms
class CBinTree
{
struct Node
{
int value;
Node *LeftChild,*RightChild;
}*Root;
/***Operations*********/
/************************/
};

13. Data Structures & Algorithms
ROOT

14. Data Structures & Algorithms
Binary Tree: contiguous storage
•Value in root node stored first, followed by left child, then right child
•Each successive level in the tree stored left to right; unused nodes in tree
represented by a bit pattern to indicate nothing stored there
•Children of any given node n is stored in cells 2n and 2n + 1 (If array index
starts at 1)
•Can calculate position for any given node
•Storage allocated as for full tree, even if many nodes empty
•For a tree of depth h we need array of 2
h+1
-1 cells

15. Data Structures & Algorithms
Binary Trees
•Full binary tree of height (depth) h: all nodes at a
height less than h have exactly two children
•Balanced binary tree: for each node, the difference
in depth of the right and left subtrees is no more than
one
•Completely balanced tree: left and right subtrees of
every node have the same height

16. Data Structures & Algorithms
Full Binary Tree
A very sparse,
unbalanced tree

17. Data Structures & Algorithms
Primitive Operations
•Left(node): Gives index/pointer of left child
•Right(node): Gives index/pointer of right child
•Parent(node): Returns index/pointer of parent
•Brother(node): Returns index/pointer of brother
•Root: Gives index/pointer of root node
•Info(Node): Data/Info stored at node
•IsLeft(node): Is node left child? Yes/No
•IsRight(node): Is node right child? Yes/No

18. Data Structures & Algorithms
Common Operations
•Tree traversal
•Node addition
•Node deletion
•Destroy

19. Data Structures & Algorithms
Traversal of Binary Trees
•Pass through all nodes of tree
•Inorder (symmetric traversal)
•Preorder (depth first traversal)
•Postorder

20. Data Structures & Algorithms
Trees Traversal
•Inorder
–(Left) Root (Right)
•Preorder
–Root (Left) (Right)
•Postorder
–(Left) (Right) Root
Root
Left Right

21. Data Structures & Algorithms
Inorder Traversal
Left Root Right manner
•Left + Right
•[Left*Right]+[Left+Right]
•(A*B)+[(Left*Right)+E)
•(A*B)+[(C*D)+E]
+
* +
A B* E
C D
(A*B)+(C*D+E)

22. Data Structures & Algorithms
Preorder Traversal
Root Left Right manner
•+ Left Right
•+ [*Left Right] [+Left Right]
•+(*AB) [+ *Left Right E]
•+*AB + *C D E
+
* +
A B* E
C D

23. Data Structures & Algorithms
Postorder Traversal
Left Right Root manner
•Left Right +
•[Left Right *] [Left Right+] +
•(AB*) [Left Right * E + ]+
•(AB*) [C D * E + ]+
•AB* C D * E + +
+
* +
A B* E
C D