树系列之BST树 数据结构 完整源码

#include <algorithm> #include <stdlib.h> #include <time.h> #include "BST.h" // 测试类, 用于测试BST是否合法 template <class T> class TestBST { public : bool operator () (const BST<T>& bst) { BST<T>::PBST_NODE root = bst.GetRoot(); if (!Check(root)) { InOrder(root); return false; } //cout << "Congratulation!" << endl; return true; } // 中序遍历 void InOrder(BST<T>::PBST_NODE root) { if (!root) return; InOrder(root->left); cout << root->key << "\t"; InOrder(root->right); } bool Check(BST<T>::PBST_NODE root) { if (!root) return true; // 键值是否合法 if ((root->left && root->key < root->left->key)) { cout << "Left Child Key Invalid!" << endl; return false; } if ((root->right && root->key > root->right->key)) { cout << "Right Child Key Invalid!" << endl; return false; } int ln = (root->left ? root->left->n: 0); int rn = (root->right? root->right->n: 0); // 节点数是否合法 if (root->n != (ln + rn + 1)) { cout << "Number Of Node Invalid!" << endl; return false; } // 递归测试 if (!Check(root->left) || !Check(root->right)) return false; return true; } }; const int MAXN = 2000; int arr[MAXN + 100]; int mark[MAXN + 100]; // 随机输入 MAXN 个不同的数在区间[1, MAXN]里 int Rand() { int i; for (i = 1; i <= MAXN; ++i) arr[i] = i; srand(time(NULL)); for (i = 1; i <= MAXN; ++i) { int rnd = i + rand() % (MAXN - i + 1); //rand() % MAXN + 1; int t = arr[i]; arr[i] = arr[rnd]; arr[rnd] = t; } return 0; } int Successor(const BST<int>& bst, int key) { BST<int>::PBST_NODE node = bst.Find(key); node = bst.Successor(node); if (!node) { cout << "No Successor!" << endl; return 0; } return node->key; } int Vanguard(const BST<int>& bst, int key) { BST<int>::PBST_NODE node = bst.Find(key); node = bst.Vanguard(node); if (!node) { cout << "No Vanguard!" << endl; return 0; } return node->key; } int main() { BST<int> bsts; BST<int> bstn; TestBST<int> func; int i; memset(mark, 0, sizeof(mark)); //srand(time(NULL)); //int rnd; cout << "******* Insert ********" << endl; Rand(); for (i = 1; i <= MAXN; ++i) { //rnd = rand() % MAXN + 1; //cout << rnd << "\t"; //scanf("%d", &rnd); //arr[i] = rnd; //++mark[rnd]; bsts.InsertSpecial(arr[i]); bstn.InsertNormal(arr[i]); //bst.InsertNormal(rnd); } func(bsts); func(bstn); sort(arr + 1, arr + MAXN + 1); cout << "***** SelectKth *****\n"; Successor(bsts, arr[MAXN]); Successor(bstn, arr[MAXN]); Vanguard(bsts, arr[1]); Vanguard(bstn, arr[1]); for (i = 2; i < MAXN; ++i) { if (Successor(bsts, arr[i]) != arr[i + 1] || Successor(bstn, arr[i]) != arr[i + 1]) { cout << "Successor Error!" << endl; } if (Vanguard(bsts, arr[i]) != arr[i - 1] || Vanguard(bstn, arr[i]) != arr[i - 1]) { cout << "Vanguard Error!" << endl; } } /* //func(bsts); //func(bstn); cout << endl << "*********" << endl; cout << "****** Remove ******" << endl; for (i = 1; i <= MAXN; ++i) { int c1 = bsts.Count(arr[i]); if (mark[arr[i]] != c1) cout << "Special Erase Error!" << endl; bsts.EraseSpecial(arr[i]); //bstn.EraseNormal(arr[i]); --mark[arr[i]]; func(bsts); //func.InOrder(bsts.GetRoot()); //cout << "\n******" << endl; //func(bstn); } */ /* for (i = 1; i <= MAXN; ++i) { int c1 = bsts.Count(arr[i]); if (c1 != mark[arr[i]]) { cout << "Special Insert Error!" << endl; } int c2 = bstn.Count(arr[i]); if (c2 != mark[arr[i]]) { cout << "Normal Insert Error!" << endl; } } */ return 0; }