Close

 Technicalsymposium

Free Training & Project Alerts & Study Notes Download-Subscribe

Free Training / Tech Courses Info/Student Scholarships

Student Project Details/IIT Courses Info

Aboard Admissions/ Study Materials & Ebooks Download

Click here to Subscribe & Details


Join Our Email Alerts-Subscribe
Important Note:Login & Check Your Email Inbox and Activate Confirmation Link


Enter Your Email :

DataStructure-Program to maintain a threaded binary tree

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
enum boolean
{
false = 0,
true = 1
} ;
struct thtree
{
enum boolean isleft ;
struct thtree *left ;
int data ;
struct thtree *right ;
enum boolen isright ;
} ;
void insert ( struct thtree **, int ) ;
void delete ( struct thtree **, int ) ;
void search ( struct thtree **, int, struct thtree **,struct thtree **, int * ) ;
void inorder ( struct thtree * ) ;
void deltree ( struct thtree ** ) ;
void main( )
{
struct thtree *th_head ;
th_head = NULL ; /* empty tree */
insert ( &th_head, 11 ) ;
insert ( &th_head, 9 ) ;
insert ( &th_head, 13 ) ;
insert ( &th_head, 8 ) ;
insert ( &th_head, 10 ) ;
insert ( &th_head, 12 ) ;
insert ( &th_head, 14 ) ;
insert ( &th_head, 15 ) ;
insert ( &th_head, 7 ) ;
clrscr( ) ;
printf ( "Threaded binary tree before deletion:\n" ) ;
inorder ( th_head ) ;
delete ( &th_head, 10 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;
delete ( &th_head, 14 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;
delete ( &th_head, 8 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;
delete ( &th_head, 13 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;
deltree ( &th_head ) ;
getch( ) ;
}
/* inserts a node in a threaded binary tree */
void insert ( struct thtree **s, int num )
{
struct thtree *p, *z, *head = *s ;
/* allocating a new node */
z = malloc ( sizeof ( struct thtree ) ) ;
z -> isleft = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> isright = true ; /* indicates a thread */
/* if tree is empty */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;
/* the entire tree is treated as a left sub-tree of the head node */
head -> isleft = false ;
head -> left = z ; /* z becomes leftchild of the head node */
head -> data = -9999 ; /* no data */
head -> right = head ; /* right link will always be pointing to itself */
head -> isright = false ;
*s = head ;
z -> left = head ; /* left thread to head */
z -> right = head ; /* right thread to head */
}
else /* if tree is non-empty */
{
p = head -> left ;
/* traverse till the thread is found attached to the head */
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> isleft != true ) /* checking for a thread */
p = p -> left ;
else
{
z -> left = p -> left ;
p -> left = z ;
p -> isleft = false ; /* indicates a link */
z -> isright = true ;
z -> right = p ;
return ;
}
}
else
{
if ( p -> data < num )
{
if ( p -> isright != true )
p = p -> right ;
else
{
z -> right = p -> right ;
p -> right = z ;
p -> isright = false ; /* indicates a link */
z -> isleft = true ;
z -> left = p ;
return ;
}
}
}
}
}
}
/* deletes a node from the binary search tree */
void delete ( struct thtree **root, int num )
{
int found ;
struct thtree *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;
/* if the node to deleted is not found */
if ( found == false )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
/* if the node to be deleted has two children */
if ( x -> isleft == false && x -> isright == false )
{
parent = x ;
xsucc = x -> right ;
while ( xsucc -> isleft == false )
{
parent = xsucc ;
xsucc = xsucc -> left ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
/* if the node to be deleted has no child */
if ( x -> isleft == true && x -> isright == true )
{
/* if node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = *root ;
( *root ) -> isleft = true ;
free ( x ) ;
return ;
}
if ( parent -> right == x )
{
parent -> isright = true ;
parent -> right = x -> right ;
}
else
{
parent -> isleft = true ;
parent -> left = x -> left ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only rightchild */
if ( x -> isleft == true && x -> isright == false )
{
/* node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = x -> right ;
free ( x ) ;
return ;
}
if ( parent -> left == x )
{
parent -> left = x -> right ;
x -> right -> left = x -> left ;
}
else
{
parent -> right = x -> right ;
x -> right -> left = parent ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only left child */
if ( x -> isleft == false && x -> isright == true )
{
/* the node to be deleted is a root node */
if ( parent == NULL )
{
parent = x ;
xsucc = x -> left ;
while ( xsucc -> right == false )
xsucc = xsucc -> right ;
xsucc -> right = *root ;
( *root ) -> left = x -> left ;
free ( x ) ;
return ;
}
if ( parent -> left == x )
{
parent -> left = x -> left ;
x -> left -> right = parent ;
}
else
{
parent -> right = x -> left ;
x -> left -> right = x -> right ;
}
free ( x ) ;
return ;
}
}
/* returns the address of the node to be deleted, address of its parent and whether the node is found or not */
void search ( struct thtree **root, int num, struct thtree **par, struct thtree **x, int *found )
{
struct thtree *q ;
q = ( *root ) -> left ;
*found = false ;
*par = NULL ;
while ( q != *root )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = true ;
*x = q ;
return ;
}
*par = q ;
if ( q -> data > num )
{
if ( q -> isleft == true )
{
*found = false ;
x = NULL ;
return ;
}
q = q -> left ;
}
else
{
if ( q -> isright == true )
{
*found = false ;
*x = NULL ;
return ;
}
q = q -> right ;
}
}
}
/* traverses the threaded binary tree in inorder */
void inorder ( struct thtree *root )
{
struct thtree *p ;
p = root -> left ;
while ( p != root )
{
while ( p -> isleft == false )
p = p -> left ;
printf ( "%d\t", p -> data ) ;
while ( p -> isright == true )
{
p = p -> right ;
if ( p == root )
break ;
printf ( "%d\t", p -> data ) ;
}
p = p -> right ;
}
}
void deltree ( struct thtree **root )
{
while ( ( *root ) -> left != *root )
delete ( root, ( *root ) -> left -> data ) ;
}

Get All Programming Codes & Placement and Tech Round Notes in Our Website




Placement Papers

All Companies Placement Papers with Answers - Free Download of Materials

Software Program

Top Programming Source Codes/Lab Manuals with Solutions-Complete Details

Technical Round Interview

All Companies Technical Round Interview Asked Questions with Answers

Government Jobs

All State and Central Government Jobs/Railway & Bank Jobs/Alll Competitive Exams-Complete Details.

Software Jobs

Entry Level Software & IT Jobs in Chennai/Bangalore & Leading Metro Cities-Complete Details.

Conference/Symposium

Engineering Colleges & University /Premier Institute (IIT/IIM/etc.,) Events Details.

Off-Campus/Walk-in

All Software Companies & Core Companies Off-Campus Interviews & Walk-in across India-Complete Details.

All Bank Jobs

All Government Bank & Private Bank Jobs-Complete Details.

Internships

All Companies Internships-Complete Details.

IBPS

Probationary Officers/Clerk and Management Trainees & All IBPS Exams/Syllabus-Complete Details.

GATE

All Branches Syllabus & Question Papers-Free Download.

IES-Exam

Indian Engineering Services Syllabus & Question.Papers-Complete Details.

Software Program

Top Programming Source Codes/Lab Manuals with Solutions-Complete Details

Anna University

B.E/B.Tech/M.E/M.Tech/MCA/MBA Latest Syllabus & Question Papers

Scholarships

All Central & State Govt Scholarships/ International Scholarships/Merit Scholarships Details.

Placement Papers

All Companies Placement Papers with Answers - Free Download of Materials

Aptitude

All Aptitude Test Topics with Answers-Complete Details & Free Download

Technical Round Interview

All Companies Technical Round Interview Asked Questions with Answers

Certifications

All Certifications Software & All Branches Certifications-Complete Details.

Group Discussion

Group Discussion Various Topics with Valid Points-Complete Details.

HR Round

All HR Round Questions and Answers/Tips & Do's and Don'ts of HR Round.

General Job

Job Interview Tips & Do's/Dont's/Dress Codes/Body Language-Complete Details.

Placement ebooks

All Companies Placement Materials with Answers-Complete Details.

Technical Round Tips

All Kind of Technical Round Interview Tips and Answers/ Do's and Don'ts

Resume

Resume Writing Tips/Do's & Don'ts-Complete Details.

Career Pages

All MNC Companies Career Pages & Current Openings-Complete Details.

Software Projects

All Software Projects with Source Codes-Free Download & Details.

GRE

GRE Exam Procedure and Complete Details.

TOEFL

TOEFL Exam Procedure and Complete Details.

IELTS

IELTS Exam Procedure and Complete Details

SAT

SAT Exam Procedure and Complete Details

GMAT

GMAT Exam Procedure and Complete Details

MS in USA

MS in USA Procedure and Complete Details

Civil Engineering

Civil Engineering Lecture Notes for All Universities & Lab Manuals for All Semester.-Free Download

Mechanical Engineering

Mechanical Engineering Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Automobile Engineering

Automobile Engineering Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Computer Science

Computer Science Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Information Technology

Information Technology Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

MBA

MBA Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Biotechnology

Biotechnology Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Biomedical

Biomedical Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Aeronautical Engineering

Aeronautical Engineering Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download

Chemical Engineering

Chemical Engineering Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Electronics & Communication

Electronics & Communication Engineering Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Electrical & Electronics

Electrical & Electronics Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

MCA

MCA Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

B.Sc

B.Sc All Branches (Maths/Physics/Computer Science/Electronics/etc.,)-Lecture Notes-Free Download

BCA

BCA Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

BBA

BBA Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

M.Sc

M.Sc All Branches (Maths/Physics/Computer Science/Electronics/etc.,)-Lecture Notes-Free Download

M.Com

M.Com Lecture Notes for All Universities & Lab Manuals for All Semester-Free Download.

Engineering Maths

All Semester Engineering Maths (M1/M2/M3/M4/etc.,) Lecture Notes-Free Download

Engineering EBooks

All Engineering Branches of ebooks Free Download-Complete Details.

Engineering Physics

All Semester Engineering Physics Lecture Notes-Free Download

GATE Preparation Books

All Branches of GATE Free Preparation eBooks-Free Download.

Engineering Chemistry

All Semester Engineering Chemistry Lecture Notes-Free Download

Software Companies Info

All Software Companies in India - Complete Details.

Admission

Foreign Universities All Course Admission Procedures-Complete Details.

Software Ebooks

All Programming Software free Eboooks-Free Download.

Web Hosting

All Web Hosting Procedure-Complete Details.