1 /*
 2 Date:    2014-04-29
 3 purpose: An implementation of MAP using binary search tree.
 4 */
 5 
 6 #ifndef CUSTOMIZED_MAP_H
 7 #define CUSTOMIZED_MAP_H
 8 
 9 #ifndef NULL
10 #define NULL 0
11 #endif
12 
13 class NODE{
14 public:
15     NODE(int _key, char * _data):key(_key),data(_data),left(NULL),right(NULL){}
16     
17 public:    
18     int key;
19     char * data;
20     NODE * left;
21     NODE * right;    
22 };
23 
24 class CUST_MAP{
25 public:
26     CUST_MAP():root(NULL){}; // how about construction failed?
27     ~CUST_MAP();
28     void destructorImp(NODE * root);
29     bool appendItem(int key, char * data);
30     bool removeItem(int key);
31     bool traverse();
32     bool traverseImp(NODE * root);
33 
34 public:
35     NODE * root;
36 };
37 
38 #endif

  1 #include <iostream>
  2 #include <vector>
  3 #include "Customized_MAP.h"
  4 
  5 using std::cout;
  6 using std::endl;
  7 using std::string;
  8 
  9 bool CUST_MAP::appendItem(int key, char * data){
 10     enum Direction{LEFT, RIGHT}; //append which direction of the pended item
 11     Direction direction = LEFT; 
 12     
 13     //routine check.
 14     NODE * root = this->root;
 15     if (root == NULL){
 16         this->root = new NODE(key, data);
 17         if (this->root)
 18             return true;
 19         else return false;
 20     }
 21 
 22     NODE * image = root;//record the history of root
 23     
 24     // find inserting point
 25     while (root){
 26         image = root;
 27         if (root->key > key){ 
 28             root = root->left;
 29             direction = LEFT;
 30         }
 31         else if (root->key < key){
 32             root = root->right;
 33             direction = RIGHT;
 34         }
 35         else return false;  // duplicated key==> abort appending operation
 36     }
 37 
 38     // append the fresh node
 39     NODE * newNode = new NODE(key, data);
 40     if (direction == LEFT){
 41         image->left = newNode;
 42     }else if (direction == RIGHT){
 43         image->right = newNode;
 44     }
 45 
 46     return true;
 47 }
 48 
 49 bool CUST_MAP::removeItem(int key){
 50     enum Direction{LEFT, RIGHT}; //append which direction of the new item
 51     Direction direction = LEFT;
 52 
 53     NODE * root = this->root;
 54     if (root == NULL) // no node deleted. return false 
 55         return false;
 56 
 57     NODE * parent = NULL;
 58 
 59     while(root){
 60         if (root->key > key){
 61             parent = root;
 62             root = root->left;
 63             direction = LEFT;
 64         }
 65         else if (root->key < key){
 66             parent = root;
 67             root = root->right;
 68             direction = RIGHT;
 69         }
 70         else if (root->key == key){
 71             if (root->left && root->right){//要删除的节点有两个孩子节点
 72                 if (root->right->left == NULL){ 
 73                     //要删除节点的右孩子结点没有左孩子节点
 74                     //1：copy data, root->right  ===>  root.
 75                     //2: record pointer
 76                     //3: delete root->right
 77                     //4: finish pointer association
 78                     //how to delete root->data;
 79                     root->data = http://www.mamicode.com/root->right->data;
 80                     root->key = root->right->key;
 81                     NODE * right = root->right->right;
 82                     
 83                     delete root->right;
 84 
 85                     root->right = right;
 86                 }else{ 
 87                     //要删除节点的右孩子结点有左孩子节点
 88                     //root: 要删除的节点
 89                     //找到root右孩子的 最左方没左孩子的节点： tParent
 90                     NODE * t = root->right;
 91                     NODE * tParent = NULL;
 92                     while (t->left){
 93                         tParent = t;
 94                         t = t->left;
 95                     }
 96                     root->key = t->key;
 97                     root->data = http://www.mamicode.com/t->data;
 98                     NODE * right = t->right;
 99                     
100                     delete t;
101                     t = NULL;
102                     
103                     tParent->left = right;
104                 }
105 
106             }else if (root->left){//要删除的节点只有左孩子节点
107                 if (direction == LEFT)
108                     parent->left = root->left;
109                 else if(direction == RIGHT)
110                     parent->right = root->left;
111 
112                 delete root;
113                 root = NULL;
114             }else if(root->right){//要删除的节点只有右孩子节点
115                 if (direction == LEFT)
116                     parent->left = root->right;
117                 else if(direction == RIGHT)
118                     parent->right = root->right;
119                 
120                 delete root;
121                 root = NULL;
122             }else if (root->left==NULL && root->right==NULL){//要删除的节点没有孩子节点
123                 if (direction == LEFT)
124                     parent->left = NULL;
125                 else if(direction == RIGHT)
126                     parent->right = NULL;
127                 
128                 delete root;
129                 root = NULL;
130             }
131 
132             return true;
133         }
134     }
135 
136     return false;
137 }
138 
139 void CUST_MAP::destructorImp(NODE * root){
140     if (root){
141         destructorImp(root->left);
142         destructorImp(root->right);
143         
144         delete root;
145         root = NULL;
146     }
147 }
148 
149 CUST_MAP::~CUST_MAP(){
150     destructorImp(root);
151 }
152 
153 bool CUST_MAP::traverseImp(NODE * root){
154     if (root){
155         traverseImp(root->left);
156         cout<<root->data<<endl;
157         traverseImp(root->right);
158     }
159 
160     return true;
161 }
162 
163 bool CUST_MAP::traverse(){
164     traverseImp(root);
165 
166     return true;
167 }
168 
169 int main(){
170     CUST_MAP mapTest;
171     mapTest.appendItem(1, "1 one");
172     mapTest.appendItem(28, "28 twenty-eight");
173     mapTest.appendItem(16, "16 sixteen");
174     mapTest.appendItem(12, "12 twelf");
175     mapTest.appendItem(24, "24 twety-four");
176     mapTest.appendItem(56, "56 fifty-six");
177     mapTest.appendItem(36, "36 thirty-six");
178     mapTest.appendItem(66, "66 sixty-six");
179     mapTest.appendItem(46, "46 fourty-six");
180 
181     cout<<"New:"<<endl;
182     mapTest.traverse();
183     cout<<endl<<endl;
184 
185     mapTest.removeItem(36);
186     cout<<"New:"<<endl;
187     mapTest.traverse();
188 
189     cout<<"over"<<endl;
190 
191     return 0;
192 }