1. #include <iostream>
2. using namespace std;
3.  
4. struct node
5. {
6.         char val;
7.         int count;
8.         struct node *l, *r;
9. };
10.  
11. struct node *newNode(char item)
12. {
13.         struct node *data = new  node();
14.         data->val = item;
15.         data->l =NULL;
16.         data->r = NULL;
17.         data->count = 1;
18.         return data;
19. }
20. void function (struct node *base)
21. {
22.     if (base != NULL)
23.     {   if(base->count==1){
24.        
25.                 function(base->l);
26.             cout << base->val << " ";
27.             function(base->r);
28.  
29.         }
30.         else{
31.                 for(int i=1;i<=base->count;i++)
32.                         cout << base->val << " ";
33.  
34.                         function(base->l);
35.                 function(base->r);
36.         }
37.     }
38. }
39. void inorder (struct node *base)
40. {
41.         if (base != NULL){
42.                 inorder(base->l);      
43.                 cout << base->val << "(" << base->count << ") "; inorder(base->r);
44.         }
45. }
46.  
47. struct node* ins_func (struct node* node, char val)
48. {
49.         if (node == NULL)
50.                 return newNode(val);
51.         if (val == node->val){
52.                 (node->count)++;
53.                 return node;
54.         }
55.         if (val< node->val){
56.         node->l = ins_func(node->l, val);
57.         }
58.         else
59.         node->r = ins_func(node->r, val);
60.  
61. return node;
62. }
63.  
64. struct node * mv_node (struct node* node)
65. {
66.         struct node* crnt = node;
67.  
68.         while (crnt->l != NULL)
69.                 crnt = crnt->l;
70.  
71. return crnt;
72. }
73.  
74. struct node* del_node (struct node* base, char val)//delete funtion
75. {
76.     if (base == NULL)
77.                 return base;
78.     if (val < base->val)
79.         base->l = del_node(base->l, val);
80.     else if (val > base->val)
81.         base->r = del_node(base->r, val);
82.     else{
83.         if (base->count > 1){
84.            (base->count)--;
85.            return base;
86.         }
87.         if (base->l == NULL){
88.             struct node *data = base->r;
89.             delete(base);
90.             return data;
91.         }
92.         else if (base->r == NULL){
93.             struct node *data = base->l;
94.             delete(base);
95.             return data;
96.         }
97.        
98.         struct node* data = mv_node(base->r);
99.  
100.         base->val = data->val;
101.         base->r = del_node(base->r, data->val);
102.     }
103. return base;
104. }
105.  
106. int main()
107. {
108.         struct node *base = NULL;
109.         char a;
110.         cout << "Enter characters for your tree: \n (0 for exit):"<<endl;
111.         cin >> a;
112.        
113.         while (a != '0') {
114.                 base=ins_func (base,a);
115.                 cin >> a;
116.         }
117.         cout << "\nInorder traversal: " << endl;
118.         function (base);
119.         cout<<endl;
120.         inorder (base);
121.  
122.         cout<<"\n"<<endl;
123.        
124.         char b;
125.         cout << "enter the character that you want to delete . \n (If you don't, please enter 0 again) :" << endl;
126.         cin >> b;
127.  
128.         cout<<endl;
129.        
130.         while (b != '0') {
131.                 base = del_node (base, b);
132.                 cin >> b;
133.         }
134.     cout<<endl;
135.    
136.         cout << "Inorder traversal:"<<endl;
137.         function (base);
138.         cout<<endl;
139.         inorder (base);
140.        
141.         }
142.