DataStructure/threatedtree.cpp at master · abhilabh/DataStructure · GitHub

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
#include<iostream>
 using namespace std;

  template<class T>
  class thnode
  {
	  public:
	  T info;
	  thnode <T> *lc;
	  thnode<T> *rc;
	  char tag;

	  thnode()
	  {
		  lc=rc=NULL;
		  tag='L';


		  }
		  ~thnode()
		  {
			  lc=rc=NULL;
			  }

  };

  template<class T>
  class  thtree
  {
	  public:
	 thnode<T> *root,*prev;
	  thtree()
	  {
		  root=NULL;

		  }
		  ~thtree(){}

		//  void insert(T x);
		  //void inorder(void);
	void insert(T x)
 {
	 thnode<T> *p;
	p=root;
	 thnode<T> *n=new thnode<T>;
	  n->info=x;
	 if (root==NULL)
	 {
		 root=n;
		 return ;
		 }
	 while(p!=NULL)
	 {
		 prev=p;
		 if(x<p->info)
		 p=p->lc;
		 else if(p->tag!='T')
		 p=p->rc;
		 else break;


		 }
	 if(x<prev->info)
	 {
		 prev->lc=n;
		 n->rc=prev ;
		 n->tag='T';
		 return ;

		 }
		 else if(prev->tag=='T')
		 {
			 n->rc=prev->rc;
			 prev->tag='L';
			 n->tag='T';
			 prev->rc=n;
			 return ;

			 }
			 else
			 {
				  prev->rc=n;
			      return ;
			 }

	 return ;
	 }

	// template<class T>
	 void inorder(thnode<T> *ptr)
	 {
		 if(ptr!=NULL)
		 {
			 inorder(ptr->lc);
			 cout<<ptr->info;
			 if(ptr->tag!='L')
			 {
				 inorder(ptr->rc);
				 }
			 }
		 }

	  };
 //template<class T>

int main()
{
	int n=6;
	thtree<int> t1;
	thtree<string> t2;
	int x;
	for(int i=0;i<n;i++)
	{
		cout<<"enter the no:";
		cin>>x;
		t1.insert(x);
		}
		t1.inorder(t1.root);
	}