Subjects
Applied Mathematics for Electrical Engineering - 3130908
Complex Variables and Partial Differential Equations - 3130005
Engineering Graphics and Design - 3110013
Basic Electronics - 3110016
Mathematics-II - 3110015
Basic Civil Engineering - 3110004
Physics Group - II - 3110018
Basic Electrical Engineering - 3110005
Basic Mechanical Engineering - 3110006
Programming for Problem Solving - 3110003
Physics Group - I - 3110011
Mathematics-I - 3110014
English - 3110002
Environmental Science - 3110007
Software Engineering - 2160701
Data Structure - 2130702
Database Management Systems - 2130703
Operating System - 2140702
Advanced Java - 2160707
Compiler Design - 2170701
Data Mining And Business Intelligence - 2170715
Information And Network Security - 2170709
Mobile Computing And Wireless Communication - 2170710
Theory Of Computation - 2160704
Semester
Semester - 1
Semester - 2
Semester - 3
Semester - 4
Semester - 5
Semester - 6
Semester - 7
Semester - 8
Data Structure
(2130702)
DS-2130702
Summer-2019
Question-5-b
BE | Semester-
3
Summer-2019
|
06/04/2019
Q5) (b)
4 Marks
Explain Threaded binary trees with suitable examples.
Threaded Binary Tree
The wasted NULL links in the binary tree storage representation can be replaced by threads.
A binary tree is threaded according to particular traversal order. e.g.: Threads for the inorder traversals of tree are pointers to its higher nodes, for this traversal order.
If left link of node P is null, then this link is replaced by the address of its predecessor.
If right link of node P is null, then it is replaced by the address of its successor.
Because the left or right link of a node can denote either structural link or a thread, we must somehow be able to distinguish them.
Method 1:-
Represent thread a –ve address.
Method 2:-
To have a separate Boolean flag for each of left and right pointers, node structure for this is given below,
LTHREAD = true = Denotes leaf thread link.
LTHREAD = false = Denotes leaf structural link.
RTHREAD = true = Denotes right threaded link.
RTHREAD = false = Denotes right structural link.
Head Node
Head node is simply another node which serves as the predecessor and successor of first and last tree nodes. Tree is attached to the left branch of the head node
Advantages
Inorder traversal is faster than unthreaded version as stack is not required.
Effectively determines the predecessor and successor for inorder traversal, for unthreaded tree this task is more difficult.
A stack is required to provide upward pointing information in tree which threading provides.
It is possible to generate successor or predecessor of any node without having over head of stack with the help of threading.
Disadvantages
Threaded trees are unable to share common subtrees.
If –ve addressing is not permitted in programming language, two additional fields are required.
Insertion into and deletion from threaded binary tree are more time consuming because both thread and structural link must be maintained.
Given a Binary Tree
Fully In-threaded binary tree of given binary tree
Questions
Go to Question Paper
Q1
(a)
(b)
(c)
Q2
(a)
(b)
(c)
(c)
(OR)
Q3
(a)
(b)
(c)
(a)
(OR)
(b)
(OR)
(c)
(OR)
Q4
(a)
(b)
(c)
(a)
(OR)
(b)
(OR)
(c)
(OR)
Q5
(a)
(b)
(c)
(a)
(OR)
(b)
(OR)
(c)
(OR)