Scribd
Upload
12 views11 pages

Tree

The document provides an overview of tree structures in computer science, defining key terms such as nodes, leaf nodes, and types of trees including binary trees and binary search trees. It explains concepts like tree traversal methods (in-order, pre-order, post-order) and various tree types like complete, strictly binary, and skewed binary trees. Additionally, it describes the characteristics of almost complete binary trees.

Uploaded by

siddojigariarpi6979
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
12 views11 pages

Tree

The document provides an overview of tree structures in computer science, defining key terms such as nodes, leaf nodes, and types of trees including binary trees and binary search trees. It explains concepts like tree traversal methods (in-order, pre-order, post-order) and various tree types like complete, strictly binary, and skewed binary trees. Additionally, it describes the characteristics of almost complete binary trees.

Uploaded by

siddojigariarpi6979
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/ 11

Tree

Tree is a infinite set of nodes with one


specially designated node called the
“root” and the remaining node are
partitioned into disjoints sets T1 to Tn,
where each of those sets is a TREE.
T1 to Tn are called sub-trees of the
root

Sunbeam Infotech 1
Terms used with trees
Node: A item storing information and
branches to other nodes
Null Tree: Tree with no node
Leaf Node: Terminal node of a tree & does
not have any node connected to it
Degree of a Node: No of sub trees of a node
Degree of a tree: Degree of a tree is
maximum degree of a node in the tree

Sunbeam Infotech 2
Terms used in trees
Parent Node: node having other nodes
connected to it
Siblings: Children of the same parents
Descendants: all those node which are
reachable from that node
Ancestor: all the node along the path from
the root to that node

Sunbeam Infotech 3
Terms used in Trees
Level of a Node:
 Indicates the position of the node in the
hierarchy
 Level of any node is level of its parent +1
 Level of root is 0
Depth of a tree: maximum level of any node
in the tree
Traversal : Visiting each node of tree exactly
once
Sunbeam Infotech 4
Binary Tree Traversal
In-order  L V R
Pre-Order  V L R
Post-Order  L R V
The traversal algorithms can be
implemented easily using recursion.
Non-recursive algorithms for
implementing traversal needs stack to
store node pointers.
Sunbeam Infotech 5
100,50,125,75,135,25,85,45,115,130,128
in-25,45,50,75,85,100,115,125,128,130,135
pre-100,50,25,45,75,85,125,115,135,130,128
post45,25,85,75,50,115,128,130,135,125,100

Sunbeam Infotech 6
Types of Trees
Binary Trees: It is a finite set of nodes
partitioned into three sub sets:- Root, Left
sub tree, Right sub tree

Binary Search tree: A binary search tree is a


binary tree in which the nodes are arranged
according to their values

Strictly Binary tree: All non leaf node have


two branches

Complete Binary tree: Tree with all leaf


nodes at the sameSunbeam
level Infotech 7
Complete Binary Tree
A A

B C
B C

D E
D F G E

Sunbeam Infotech 8
Strictly Binary Tree
A A

B C B C

D I J E D E

F G H F
K

Sunbeam Infotech 9
Types of trees
Skewed Binary tree: The branches of this
tree have either only left branches or right
branches
Almost Complete Binary Tree: A Binary
Tree of depth d is said to be an Almost
Complete Binary Tree if:
 Each leaf in a tree is at level d or d-1
 For any node N1 in a tree with right
descendent at level d , N1 must have Son
and every left descendant of N1 should be
either a leaf or should have two sons
Sunbeam Infotech 10
Almost complete binary tree
A A A

B C B B
C C

D E D E F G D E F G

F G H I J K H I

Sunbeam Infotech 11

You might also like