二叉搜索树

it2024-10-14 15

对应HDU3791

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <cassert> #include <set> #include <sstream> #include <map> using namespace std ; #ifdef DeBUG #define bug assert #else #define bug // #endif #define zero {0} #define INF 2000000000 #define eps 1e-6 typedef struct _Node //二叉树类，n保存变量 { int n; struct _Node *lf; struct _Node *rt; } Node,*pNode; //定义pNode 为指针变量 int cmp(pNode a,pNode b)//两棵二叉树的比较，传入根节点，相同为1，不同为0 { if(!a||!b) { if(a==b) return 1; else return 0; } if(a->n!=b->n)return 0; if(!cmp(a->lf,b->lf)) return 0; if(!cmp(a->rt,b->rt)) return 0; return 1; } void insert(pNode h,int e)//建树，e为变量 { if(e<h->n) { if(h->lf==0) { h->lf=(pNode)malloc(sizeof(Node)); h->lf->n=e; h->lf->lf=h->lf->rt=0; } else insert(h->lf,e); } else { if(h->rt==0) { h->rt=(pNode)malloc(sizeof(Node)); h->rt->n=e; h->rt->lf=h->rt->rt=0; } else insert(h->rt,e); } } void del(pNode h)//删除一棵 { if(!h)return ; del(h->lf); del(h->rt); free(h); } int main() { #ifdef DeBUG freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif int i,j,n,l,ll; char seq[11]; Node tgt,src; while(scanf("%d",&n),n) { getchar(); gets(seq); l=strlen(seq); src.n=seq[0]-48;//根节点的初始化 src.lf=src.rt=0;//左右初始化为0 for(i=1; i<l; i++) insert(&src,seq[i]-48); for(i=0; i<n; i++) { gets(seq); ll=strlen(seq); if(ll!=l) break; tgt.n=seq[0]-48; tgt.lf=tgt.rt=0; for(j=1; j<ll; j++) insert(&tgt,seq[j]-48); if(cmp(&src,&tgt)) printf("YES\n"); else printf("NO\n"); del(tgt.lf); del(tgt.rt); } del(src.lf);//注意删除格式 del(src.rt); } return 0; } View Code

模板

typedef struct _Node //二叉树类，n保存变量 { int n; struct _Node *lf; struct _Node *rt; } Node,*pNode; //定义pNode 为指针变量 int cmp(pNode a,pNode b)//两棵二叉树的比较，传入根节点，相同为1，不同为0 { if(!a||!b) { if(a==b) return 1; else return 0; } if(a->n!=b->n)return 0; if(!cmp(a->lf,b->lf)) return 0; if(!cmp(a->rt,b->rt)) return 0; return 1; } void insert(pNode h,int e)//建树，e为变量 { if(e<h->n) { if(h->lf==0) { h->lf=(pNode)malloc(sizeof(Node)); h->lf->n=e; h->lf->lf=h->lf->rt=0; } else insert(h->lf,e); } else { if(h->rt==0) { h->rt=(pNode)malloc(sizeof(Node)); h->rt->n=e; h->rt->lf=h->rt->rt=0; } else insert(h->rt,e); } } void del(pNode h)//删除一棵 { if(!h)return ; del(h->lf); del(h->rt); free(h); } int main() { Node tgt,src; src.n=x;//根节点的初始化 src.lf=src.rt=0;//左右初始化为0 insert(&src,变量); tgt.n=y; tgt.lf=tgt.rt=0; insert(&tgt,变量); if(cmp(&src,&tgt)) printf("YES\n"); else printf("NO\n"); del(tgt.lf); del(tgt.rt); del(src.lf);//注意删除格式 del(src.rt); return 0; } View Code

二叉树类

作者http://blog.csdn.net/qq276592716/article/details/7402040

1 #include <iostream.h> 2 #define max 10 3 struct BinTreeNode //二叉查找树的节点结构体 4 { 5 int m_data; 6 struct BinTreeNode *lchild, *rchild; 7 BinTreeNode(int item, BinTreeNode *left = NULL, BinTreeNode *right = NULL) 8 : m_data(item), lchild(left), rchild(right) //构造函数默认的lchild,rchild为NULL 9 { 10 } 11 }; 12 13 class BinaryTree //二叉搜索树类 14 { 15 16 private: 17 BinTreeNode *root; //根节点指针 18 19 public: 20 BinaryTree() 21 { 22 root = NULL; 23 } 24 25 //迭带插入的方法建二叉搜索树 26 void Insert(const int node) 27 { 28 BinTreeNode *currentpointer; //当前节点指针 29 BinTreeNode *parentpointer; //父亲节点指针 30 BinTreeNode *newpointer; 31 //ptr必须为根节点指针的引用 32 BinTreeNode *ptr = root; 33 newpointer = new BinTreeNode(node); //新动态分配一个节点 34 35 if(root == NULL) //如果此时树为空，返回新开辟的节点 36 { 37 root = newpointer; 38 } 39 else 40 { 41 currentpointer = ptr; //保存root指针 42 //一直移动到是使parentpointer指向叶子节点而currentpointer为NULL 43 while(currentpointer != NULL) //当当前节点不为空的情况下 44 { 45 parentpointer = currentpointer; //用指向父亲节点的指针保存当前指针 46 47 if(currentpointer->m_data > node) 48 { 49 currentpointer = currentpointer->lchild; 50 } 51 else 52 { 53 currentpointer = currentpointer->rchild; 54 } 55 } 56 //以下是将节点插入 57 if(parentpointer->m_data > node) 58 { 59 parentpointer->lchild = newpointer; 60 } 61 else 62 { 63 parentpointer->rchild = newpointer; 64 } 65 } 66 } 67 68 //创建方法，依次插入 69 BinTreeNode *Creat(int data[],int len) 70 { 71 for(int i=0; i<len; i++) 72 { 73 Insert(data[i]); 74 } 75 return root; 76 } 77 78 void PreOrder() 79 { 80 cout<<"前序遍历的结果为："; 81 PrePrint(root); 82 } 83 84 void InOrder() 85 { 86 cout<<"中序遍历的结果为："; 87 InPrint(root); 88 } 89 90 void PostOrder() 91 { 92 cout<<"后序遍历的结果为："; 93 PostPrint(root); 94 } 95 96 void Count() 97 { 98 cout<<endl; 99 cout<<"叶子节点数为："<<CountLeafs(root)<<endl; 100 } 101 102 void PrePrint(BinTreeNode *p) //前序遍历 103 { 104 if(p != NULL) 105 { 106 cout << p->m_data << ','; 107 PrePrint(p->lchild); 108 PrePrint(p->rchild); 109 } 110 } 111 112 void InPrint(BinTreeNode *p) //中序遍历 113 { 114 if(p != NULL) 115 { 116 InPrint(p->lchild); 117 cout<< p->m_data<<','; 118 InPrint(p->rchild); 119 } 120 } 121 122 123 void PostPrint(BinTreeNode *p) //后序遍历 124 { 125 if(p != NULL) 126 { 127 PostPrint(p->lchild); 128 PostPrint(p->rchild); 129 cout<< p->m_data<< ','; 130 } 131 } 132 133 BinTreeNode * Find(const int &c) //用迭带的方法寻找特定的节点 134 { 135 BinTreeNode *pCurrent = root; 136 if(pCurrent != NULL) 137 { 138 while(pCurrent != NULL) 139 { 140 if(pCurrent->m_data == c) 141 { 142 return pCurrent; 143 } 144 else 145 { 146 if(c > pCurrent->m_data) 147 pCurrent = pCurrent->rchild; 148 else 149 pCurrent = pCurrent ->lchild; 150 } 151 } 152 } 153 return NULL; 154 } 155 156 bool DeleteBT(const int &key) //删除节点的函数定义 157 { 158 BinTreeNode *q, *s; 159 BinTreeNode *current = root; //找到要删除的节点 160 BinTreeNode *prt = NULL; //current的父亲节点 161 162 while ((NULL != current) && (current->m_data != key)) 163 //通过查找找到值为key的节点和它的父亲节点 164 { 165 prt = current; 166 167 if (current->m_data > key) 168 current = current->lchild; 169 else 170 current = current->rchild; 171 } 172 173 if(current == NULL) //current为NULL说明节点不存在 174 { 175 cout<<"没有此节点!"<<endl; 176 return false; 177 } 178 if(current->lchild == NULL && current->rchild == NULL) 179 //当找到的节点即没有左孩子也没有右孩子 180 { 181 if(current == root) 182 { 183 root = NULL; 184 } 185 else 186 { 187 if(current == prt->lchild) 188 { 189 prt->lchild = NULL; 190 } 191 else 192 { 193 prt->rchild = NULL; 194 } 195 } 196 } 197 if(current->lchild == NULL && current->rchild != NULL) 198 //当找到的节点有右孩子而没有左孩子 199 { 200 if(current == root) 201 { 202 current = current->rchild; 203 } 204 else 205 { 206 if(current == prt->lchild) //如果当前节点是prt指向节点的左孩子 207 { 208 prt->lchild = current->rchild; 209 } 210 else 211 { 212 prt->rchild = current->rchild; 213 } 214 } 215 } 216 if(current->rchild == NULL && current->lchild != NULL) 217 //如果当前节点有左孩子而没有右孩子 218 { 219 if(current == root) 220 { 221 current = current->lchild; 222 } 223 else 224 { 225 if(current == prt->lchild) 226 { 227 prt->lchild = current->lchild; 228 } 229 else 230 { 231 prt->rchild = current->lchild; 232 } 233 } 234 } 235 236 if(current ->lchild != NULL && current->rchild != NULL)//当前节点左右孩子都有 237 { 238 q = current; //用q保存current节点指针 239 s = current; //s是current的前驱指针 240 241 current = current->lchild; 242 //先向左走 243 while(current->rchild) //然后向右走到尽头，其实就是寻找左子树当中最大的节点 244 { //补充：寻找右子树当中最小的节点也是可以的 245 s = current; //s指向current的前驱 246 current = current->rchild; 247 } 248 249 q->m_data = current->m_data; //用找到的节点替换当前节点 250 251 if(q != s) //将current节点从树中拆下来 252 s->rchild = current->lchild; 253 else 254 q->lchild = current->lchild; 255 } 256 delete current; //释放current指向的空间 257 current = NULL; 258 return true; 259 } 260 261 void destroy(BinTreeNode *current) //销毁二叉树 262 { 263 if(current != NULL) 264 { 265 destroy(current->lchild); 266 destroy(current->rchild); 267 delete current; 268 current = NULL; 269 } 270 } 271 272 int CountLeafs(BinTreeNode *current) 273 { 274 if(current == NULL) 275 { 276 return 0; 277 } 278 else 279 { 280 if( current->lchild == NULL && current->rchild == NULL ) 281 { 282 return 1; 283 } 284 else 285 { 286 int num1 = CountLeafs(current->lchild); 287 int num2 = CountLeafs(current->rchild); 288 return (num1+num2); 289 } 290 } 291 } 292 293 virtual ~BinaryTree() 294 { 295 destroy(root); 296 } 297 }; 298 void main() 299 { 300 BinaryTree myTree; 301 int a[]={6, 3, 4, 7, 8, 2, 5, 9, 0, 1}; 302 //输出 303 cout<<"(1)输出部分:"<<endl; 304 myTree.Creat(a, max); //创建二叉搜索树 305 myTree.PreOrder(); //先序遍历 306 cout<<endl; 307 myTree.InOrder(); //中序遍历 308 cout<<endl; 309 myTree.PostOrder(); //后序遍历 310 cout<<endl<<endl; 311 //插入 312 cout<<"(2)插入部分:"<<endl; 313 int x; 314 cout<<"输入你想要插入的节点:"; 315 cin>>x; 316 myTree.Insert(x); 317 myTree.InOrder(); //中序遍历 318 cout<<endl<<endl; 319 320 //删除 321 cout<<"(3)删除部分:"<<endl; 322 cout<<"输入一个你想删除的节点: "; 323 cin>>x; 324 if(myTree.DeleteBT(x)) //进行删除 325 cout<<"删除成功!"<<endl; 326 else 327 cout<<"删除失败!"<<endl; 328 myTree.InOrder(); //中序遍历 329 cout<<endl<<endl; 330 331 //查询 332 cout<<"(4)查询部分:"<<endl; 333 cout<<"输入你想要找的节点"; 334 cin>>x; 335 if(myTree.Find(x)) //进行查找 336 cout<<"查找成功!"<<endl; 337 else 338 cout<<"查找失败!"<<endl; 339 } View Code

自写二叉排序树

1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 using namespace std; 5 #define MAX 10 6 struct BinTreeNode 7 { 8 int m_data; 9 BinTreeNode *lchild,*rchild; 10 BinTreeNode(int item,BinTreeNode *left=NULL,BinTreeNode *right=NULL) 11 :m_data(item),lchild(left),rchild(right) {} 12 }; 13 class BinaryTree 14 { 15 private: 16 BinTreeNode *root; 17 public: 18 BinaryTree() 19 { 20 root=NULL; 21 } 22 BinTreeNode *GetRoot() 23 { 24 return root; 25 } 26 void Insert(const int node) 27 { 28 BinTreeNode *currentpointer; 29 BinTreeNode *parentpointer; 30 BinTreeNode *newpointer; 31 BinTreeNode *ptr = root; 32 newpointer = new BinTreeNode(node); 33 if(root==NULL) 34 { 35 root=newpointer; 36 } 37 else 38 { 39 currentpointer=ptr; 40 while(currentpointer!=NULL) 41 { 42 parentpointer=currentpointer; 43 if(currentpointer->m_data>node) 44 { 45 currentpointer=currentpointer->lchild; 46 } 47 else 48 { 49 currentpointer=currentpointer->rchild; 50 } 51 } 52 if(parentpointer->m_data>node) 53 { 54 parentpointer->lchild=newpointer; 55 } 56 else 57 { 58 parentpointer->rchild=newpointer; 59 } 60 } 61 } 62 BinTreeNode *Creat(int data[],int len) 63 { 64 for(int i=0; i<len; i++) 65 { 66 Insert(data[i]); 67 } 68 return root; 69 } 70 void PreOrder(BinTreeNode *p) 71 { 72 if(p!=NULL) 73 { 74 cout<<p->m_data<<','; 75 PreOrder(p->lchild); 76 PreOrder(p->rchild); 77 } 78 } 79 void PreOrder2(BinTreeNode *p)//非递归版 80 { 81 stack<BinTreeNode*>S; 82 S.push(p); 83 while(!S.empty()) 84 { 85 p=S.top(); 86 while(p) 87 { 88 cout<<p->m_data<<','; 89 S.push(p->lchild); 90 p=p->lchild; 91 } 92 S.pop(); 93 if(!S.empty()) 94 { 95 p=S.top(); 96 S.pop(); 97 S.push(p->rchild); 98 } 99 } 100 101 } 102 void InOrder(BinTreeNode *p) 103 { 104 if(p!=NULL) 105 { 106 InOrder(p->lchild); 107 cout<<p->m_data<<','; 108 InOrder(p->rchild); 109 } 110 } 111 void InOrder2(BinTreeNode *p)//非递归版 112 { 113 stack<BinTreeNode*>S; 114 S.push(p); 115 while(!S.empty()) 116 { 117 p=S.top(); 118 while(p) 119 { 120 S.push(p->lchild); 121 p=p->lchild; 122 } 123 S.pop(); 124 if(!S.empty()) 125 { 126 p=S.top(); 127 S.pop(); 128 cout<<p->m_data<<','; 129 S.push(p->rchild); 130 } 131 } 132 133 } 134 void PostOrder(BinTreeNode *p) 135 { 136 if(p!=NULL) 137 { 138 PostOrder(p->lchild); 139 PostOrder(p->rchild); 140 cout<<p->m_data<<','; 141 } 142 } 143 void layerOrder(BinTreeNode *p) 144 { 145 if(p!=NULL) 146 { 147 queue<BinTreeNode *>st; 148 st.push(p); 149 while(!st.empty()) 150 { 151 BinTreeNode*now=st.front(); 152 st.pop(); 153 cout<<now->m_data<<','; 154 if(now->lchild!=NULL) 155 { 156 st.push(now->lchild); 157 } 158 if(now->rchild!=NULL) 159 { 160 st.push(now->rchild); 161 } 162 } 163 } 164 } 165 BinTreeNode *Find(const int &c) 166 { 167 BinTreeNode *pCurrent =root; 168 if(pCurrent!=NULL) 169 { 170 while(pCurrent!=NULL) 171 { 172 if(pCurrent->m_data==c) 173 { 174 return pCurrent; 175 } 176 else 177 { 178 if(c > pCurrent->m_data) 179 pCurrent=pCurrent->rchild; 180 else 181 pCurrent=pCurrent->lchild; 182 } 183 } 184 } 185 return NULL; 186 } 187 bool DeleteBT(const int &key) 188 { 189 BinTreeNode *q,*s; 190 BinTreeNode *current=root; 191 BinTreeNode *prt=NULL; 192 while((NULL!=current)&&(current->m_data!=key)) 193 { 194 prt=current; 195 if(current->m_data>key) 196 current=current->lchild; 197 else 198 current=current->rchild; 199 } 200 if(current==NULL) 201 { 202 cout<<"没有此节点"<<endl; 203 return false; 204 } 205 //删除叶子节点 206 if(current->lchild==NULL&&current->rchild==NULL) 207 { 208 if(current==root) 209 { 210 root=NULL; 211 } 212 else 213 { 214 if(current==prt->lchild) 215 { 216 prt->lchild=NULL; 217 } 218 else 219 { 220 prt->rchild=NULL; 221 } 222 } 223 } 224 //右边有人 225 if(current->lchild==NULL&&current->rchild!=NULL) 226 { 227 if(current==root) 228 { 229 current=current->rchild; 230 } 231 else 232 { 233 if(current==prt->lchild) 234 { 235 prt->lchild=current->rchild; 236 } 237 else 238 { 239 prt->rchild=current->rchild; 240 } 241 } 242 } 243 //左边有人 244 if(current->rchild==NULL&&current->lchild!=NULL) 245 { 246 if(current==root) 247 { 248 current=current->lchild; 249 } 250 else 251 { 252 if(current==prt->lchild) 253 { 254 prt->lchild=current->lchild; 255 } 256 else 257 { 258 prt->rchild=current->lchild; 259 } 260 } 261 } 262 //两边都有人 263 if(current->lchild!=NULL&&current->rchild!=NULL) 264 { 265 q=current; 266 s=current; 267 current=current->lchild; 268 while(current->rchild) 269 { 270 s=current; 271 current=current->rchild; 272 } 273 q->m_data=current->m_data; 274 if(q!=s) 275 s->rchild=current->lchild; 276 else 277 q->lchild=current->lchild; 278 } 279 delete current; 280 current=NULL; 281 return true; 282 } 283 void destroy(BinTreeNode *current) 284 { 285 if(current!=NULL) 286 { 287 destroy(current->lchild); 288 destroy(current->rchild); 289 delete current; 290 current = NULL; 291 } 292 } 293 ~BinaryTree() 294 { 295 destroy(root); 296 } 297 int CountLeafs(BinTreeNode *current)//叶子节点 298 { 299 if(current==NULL) 300 { 301 return 0; 302 } 303 else 304 { 305 if(current->rchild==NULL&&current->rchild==NULL) 306 { 307 return 1; 308 } 309 else 310 { 311 int num1=CountLeafs(current->lchild); 312 int num2=CountLeafs(current->rchild); 313 return num1+num2; 314 } 315 } 316 } 317 318 int Depth(BinTreeNode *current)//深度 319 { 320 int Depthleft; 321 int Depthright; 322 int dp=0; 323 if(current==NULL) 324 { 325 return 0; 326 } 327 else 328 { 329 Depthleft=Depth(current->lchild); 330 Depthright=Depth(current->rchild); 331 dp=1+(Depthright>=Depthleft ? Depthright:Depthleft); 332 } 333 return dp; 334 } 335 BinTreeNode *Copy(BinTreeNode *tree) 336 { 337 BinTreeNode *pleft; 338 BinTreeNode *pright; 339 if(!tree) 340 { 341 return NULL; 342 } 343 if(tree->lchild!=NULL) 344 { 345 pleft=Copy(tree->lchild); 346 } 347 else 348 { 349 pleft=NULL; 350 } 351 if(tree->rchild!=NULL) 352 { 353 pright=Copy(tree->rchild); 354 } 355 else 356 { 357 pright=NULL; 358 } 359 BinTreeNode *cptree=new BinTreeNode(tree->m_data,pleft,pright); 360 root=cptree; 361 return cptree; 362 } 363 }; 364 int main() 365 { 366 BinaryTree myTree; 367 int a[]= {6, 3, 4, 7, 8, 2, 5, 9, 0, 1}; 368 /* 369 6 370 / \ 371 3 7 372 / \ \ 373 2 4 8 374 / \ \ 375 0 5 9 376 \ 377 1 378 */ 379 myTree.Creat(a, MAX); //创建二叉搜索树 380 cout<<"先序遍历";myTree.PreOrder(myTree.GetRoot());cout<<endl; 381 cout<<"中序遍历";myTree.InOrder(myTree.GetRoot());cout<<endl; 382 cout<<"后序遍历";myTree.PostOrder(myTree.GetRoot());cout<<endl; 383 cout<<"层序遍历";myTree.layerOrder(myTree.GetRoot());cout<<endl; 384 385 cout<<"非递归先序遍历";myTree.PreOrder2(myTree.GetRoot());cout<<endl; 386 cout<<"非递归中序遍历";myTree.InOrder2(myTree.GetRoot());cout<<endl; 387 388 cout<<"树深度";cout<<myTree.Depth(myTree.GetRoot())<<endl; 389 cout<<"叶子节点数";cout<<myTree.CountLeafs(myTree.GetRoot())<<endl; 390 BinaryTree copyTree;//新建复制树 391 copyTree.Copy(myTree.GetRoot()); 392 cout<<"复制树先序遍历";copyTree.PreOrder(copyTree.GetRoot()); 393 cout<<"复制树深度"<<copyTree.Depth(copyTree.GetRoot())<<endl; 394 } View Code

转载于:https://www.cnblogs.com/Skyxj/p/3236793.html

相关资源：二叉搜索树的c++实现

最新回复(0)