查找算法代码C++——包括顺序、二分、BST、哈希

/**** * BinarySortTree. * ****/ #include "Global.h" #include <iostream> using namespace std; //BinarySortTree //insert operation BinTree Insert_BinaryTree(BinTree bt, KeyType key) { if(bt == 0) { bt = new BitNode; bt->elem = key; bt->leftchild = 0; bt->rightchild = 0; return bt; } if(key < bt->elem) bt->leftchild = Insert_BinaryTree(bt->leftchild, key); else bt->rightchild = Insert_BinaryTree(bt->rightchild,key); return bt; } //Binary sort tree search algorithm BitNode* Search_BinaryTree(BinTree bt, KeyType key) { if(bt == 0) return 0; if(key == bt->elem) return bt; if(key < bt->elem) return Search_BinaryTree(bt->leftchild, key); else return Search_BinaryTree(bt->rightchild, key); } //another search algorithm int Search_BinaryTree(BinTree bt, KeyType key, BitNode** p, BitNode** pf) { //pf is the pointer which point to the parent. *p = bt; *pf = 0; while(*p != 0) { if(key == (*p)->elem) return 1; if(key < (*p)->elem) { *pf = *p; *p = (*p)->leftchild; } else { *pf = *p; *p = (*p)->rightchild; } } return 0; } //BinarySortTree //Delete Operation int Delete_BinaryTree(BinTree *bt, KeyType key) { BitNode* p = *bt; BitNode* pf = 0; // pf is the parent of the p. int findflag; //whether find or not. if(*bt == 0) return 0; // tree is null. findflag = Search_BinaryTree(*bt, key, &p, &pf); if(findflag == 0) return 0; // no match. //--------------------------------------------- //You need to delete a node that have no child. if(p->leftchild == 0 && p->rightchild == 0) { if(pf == 0) // delete the root node. { delete bt; bt = 0; return 1; } if(p == pf->leftchild) pf->leftchild = 0; else pf->rightchild = 0; delete p; return 1; } //--------------------------------------------- //--------------------------------------------- //You need to delete a node that have one child if(p->leftchild == 0) // left child is null. { if(pf == 0) //delete the root node. { *bt = p->rightchild; delete p; return 1; } if(p == pf->leftchild) pf->leftchild = p->rightchild; else pf->rightchild = p->rightchild; delete p; return 1; } if(p->rightchild == 0) // right child is null. { if(pf == 0) // delete the root node. { *bt = p->leftchild; delete p; return 1; } if(p == pf->leftchild) pf->leftchild = p->leftchild; else pf->rightchild = p->leftchild; delete p; return 1; } //--------------------------------------------- //--------------------------------------------- //You need to delete a node that have two child BitNode* prf = p; BitNode* pr = p->rightchild; while(pr->leftchild != 0) { prf = pr; pr = pr->leftchild; } p->elem = pr->elem; //replace if(prf == p) prf->rightchild = pr->rightchild; else prf->leftchild = pr->rightchild; delete pr; return 1; } //test function int main() { int a[10] = {12, 52, 65, 84, 63, 14, 68, 69, 99,77}; // initialization and creat the Binary Sort Tree. BinTree bt = 0; for(int i = 0; i < 10; i++) { bt = Insert_BinaryTree(bt, a[i]); } //search start. cout << Search_BinaryTree(bt,14) << endl; cout << Search_BinaryTree(bt,55) << endl; //delete start. cout << Delete_BinaryTree(&bt,14) << endl; //search 14 again. cout << Search_BinaryTree(bt,14) << endl; return 0; }