Binary Search Tree (with non-recursive traversals) - Data Structures Source Code in C++

Special : Web Developer's Collection CD-ROM
50,000+ Web Templates, Logos, Cliparts, Scripts. Order Now!

Add to Favorites Make Home Page

5401 Online

Language Categories

Source Codes Home
Project Ideas New!
Interview Questions
FAQs Home
ASP Home: ASP Source Codes; ASP Script Directory New!; ASP .Net Script Directory New!; ASP Interview Questions; ASP FAQs; ASP How Tos
C Home: C Source Codes; C Script Directory New!; C Interview Questions; C FAQs; C How Tos
C++ Home: C++ Source Codes; C++ Script Directory New!; C++ Interview Questions; C++ FAQs; C++ How Tos
Java Home: Java Source Codes; Java Directory New!; Java Interview Questions; Java FAQs; Java How Tos
JavaScript Home: JavaScript Directory New!; JavaScript Source Codes; JavaScript FAQs; JavaScript How Tos
COBOL Home: COBOL Source Codes; COBOL FAQs; COBOL How Tos
Pascal Home: Pascal Source Codes; Pascal FAQs; Pascal How Tos
PHP Script Directory New!
Python Script Directory New!
Perl & CGI Script Directory New!
Flash Script Directory New!
CFML Script Directory New!
Remotely Hosted Scripts New!
Tools & Utilities Directory New!
XML Script Directory New!
Best Programmers: Amit Mathur; Vishal Bhardwaj; Deepesh Jain
Vyom NetWork

Our Services

Get 9,000 Interview Questions & Answers in an eBook.

9500+ Pages
9000 Question & Answers
All Tech. Categories

14 MB Content

Get it now !!

Home » C++ Home » Data Structures Home » Binary Search Tree (with non-recursive traversals)

A D V E R T I S E M E N T

Title	Binary Search Tree (with non-recursive traversals)
Author	Rajeswari Natarajan
Author Email	raji [at] svce.ac.in
Description	This program includes the inserting a node, deleting a node,recursive tree traversal,non-recursive tree traversal,finding the minimum,maximum,leftchild,rightchild,copy a tree to another,making a tree null.
Category	C++ » Data Structures
Hits	393239
Code	Select and Copy the Code
Code : # include <conio.h> # include <process.h> # include <iostream.h> # include <alloc.h> struct node { int ele; node left; node right; }; typedef struct node nodeptr; class stack { private: struct snode { nodeptr ele; snode next; }; snode top; public: stack() { top=NULL; } void push(nodeptr p) { snode temp; temp = new snode; temp->ele = p; temp->next = top; top=temp; } void pop() { if (top != NULL) { nodeptr t; snode *temp; temp = top; top=temp->next; delete temp; } } nodeptr topele() { if (top !=NULL) return top->ele; else return NULL; } int isempty() { return ((top == NULL) ? 1 : 0); } }; class bstree { public: void insert(int,nodeptr &); void del(int,nodeptr &); int deletemin(nodeptr &); void find(int,nodeptr &); nodeptr findmin(nodeptr); nodeptr findmax(nodeptr); void copy(nodeptr &,nodeptr &); void makeempty(nodeptr &); nodeptr nodecopy(nodeptr &); void preorder(nodeptr); void inorder(nodeptr); void postorder(nodeptr); void preordernr(nodeptr); void inordernr(nodeptr); void postordernr(nodeptr); void leftchild(int,nodeptr &); void rightchild(int,nodeptr &); }; void bstree::insert(int x,nodeptr &p) { if (p==NULL) { p = new node; p->ele=x; p->left=NULL; p->right=NULL; } else { if (x < p->ele) insert(x,p->left); else if (x>p->ele) insert(x,p->right); else cout<<"Element already Exits !"; } } void bstree:: del(int x,nodeptr &p) { nodeptr d; if (p==NULL) cout<<"Element not found "; else if (x < p->ele) del(x,p->left); else if (x > p->ele) del(x,p->right); else if ((p->left == NULL) && (p->right ==NULL)) { d=p; free(d); p=NULL; } else if (p->left == NULL) { d=p; free(d); p=p->right; } else if (p->right ==NULL) { d=p; p=p->left; free(d); } else p->ele=deletemin(p->right); } int bstree::deletemin(nodeptr &p) { int c; if (p->left == NULL) { c=p->ele; p=p->right; return c; } else c=deletemin(p->left); return c; } void bstree::copy(nodeptr &p,nodeptr &p1) { makeempty(p1); p1=nodecopy(p); } void bstree::makeempty(nodeptr &p) { nodeptr d; if (p!=NULL) { makeempty(p->left); makeempty(p->right); d=p; free(d); p=NULL; } } nodeptr bstree::nodecopy(nodeptr &p) { nodeptr temp; if (p == NULL) return p; else { temp = new node; temp->ele=p->ele; temp->left = nodecopy(p->left); temp->right = nodecopy(p->right); return temp; } } nodeptr bstree::findmin(nodeptr p) { if (p==NULL) { cout<<"Tree is empty !"; return p; } else { while (p->left !=NULL) p=p->left; return p; } } nodeptr bstree::findmax(nodeptr p) { if (p==NULL) { cout<<"Tree is empty !"; return p; } else { while (p->right !=NULL) p=p->right; return p; } } void bstree::find(int x,nodeptr &p) { if (p==NULL) cout<<"Element not found !"; else { if (x <p->ele) find(x,p->left); else if ( x> p->ele) find(x,p->right); else cout<<"Element Found !"; } } void bstree::preorder(nodeptr p) { if (p!=NULL) { cout<<p->ele<<"-->"; preorder(p->left); preorder(p->right); } } void bstree::inorder(nodeptr p) { if (p!=NULL) { inorder(p->left); cout<<p->ele<<"-->"; inorder(p->right); } } void bstree::postorder(nodeptr p) { if (p!=NULL) { postorder(p->left); postorder(p->right); cout<<p->ele<<"-->"; } } void bstree::preordernr(nodeptr p) { stack s; while (1) { if (p != NULL) { cout<<p->ele<<"-->"; s.push(p); p=p->left; } else if (s.isempty()) { cout<<"Stack is empty"; return; } else { nodeptr t; t=s.topele(); p=t->right; s.pop(); } } } void bstree::inordernr(nodeptr p) { stack s; while (1) { if (p != NULL) { s.push(p); p=p->left; } else { if (s.isempty()) { cout<<"Stack is empty"; return; } else { p=s.topele(); cout<<p->ele<<"-->"; } s.pop(); p=p->right; } } } void bstree::postordernr(nodeptr p) { stack s; while (1) { if (p != NULL) { s.push(p); p=p->left; } else { if (s.isempty()) { cout<<"Stack is empty"; return; } else if (s.topele()->right == NULL) { p=s.topele(); s.pop(); cout<<p->ele<<"-->"; if (p==s.topele()->right) { cout<<s.topele()->ele<<"-->"; s.pop(); } } if (!s.isempty()) p=s.topele()->right; else p=NULL; } } } void bstree::leftchild(int q,nodeptr &p) { if (p==NULL) cout<<"The node does not exists "; else if (q < p->ele ) leftchild(q,p->left); else if (q > p->ele) leftchild(q,p->right); else if (q == p->ele) { if (p->left != NULL) cout<<"Left child of "<<q<<"is "<<p->left->ele; else cout<<"No Left child !"; } } void bstree::rightchild(int q,nodeptr &p) { if (p==NULL) cout<<"The node does not exists "; else if (q < p->ele ) rightchild(q,p->left); else if (q > p->ele) rightchild(q,p->right); else if (q == p->ele) { if (p->right != NULL) cout<<"Right child of "<<q<<"is "<<p->right->ele; else cout<<"No Right Child !"; } } int main() { int ch,x,leftele,rightele; bstree bst; char c='y'; nodeptr root,root1,min,max; root=NULL; root1=NULL; do { // system("clear"); clrscr(); cout<<" Binary Search Tree "; cout<<"------------------------- "; cout<<" 1.Insertion 2.Deletion 3.NodeCopy "; cout<<" 4.Find 5.Findmax 6.Findmin "; cout<<" 7.Preorder 8.Inorder 9.Postorder "; cout<<" 10.Leftchild 11.Rightchild 0.Exit "; cout<<" Enter your choice :"; cin>>ch; switch(ch) { case 1: cout<<" 1.Insertion "; cout<<"Enter the new element to get inserted : "; cin>>x; bst.insert(x,root); cout<<"Inorder traversal is : "; bst.inorder(root); break; case 2: cout<<" 2.Deletion "; cout<<"Enter the element to get deleted : "; cin>>x; bst.del(x,root); bst.inorder(root); break; case 3: cout<<" 3.Nodecopy "; bst.copy(root,root1); cout<<" The new tree is : "; bst.inorder(root1); break; case 4: cout<<" 4.Find "; cout<<"Enter the element to be searched : "; cin>>x; bst.find(x,root); break; case 5: cout<<" 5.Findmax "; if (root == NULL) cout<<" Tree is empty"; else { max=bst.findmax(root); cout<<"Largest element is : "<<max->ele<<endl; } break; case 6: cout<<" 6.Findmin "; if (root == NULL) cout<<" Tree is empty"; else { min=bst.findmin(root); cout<<"Smallest element is : "<<min->ele<<endl; } break; case 7: cout<<" 7.Preorder "; if (root==NULL) cout<<" Tree is empty"; else { cout<<" Preorder traversal (Non-Recursive) is : "; bst.preordernr(root); cout<<" Preorder traversal (Recursive) is : "; bst.preorder(root); } break; case 8: cout<<" 8.Inorder "; if (root==NULL) cout<<" Tree is empty"; else { cout<<" Inorder traversal (Non-Recursive) is : "; bst.inordernr(root); cout<<" Inorder traversal (Recursive) is : "; bst.inorder(root); } break; case 9: cout<<" 9.Postorder "; if (root==NULL) cout<<" Tree is empty"; else { cout<<" Postorder traversal (Non-Recursive) is : "; bst.postordernr(root); cout<<" Postorder traversal (Recursive) is : "; bst.postorder(root); } break; case 10: cout<<" 10.Finding the left Child "; if (root==NULL) cout<<" Tree is empty"; else { cout<<"Enter the node for which the left child is to be found : "; cin>>leftele; bst.leftchild(leftele,root); } break; case 11: cout<<" 11.Finding the Right Child "; if (root==NULL) cout<<" Tree is empty"; else { cout<<"Enter the node for which the Right child is to be found : "; cin>>rightele; bst.rightchild(rightele,root); } break; case 0: exit(0); } cout<<" Continue (y/n) ? "; cin>>c; }while (c=='y' \|\| c == 'Y'); return 0; }

Related Source Codes

Script Name Author

Moving ball screen saver karlmarx

The Classic Game of Snake & Ladder Lakshmi Narayana .A

Railway seat reservation question which comes in sapient VyomWorld

To calculate percentile Ravi Mathur

Send to folder ANIMESH SAHU

Analog clock and calendar Nazia & Rida

HIGH/LOW GAME MOLLY ARORA

Data structure (stack Implimentation) Swapnil B Adsure

Memory Game AnirudhSanyal

Easy Calc Anirudh Sanyal

GK Quiz Anirudh Sanyal

Hangman Game Manish Jain

Snakeman Manish Jain

Full month Calendar Nigi

Cursor shapes nigi

A D V E R T I S E M E N T

Google Groups Subscribe to SourceCodesWorld - Techies Talk

Email:

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

Free Tutorials - HTML, Java, SQL, PHP, ASP, Perl, SQL Tutorials
Discuss Programming Problems and Freshers Jobs related issues here.
Discuss Final Year Project Ideas here.