数据结构大型实验的记录(done)

用平衡二叉树的知识实现用户登录系统模拟

基本思路：

　　类：AVLnode (树的节点类)

　　　　AVLtree (树的基本操作类包括insert remove search 平衡树的4种旋转)

　　　　UserInfo(用户信息类)

决定还是按日期更新这样更完整一点

12-15

昨天写到12点多，基本写完了AVL类，删除部分还有待完善，之后可能要补充平衡过程。

昨天写完类后想到具体的用户交互过程，想到一个节点里不仅要存用户名还要存密码，然后之前写类的时候一直是当一个nodeValue来写的，写到头昏脑胀有点晕以为要重新写一遍把nodeValue更新到两个了。今天想到了很简单的解决办法，只要在AVLnode类里加一个string password然后在每次insert完后返回insert的节点，再用节点指向它的password就可以了。

初步做了交互界面。

不是数据的问题，insert方法本身就有问题可能不只是旋转上的错误

apple fhy1118
Apple 1110111
abc ABC4C
Aabc1 **2
cat 890
but happy
flower flower
trees 5678910
flowst 9087
but1 000000
flowar 080808

12-16

尼玛挑了半天旋转本来没问题的都快被我调成有问题的了。格式也超优化结果发现是insert里面p往上遍历写错

for(int i=0;i<count-2;i++)

　　p=newnode->parent;

发现的时候心中真的千万匹草泥马开始奔腾啊！！！！！！

但是成功构建以后很爽！！！！！！！

这尼玛大概就是程序猿的痛并快乐着了吧！！！！！！！！！！

贴上完整代码！！！

 1 // AVLnode.h: interface for the AVLnode class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_AVLNODE_H__C8E651E6_0EA9_4808_848B_0CB927923FAE__INCLUDED_)
 6 #define AFX_AVLNODE_H__C8E651E6_0EA9_4808_848B_0CB927923FAE__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 #include <stddef.h>
12 #include <string>
13 using namespace std;
14 
15 class AVLnode  
16 {
17     public:
18         string nodeValue;// node data
19         string password;
20         AVLnode *left, *right, *parent; // child pointers and pointer to the node's parent
21         AVLnode (const string item, AVLnode *lptr=NULL, AVLnode *rptr=NULL, AVLnode *pptr=NULL):
22             nodeValue(item), left(lptr), right(rptr), parent(pptr)
23             {}
24     public:
25         AVLnode(){password="";};
26         virtual ~AVLnode(){};
27 
28 };
29 
30 #endif // !defined(AFX_AVLNODE_H__C8E651E6_0EA9_4808_848B_0CB927923FAE__INCLUDED_)

AVLnode.h

  1 // AVLtree.h: interface for the AVLtree class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #if !defined(AFX_AVLTREE_H__36B69688_6A87_4949_A008_13138B14D185__INCLUDED_)
  6 #define AFX_AVLTREE_H__36B69688_6A87_4949_A008_13138B14D185__INCLUDED_
  7 
  8 #if _MSC_VER > 1000
  9 #pragma once
 10 #endif // _MSC_VER > 1000
 11 
 12 #include "AVLnode.h"
 13 #include "tnodeShadow.h"
 14 #include <iostream>
 15 #include <iomanip>
 16 using namespace std;
 17 
 18 class AVLtree  
 19 {
 20     public:
 21         AVLtree(); // constructor. initialize root to NULL and size to 0
 22         ~AVLtree();  // destructor
 23         tnodeShadow *buildShadowTree(AVLnode *t, int level, int& column);
 24         
 25 
 26         void displayTree(int maxCharacters);
 27         void deleteShadowTree(tnodeShadow *t);
 28         AVLnode *insert(const string &item);
 29         void remove(const string &item);
 30         AVLnode *search(const string &item) const;
 31         AVLnode *getRoot();
 32 
 33     private:
 34         AVLnode *root; // pointer to tree root
 35         int treeSize; // number of elements in the tree
 36         AVLnode *creatAVLNode(const string item, AVLnode *lptr, AVLnode *rptr,  AVLnode *pptr);
 37 
 38         int depth(AVLnode *p)
 39         {
 40             int ldep=0,rdep=0,depval;
 41             if(p==NULL)
 42                 depval=-1;
 43             else
 44             {
 45                 ldep=depth(p->left);
 46                 rdep=depth(p->right);
 47                 depval=1+(ldep>rdep?ldep:rdep);
 48             }
 49             return depval;
 50         };
 51 
 52         int balanceFactor(AVLnode *cur)
 53         {
 54             int ldep=0,rdep=0;
 55             AVLnode *p=cur;
 56             ldep=depth(p->left);
 57             rdep=depth(p->right);
 58             return (rdep-ldep);    
 59         };
 60 
 61         void rightRotate(AVLnode *cur)
 62         {
 63             //cur is the middle one
 64             if(cur->right!=NULL)
 65             {
 66                 cur->parent->left=cur->right;
 67                 cur->right->parent=cur->parent;
 68             }
 69             else cur->parent->left=NULL;
 70 
 71             if(cur->parent->parent==NULL)
 72             {
 73                 cur->parent->parent=cur;
 74                 cur->right=cur->parent;
 75                 cur->parent=NULL;
 76                 root=cur;
 77             }
 78             else 
 79             {
 80                 AVLnode *pr=cur->parent->parent;
 81                 cur->right=cur->parent;
 82                 cur->parent->parent=cur;
 83 
 84                 cur->parent=pr;
 85                 if(cur->nodeValue>pr->nodeValue)
 86                     pr->right=cur;
 87                 else pr->left=cur;
 88             }
 89         };
 90 
 91         void leftRotate(AVLnode *cur)
 92         {
 93             //cur is the middle one
 94             if(cur->left!=NULL)
 95             {
 96                 cur->parent->right=cur->left;
 97                 cur->left->parent=cur->parent;
 98             }
 99             else cur->parent->right=NULL;
100 
101             if(cur->parent->parent==NULL)
102             {
103                 cur->parent->parent=cur;
104                 cur->left=cur->parent;
105                 cur->parent=NULL;
106                 root=cur;
107             }
108             else 
109             {
110                 AVLnode *pr=cur->parent->parent;
111                 cur->left=cur->parent;
112                 cur->parent->parent=cur;
113 
114                 cur->parent=pr;
115                 if(cur->nodeValue>pr->nodeValue)
116                     pr->right=cur;
117                 else pr->left=cur;
118             }
119         };
120 
121         void leftrightRotate(AVLnode *cur)
122         {
123             //cur is the third one
124             //全空
125             if(cur->left==NULL&&cur->right==NULL)
126             {
127                 cur->parent->right=NULL;
128                 cur->parent->parent->left=NULL;
129             }
130             //一边空 另一边最多一个
131             else if(cur->right==NULL)
132             {
133                 cur->left->parent=cur->parent;
134                 cur->parent->right=cur->left;
135                 cur->parent->parent->left=NULL;
136             }
137             else if(cur->left==NULL)
138             {
139                 cur->right->parent=cur->parent->parent;
140                 cur->parent->parent->left=cur->right;
141                 cur->parent->right=NULL;
142             }
143             //非空 挂在一边 另一边最多只有一个元素
144             else
145             {
146                 cur->left->parent=cur->parent;
147                 cur->parent->right=cur->left;
148 
149                 cur->right->parent=cur->parent->parent;
150                 cur->parent->parent->left=cur->right;
151         
152             }
153             AVLnode *pr=cur->parent->parent->parent;
154 
155             cur->right=cur->parent->parent;
156             cur->parent->parent->parent=cur;
157                 
158             cur->parent->parent=cur;
159             cur->left=cur->parent;
160 
161             if(pr!=NULL)
162             {
163                 cur->parent=pr;
164                 if(cur->nodeValue<pr->nodeValue)
165                     pr->left=cur;
166                 else pr->right=cur;
167             }
168             else
169             {                
170                 cur->parent=NULL;
171                 root=cur;
172             }
173         };
174 
175         void rightleftRotate(AVLnode *cur)
176         {
177             //cur is the third one
178             //全空
179             if(cur->left==NULL&&cur->right==NULL)
180             {
181                 cur->parent->left=NULL;
182                 cur->parent->parent->right=NULL;
183             }
184             //一边空 另一边最多一个
185             else if(cur->left==NULL)
186             {
187                 cur->right->parent=cur->parent;
188                 cur->parent->left=cur->right;
189                 cur->parent->parent->right=NULL;
190             }
191             else if(cur->right==NULL)
192             {
193                 cur->left->parent=cur->parent->parent;
194                 cur->parent->parent->right=cur->left;
195                 cur->parent->left=NULL;
196             }
197             //非空 挂在一边 另一边最多只有一个元素
198             else
199             {
200                 cur->right->parent=cur->parent;
201                 cur->parent->left=cur->right;
202 
203                 cur->left->parent=cur->parent->parent;
204                 cur->parent->parent->right=cur->left;
205         
206             }
207             AVLnode *pr=cur->parent->parent->parent;
208 
209             cur->left=cur->parent->parent;
210             cur->parent->parent->parent=cur;
211                 
212             cur->parent->parent=cur;
213             cur->right=cur->parent;
214 
215             if(pr!=NULL)
216             {
217                 cur->parent=pr;
218                 if(cur->nodeValue<pr->nodeValue)
219                     pr->left=cur;
220                 else pr->right=cur;
221             }
222             else
223             {                
224                 cur->parent=NULL;
225                 root=cur;
226             }
227         }
228 
229 
230 };
231 
232 #endif // !defined(AFX_AVLTREE_H__36B69688_6A87_4949_A008_13138B14D185__INCLUDED_)

AVLtree.h

 1 // menu.h: interface for the menu class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_MENU_H__A58647F3_F271_4C38_8097_A38DF9CA38CF__INCLUDED_)
 6 #define AFX_MENU_H__A58647F3_F271_4C38_8097_A38DF9CA38CF__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 #include "AVLtree.h"
12 #include <fstream>
13 #include <stack>
14 using namespace std;
15 
16 class menu  
17 {
18 public:
19     menu();
20     virtual ~menu();
21     void select();
22     void menuInsert();
23     void menuLogin();
24     void menulogsuccess(AVLnode *login);
25     void menuChange(AVLnode *login);
26     void menuDelete(AVLnode *login);
27     void menuexit();
28 
29 
30 private:
31     AVLtree tree;
32 };
33 
34 #endif // !defined(AFX_MENU_H__A58647F3_F271_4C38_8097_A38DF9CA38CF__INCLUDED_)

menu.h

  1 // menu.cpp: implementation of the menu class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "menu.h"
  6 
  7 //////////////////////////////////////////////////////////////////////
  8 // Construction/Destruction
  9 //////////////////////////////////////////////////////////////////////
 10 
 11 menu::menu()
 12 {
 13     ifstream f;
 14     f.open("1.txt");
 15     string id,pass;
 16     while(!f.eof())
 17     {
 18         f>>id>>pass;
 19         AVLnode *t=tree.insert(id);
 20         t->password=pass;
 21     }
 22     f.close();
 23 }
 24 
 25 menu::~menu()
 26 {
 27 
 28 }
 29 void menu::select()
 30 {
 31     cout<<"--------------------------------------------------------------------------------
";
 32     cout<<"                                     welcome                                    
";
 33     cout<<"--------------------------------------------------------------------------------
";
 34     cout<<"--------------------------------------------------------------------------------
";
 35     cout<<"                                   1.注册账号                                   

";
 36     cout<<"                                   2.登录账号                                   

";
 37     cout<<"                                   3.退    出                                   

";
 38     cout<<"--------------------------------------------------------------------------------
";
 39     cout<<"输入数字进行选择：";
 40     int choice;
 41     cin>>choice;
 42     if(choice==1)
 43         menuInsert();
 44     if(choice==2)
 45         menuLogin();
 46     else
 47         menuexit();
 48 }
 49 
 50 void menu::menuInsert()
 51 {
 52     cout<<"--------------------------------------------------------------------------------
";
 53     cout<<"                                    注册账号                                    
";
 54     cout<<"--------------------------------------------------------------------------------
";
 55     bool exist=true;
 56     string userId;
 57     string npassword;
 58     while(exist)
 59     {
 60         cout<<"请输入账号: ";
 61         cin>>userId;
 62         
 63         AVLnode *judge=tree.search(userId);
 64         if(judge==NULL) exist=false;
 65         else cout<<"您输入的用户名已存在！
";
 66     }
 67     AVLnode *cur=tree.insert(userId);
 68     
 69     cout<<"请输入密码: ";
 70     cin>>npassword;
 71     cur->password=npassword;
 72     menuexit();  //更新注册后的用户信息 否则删除出错。
 73     cout<<"--------------------------------------------------------------------------------
";
 74     cout<<"                                   注册成功！                                   
";
 75     cout<<"--------------------------------------------------------------------------------
";
 76     cout<<"按1键返回上层...";
 77     int num;
 78     cin>>num;
 79     if(num==1)
 80         select();
 81     else
 82         menuexit();
 83 }
 84 
 85 void menu::menuLogin()
 86 {
 87     cout<<"--------------------------------------------------------------------------------
";
 88     cout<<"                                    登录账号                                    
";
 89     cout<<"--------------------------------------------------------------------------------
";
 90     string userId;
 91     string npassword;
 92     cout<<"请输入账号: ";
 93         cin>>userId;
 94     cout<<"请输入密码: ";
 95         cin>>npassword;
 96     AVLnode *login=tree.search(userId);
 97     if(login==NULL)
 98     {
 99         cout<<"--------------------------------------------------------------------------------
";
100         cout<<"                              您输入的账号不存在!                               
";
101         cout<<"--------------------------------------------------------------------------------
";
102         cout<<"按下1键重新输入...
";
103         int num;
104         cin>>num;
105         if(num==1)
106             menuLogin();
107         else
108             menuexit();
109     }
110     else
111     {
112         if(login->password==npassword)
113             menulogsuccess(login);
114         else
115         {
116             cout<<"--------------------------------------------------------------------------------
";
117             cout<<"                                   密码错误!                                    
";
118             cout<<"--------------------------------------------------------------------------------
";    
119             cout<<"按下1键重新输入...";
120             int num;
121             cin>>num;
122             if(num==1)
123                 menuLogin();
124             else
125                 menuexit();
126         }
127     }
128 }
129 
130 void menu::menulogsuccess(AVLnode *login)
131 {
132     cout<<"--------------------------------------------------------------------------------
";
133     cout<<"                                    登录成功!                                   
";
134     cout<<"--------------------------------------------------------------------------------
";
135     cout<<"--------------------------------------------------------------------------------
";
136     cout<<"                                   1.修改密码                                   

";
137     cout<<"                                   2.删除账号                                   

";
138     cout<<"                                   3.回主菜单                                   

";
139     cout<<"--------------------------------------------------------------------------------
";
140     cout<<"输入数字进行选择：";
141     int choice;
142     cin>>choice;
143     if(choice==3) select();
144     if(choice==1)
145         menuChange(login);
146     if(choice==2)
147         menuDelete(login);
148     else
149         menuexit();
150 }
151 
152 void menu::menuChange(AVLnode *login)
153 {
154     cout<<"请输入新密码: ";
155     string npassword;
156     cin>>npassword;
157     
158     cout<<"请再次输入新密码: ";
159     string check;
160     cin>>check;
161 
162     if(check==npassword)
163     {
164         login->password=npassword;
165         cout<<"--------------------------------------------------------------------------------
";
166         cout<<"                                   修改成功!                                    
";
167         cout<<"--------------------------------------------------------------------------------
";    
168         cout<<"按下1键返回登录...";
169         int num;
170         cin>>num;
171         if(num==1)
172             menuLogin();
173         else 
174             menuexit();
175     }
176     else
177     {
178         cout<<"--------------------------------------------------------------------------------
";
179         cout<<"                                两次输入不一致!                                 
";
180         cout<<"--------------------------------------------------------------------------------
";    
181         cout<<"按下1键返回修改 2键返回登录界面...";
182         int num;
183         cin>>num;
184         if(num==1)
185             menuChange(login);
186         else if(num==2)
187             menulogsuccess(login);
188         else menuexit();
189     }
190 }
191 
192 void menu::menuDelete(AVLnode *login)
193 {
194     cout<<"--------------------------------------------------------------------------------
";
195     cout<<"                                   确认删除？                                   
";
196     cout<<"--------------------------------------------------------------------------------
";    
197     cout<<"按下1键确认 2键返回初始界面...";
198     int num;
199     cin>>num;
200     if(num==1)
201     {
202         tree.remove(login->nodeValue);
203         cout<<"--------------------------------------------------------------------------------
";
204         cout<<"                                   删除成功！                                   
";
205         cout<<"--------------------------------------------------------------------------------
";    
206         cout<<"按下1键返回初始界面...";
207         int n;
208         cin>>n;
209         if(n==1)
210             select();
211         else
212             menuexit();
213     }
214     else if(num==2)
215         select();
216     else menuexit();
217 }
218 
219 void menu::menuexit()
220 {
221     ofstream f;
222     f.open("1.txt");
223     string id,pass;
224 
225     stack<AVLnode*> s;
226     AVLnode *p=tree.getRoot();
227     while(p!=NULL||!s.empty())
228     {
229         while(p!=NULL)
230         {
231             s.push(p);
232             p=p->left;
233         }
234         if(!s.empty())
235         {
236             p=s.top();
237             id=p->nodeValue;
238             pass=p->password;
239             f<<id<<" "<<pass<<"
";
240 
241             s.pop();
242             p=p->right;
243         }
244     }
245     f.flush();
246     f.close();
247     
248 }

menu.cpp

 1 #include "AVLnode.h"
 2 #include "AVLtree.h"
 3 #include "menu.h"
 4 #include <iostream>
 5 using namespace std;
 6 int main()
 7 {
 8 
 9     menu guest;
10     guest.select();
11     return 0;
12 }

main.cpp

  1 // AVLtree.cpp: implementation of the AVLtree class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "AVLtree.h"
  6 
  7 //////////////////////////////////////////////////////////////////////
  8 // Construction/Destruction
  9 //////////////////////////////////////////////////////////////////////
 10 
 11 AVLtree::AVLtree()
 12 {
 13     root=NULL;
 14     treeSize=0;
 15 }
 16 
 17 AVLtree::~AVLtree()
 18 {
 19 }
 20 AVLnode *AVLtree::getRoot()
 21 {
 22     return root;
 23 }
 24 
 25 AVLnode *AVLtree::creatAVLNode (const string item, AVLnode *lptr, AVLnode *rptr, AVLnode *pptr)
 26 {
 27     AVLnode *newNode;
 28     // initialize the data and all pointers
 29     newNode = new AVLnode (item, lptr, rptr, pptr);
 30     return newNode;
 31 }
 32 
 33 void AVLtree::displayTree(int maxCharacters)
 34 {
 35     string label;
 36     int level = 0, column = 0;
 37     int colWidth = maxCharacters + 1;
 38 
 39     int currLevel = 0, currCol = 0;
 40 
 41     if (treeSize == 0)
 42         return;
 43 
 44     tnodeShadow *shadowRoot = buildShadowTree(root, level, column);
 45 
 46     tnodeShadow *currNode;
 47 
 48     queue<tnodeShadow *> q;
 49 
 50     q.push(shadowRoot);
 51   
 52     while(!q.empty())
 53     {
 54         currNode = q.front();
 55         q.pop();
 56 
 57         if (currNode->level > currLevel)
 58         {
 59             currLevel = currNode->level;
 60             currCol = 0;
 61             cout << endl;
 62         }
 63 
 64         if(currNode->left != NULL)
 65             q.push(currNode->left);
 66 
 67         if(currNode->right != NULL)
 68             q.push(currNode->right);
 69 
 70         if (currNode->column > currCol)
 71         {
 72             cout << setw((currNode->column-currCol)*colWidth) << " ";
 73             currCol = currNode->column;
 74         }
 75         cout << setw(colWidth) << currNode->nodeValueStr;
 76         currCol++;
 77     }
 78     cout << endl;
 79 
 80     deleteShadowTree(shadowRoot);
 81 }
 82 
 83 void AVLtree::deleteShadowTree(tnodeShadow *t)
 84 {
 85     if (t != NULL)
 86     {
 87         deleteShadowTree(t->left);
 88         deleteShadowTree(t->right);
 89         delete t;
 90     }
 91 }
 92 
 93 AVLnode *AVLtree::insert(const string &item)
 94 {
 95     AVLnode *t=root,*newnode,*parent=NULL;
 96     while(t!=NULL)
 97     {
 98         parent=t;
 99         if(item==t->nodeValue)
100             return NULL;
101         else if(item<t->nodeValue)
102             t=t->left;
103         else
104             t=t->right;
105     }
106     newnode=creatAVLNode(item,NULL,NULL,parent);
107     if(parent==NULL) 
108         root=newnode;
109     else if(item>parent->nodeValue)
110         parent->right=newnode;
111     else 
112         parent->left=newnode;
113         treeSize++;
114 
115     int bf=0,count=0;
116     AVLnode *cur=newnode,*p=newnode;
117     while(bf>=-1&&bf<=1&&cur!=root)
118     {
119         cur=cur->parent;
120         count++;
121         bf=balanceFactor(cur);
122     }
123 
124     if(bf<-1||bf>1)
125     {
126         if(count==2) ;
127         else
128         {
129             for(int i=0;i<count-2;i++)
130                 p=p->parent;
131         }
132         //all left
133         if(p->nodeValue<p->parent->nodeValue&&p->parent->nodeValue<cur->nodeValue)
134             rightRotate(p->parent);
135         
136         //all right
137         else if(p->nodeValue>p->parent->nodeValue&&p->parent->nodeValue>cur->nodeValue)
138             leftRotate(p->parent);
139         
140         //right left
141         else if(p->nodeValue<p->parent->nodeValue&&p->parent->nodeValue>cur->nodeValue)
142             rightleftRotate(p);
143         //left right 
144         else if(p->nodeValue>p->parent->nodeValue&&p->parent->nodeValue<cur->nodeValue)
145             leftrightRotate(p);
146     }
147     return newnode;
148 }
149 
150 void AVLtree::remove(const string &item)
151 {
152     AVLnode *t=search(item);
153     if(t==NULL) return;
154     
155     //leaf node
156     else if(t->left==NULL&&t->right==NULL)
157     {
158         if(t==root)
159             root=NULL;
160         else if(t->nodeValue>t->parent->nodeValue)
161             t->parent->right=NULL;
162         else 
163             t->parent->left=NULL;
164     }
165     //only left or right
166     else if(t->left==NULL)
167     {
168         if(t==root)
169         {
170             t->right->parent=NULL;
171             root=t->right;
172         }
173         else if(t->nodeValue>t->parent->nodeValue)
174             t->parent->right=t->right;
175         else 
176             t->parent->left=t->right;
177         t->right->parent=t->parent;
178     }
179     else if(t->right==NULL)
180     {
181         if(t==root)
182         {
183             t->left->parent=NULL;
184             root=t->left;
185         }
186         else if(t->nodeValue>t->parent->nodeValue)
187             t->parent->right=t->left;
188         else 
189             t->parent->left=t->left;
190         t->left->parent=t->parent;
191     }
192     //left && right
193     else
194     {
195         AVLnode *r=t;
196         if(t==root)
197         {
198             r=r->right;
199             while(r->left!=NULL)
200                 r=r->left;
201 
202             r->left=t->left;
203             t->left->parent=r;
204             if(r->right==NULL&&r->parent!=root)
205             {
206                 r->right=t->right;
207                 t->right->parent=r;
208                 r->parent->left=NULL;
209             }
210             else if(r->parent!=root)
211             {
212                 r->parent->left=r->right;
213                 r->right->parent=r->parent;
214                 r->right=t->right;
215                 t->right->parent=r;
216             }
217 
218             r->parent=NULL;
219             root=r;
220 
221         }
222 
223         else if(t->nodeValue>t->parent->nodeValue)
224         {
225             r=r->right;
226             while(r->left!=NULL)
227                 r=r->left;
228 
229             if(r->parent!=t)
230             {    
231                 if(r->right==NULL)
232                     r->parent->left=NULL;
233                 else 
234                 {
235                     r->right->parent=r->parent;
236                     r->parent->left=r->right;
237                 }
238     
239                 r->right=t->right;
240                 t->right->parent=r;
241                 
242                 r->parent=t->parent;
243                 t->parent->right=r;
244                 r->left=t->left;
245                 t->left->parent=r;
246             }
247             else
248             {
249                 r->parent=t->parent;
250                 t->parent->right=r;
251                 r->left=t->left;
252                 t->left->parent=r;
253             }
254             
255         }
256         else 
257         {
258             r=r->right;
259             while(r->left!=NULL)
260                 r=r->left;
261 
262             if(r->parent!=t)
263             {    
264                 if(r->right==NULL)
265                     r->parent->left=NULL;
266                 else 
267                 {
268                     r->right->parent=r->parent;
269                     r->parent->left=r->right;
270                 }
271     
272                 r->right=t->right;
273                 t->right->parent=r;
274                 
275                 r->parent=t->parent;
276                 t->parent->left=r;
277                 r->left=t->left;
278                 t->left->parent=r;
279             }
280             else
281             {
282                 r->parent=t->parent;
283                 t->parent->left=r;
284                 r->left=t->left;
285                 t->left->parent=r;
286             }
287             
288         }
289     }
290     treeSize--;
291     delete t;
292 //平衡部分
293 
294 }
295 
296 AVLnode *AVLtree::search(const string &item) const
297 {
298     AVLnode *t=root;
299     while(t!=NULL)
300     {
301         if(t->nodeValue==item) return t;
302         else if(item<t->nodeValue)
303             t=t->left;
304         else t=t->right;
305 
306     }
307     return NULL;
308 }
309 
310 tnodeShadow *AVLtree::buildShadowTree(AVLnode *t, int level, int& column)
311 {            
312     tnodeShadow *newNode = NULL;
313     char text[80];
314     ostrstream ostr(text,80);
315 
316     if (t != NULL)
317     {
318         newNode = new tnodeShadow;
319 
320         tnodeShadow *newLeft = buildShadowTree(t->left, level+1, column);
321         newNode->left = newLeft;
322 
323         ostr << t->nodeValue << ends;
324         newNode->nodeValueStr = text;
325         newNode->level = level;
326         newNode->column = column;
327 
328         column++;
329 
330         tnodeShadow *newRight = buildShadowTree(t->right, level+1, column);
331         newNode->right = newRight;
332     }
333 
334     return newNode;
335 }

AVLtree.cpp

附调试时用的结构化打印树的函数

 1 // tnodeShadow.h: interface for the tnodeShadow class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_TNODESHADOW_H__18034BAE_051F_4D57_91FF_BE10AFD37CDA__INCLUDED_)
 6 #define AFX_TNODESHADOW_H__18034BAE_051F_4D57_91FF_BE10AFD37CDA__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 #include <iomanip>        // for setw()
13 #include <strstream>        // for format conversion
14 #include <string>            // node data formatted as a string
15 #include <queue>
16 #include <utility>
17 
18 using namespace std;
19 
20 class tnodeShadow
21 {
22     public:
23         string nodeValueStr;    // formatted node value
24         int level,column;
25         tnodeShadow *left, *right;
26         
27         tnodeShadow ()
28         {}
29 };
30 #endif // !defined(AFX_TNODESHADOW_H__18034BAE_051F_4D57_91FF_BE10AFD37CDA__INCLUDED_)

tnodeShadow.h

第一次写这么完整的程序运行的一刻真的好爽！