您的位置: 首页 > IT文章 > 数据结构大型实验的记录(done)

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

分类: IT文章 • 2025-02-02 11:51:25

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

基本思路：

　　类：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 }

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 }

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 }

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_)

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

相关推荐