-
Notifications
You must be signed in to change notification settings - Fork 0
/
tree_tranversalWithoutRecusion.cpp
122 lines (116 loc) · 2.25 KB
/
tree_tranversalWithoutRecusion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//
// main.cpp
// tree_tranversal_without_recursion
//
// Created by raghav babbar on 26/01/17.
// Copyright © 2017 raghav babbar. All rights reserved.
//
#include <stack>
#include <iostream>
using namespace std;
typedef struct node
{int data;
node *right;
node *left;
}node;
void postOrder(node *rootnode);
void inOrder(node *rootnode);
void preOrder(node *rootNode);
node * makeNode(int d);
void createTree(node *root,int d);
node * makeNode(int d)
{
node *ptr=(node*)malloc(sizeof(node));
ptr->data=d;
ptr->left=ptr->right=NULL;
return ptr;
}
void createTree(node *root,int d)
{
if(d>root->data)
{
if(root->right)
createTree(root->right,d);
else {root->right=makeNode(d);
}
}
else
{
if(root->left)
createTree(root->left, d);
else
root->left=makeNode(d);
}
}
void preOrder(node *rootNode)
{stack<node*> stk;
stk.push(rootNode);
while(!stk.empty())
{node *ptr=stk.top();
stk.pop();
cout<<" "<<ptr->data;
if(ptr->right)
stk.push(ptr->right);
if(ptr->left)
stk.push(ptr->left);
}
}
void inOrder(node *rootnode)
{stack<node*> stk;
node*ptr=rootnode;
abc:
stk.push(ptr);
while(true)
{if(!ptr->left) break;
stk.push(ptr->left);
ptr=ptr->left;
}
while(!stk.empty())
{node *p= stk.top();
stk.pop();
cout<<" "<<p->data;
if(p->right)
{ptr=p->right;
goto abc;
}
}
}
void postOrder(node *rootnode)
{stack<node* > stk;
node * lastpop=NULL;
node *ptr=rootnode;
abc:
while(true)
{stk.push(ptr);
if(!ptr->left)
break;
ptr=ptr->left;
}
while(!stk.empty())
{
if(stk.top()->right&&stk.top()->right!=lastpop)
{ptr=stk.top()->right;
goto abc;
}
else
{cout<<" "<<stk.top()->data;
lastpop=stk.top();
stk.pop();
}
}
}
int main()
{
cout<<"\nenter the data into the node and 0 to discontinue\n";
int dd;
cin>>dd;
node * rootnode=makeNode(dd);
while(true)
{cin>>dd;
if (dd==0) break;
createTree(rootnode,dd);}
cout<<"[";preOrder(rootnode); cout<<"]";cout<<"\n";
cout<<"[" ; inOrder(rootnode);cout<<"]";cout<<"\n";
cout<<"["; postOrder(rootnode);cout<<"]";cout<<"\n";
return 0;
}