数据结构|二叉排序/搜索树类模板数据结构|链表|面向对象编程

二叉排序树类模板

- 模板类
- 测试
- 主函数调用

模板类将整个二叉排序树封装为一个模板类
刚开始用静态变量当函数参数默认参数，但所有对象共用一个变量就没办法保存多个树的root了。解决办法是：把递归的函数设为私有函数。然后用一个公用的函数去调用这个函数，同时给这个函数传值。这样用户就可以直接调用函数，而不需要传任何值。

#include #include #include using namespace std; template //luosansui class TreeNode { public: T value; TreeNode* left; TreeNode* right; TreeNode(const T& value) { this->value = https://www.it610.com/article/value; left = NULL; right = NULL; } }; //默认比较规则 class Compare { public: bool operator()(int a, int b) { return a < b; } bool operator()(char a, char b) { return a < b; } bool operator()(float a, float b) { return a < b; } bool operator()(double a, double b) { return a < b; } }; template //二叉查找树 class BinarySortTree { private: TreeNode* root; TreeNode* nullp; Tclass compare; //记录节点数目 int node_num; //查找 TreeNode*& _findData(const T& node_value, TreeNode*& node) { if (node == NULL) { return nullp; } else if (node_value =https://www.it610.com/article/= node->value) { return node; } if (!compare(node_value, node->value)) { return _findData(node_value, node->right); } else { return _findData(node_value, node->left); } } //析构用的遍历 void _destruct(TreeNode*& node) { if (node == NULL)return; _destruct(node->left); _destruct(node->right); delete node; } //打印 void _print(TreeNode*& node) { if (node == NULL)return; _print(node->left); cout << node->value << " "; _print(node->right); } public: //构造 BinarySortTree() { nullp = NULL; root = NULL; node_num = 0; } //析构 ~BinarySortTree() { _destruct(root); } //插入 bool insert(const T& node_value) { node_num++; if (root == NULL) { root = new TreeNode(node_value); return true; } else { TreeNode* tempNode = root; while (1) { if (node_value =https://www.it610.com/article/= tempNode->value) { cout << "数据重复，已忽略" << endl; node_num--; return false; } if (!compare(node_value, tempNode->value)) { if (tempNode->right != NULL) { tempNode = tempNode->right; } else { tempNode->right = new TreeNode(node_value); return true; } } else if (compare(node_value, tempNode->value)) { if (tempNode->left != NULL) { tempNode = tempNode->left; } else { tempNode->left = new TreeNode(node_value); return true; } } } } } //插入数组 bool insert(const T arr[], int n) { for (int i = 0; i < n; i++) { insert(arr[i]); } return true; } //删除 bool erase(const T& node_value) { TreeNode*& temp = _findData(node_value, root); if (temp == NULL) { cout << "无数据可删除" << endl; return false; } else { node_num--; if (temp->left == NULL && temp->right != NULL) {//仅左空 TreeNode* temp_temp = temp; temp = temp->right; delete temp_temp; } else if (temp->left != NULL && temp->right == NULL) {//仅右空 TreeNode* temp_temp = temp; temp = temp->left; delete temp_temp; } else if (temp->left != NULL && temp->right != NULL) {//无空 //内容有误，已更正，以下为原内容，没考虑指针方向。 /*TreeNode* temp_temp = temp; TreeNode* temp_tem_s = temp->right; while (temp_tem_s->left != NULL) { temp_tem_s = temp_tem_s->left; } temp = temp_tem_s; temp->left = temp_temp->left; delete temp_temp; */ TreeNode* temp_tem_s_f = temp; TreeNode* temp_tem_s = temp->right; int flag = 0; while (temp_tem_s->left != NULL) { temp_tem_s_f = temp_tem_s; temp_tem_s = temp_tem_s->left; flag = 1; } temp->value = https://www.it610.com/article/temp_tem_s->value; if (flag == 1) { temp_tem_s_f->left = NULL; }else { temp_tem_s_f->right = temp_tem_s->right; } delete temp_tem_s; } else { delete temp; temp = NULL; } cout << "数据已删除" << endl; return true; } } //获取节点总数 int getNodeNum() { return node_num; } //获取ASL，广度优先遍历求每层元素个数 int getASL() { TreeNode* node = root; if (node == NULL)return 0; vector layer; queue*> que_bfs_1; queue*> que_bfs_2; que_bfs_1.push(root); while (!que_bfs_1.empty() || !que_bfs_2.empty()) { queue*>& temp_que_1 = !que_bfs_1.empty() ? que_bfs_1 : que_bfs_2; queue*>& temp_que_2 = temp_que_1 == que_bfs_1 ? que_bfs_2 : que_bfs_1; layer.push_back((int)temp_que_1.size()); while (!temp_que_1.empty()) { if (temp_que_1.front()->left != NULL) { temp_que_2.push(temp_que_1.front()->left); } if (temp_que_1.front()->right != NULL) { temp_que_2.push(temp_que_1.front()->right); } temp_que_1.pop(); } } int ave_num = 0; int i = 1; for (vector::iterator it = layer.begin(); it != layer.end(); it++) { ave_num += i * (*it); i++; } return ave_num / getNodeNum(); } //打印 void print() { _print(root); } //查找 bool find(const T& node_value) { return _findData(node_value, root); } };

测试二叉树放入对象时应重写比较规则，同时还要重写搜索规则，a为搜索的数据，b是待搜索数据，重载输出就不多说了

//以下均为测试 class person { public: char name; int age; person() { name = 'A'; age = 0; } person(char a, int b) :name(a), age(b) {} }; //重写比较规则 class comp { public: bool operator()(person a, person b) { return a.age > b.age; } }; //重写搜索规则，a为搜索的数据，b代搜索数据 bool operator== (person a, person b) { return a.age == b.age; } //重载输出 ostream& operator<<(ostream& out, person p) { cout << p.name << p.age; return out; }

主函数调用

定义：BinarySortTree<类型> 插入：insert() 插入数组：insert(arr,n) //n为数组长度打印：print() 删除：erase() 查找：find() 获取平均查找长度： getASL() 获取结点总数：getNodeNum()

int main() { //测试 BinarySortTree tree; int arr[] = { 100,99,101,103 }; int n = sizeof(arr) / sizeof(arr[0]); tree.insert(3); tree.insert(arr, n); tree.print(); cout << endl << "总结点数" << tree.getNodeNum() << endl; ; if (tree.find(1)) { cout << "1 找到" << endl; } else { cout << "1 未找到" << endl; } tree.erase(99); tree.insert(arr, n); tree.print(); cout << "平均查找长度: " << tree.getASL(); cout << endl << "--------" << endl; BinarySortTree T; T.insert('A'); T.insert('C'); if (T.find('A')) { cout << "A 找到" << endl; } else { cout << "A 未找到" << endl; } T.print(); cout << endl << "--------" << endl; BinarySortTree per; person luo01('a', 20); person luo02('w', 10); person arrper[5] = { {'w',55},{'w',25},{'w',95},{'w',2},{'w',25} }; per.insert(luo01); per.insert(luo02); per.insert(luo02); per.insert(arrper,5); if (per.find(luo02)) { cout << "person找到" << endl; } else { cout << "person未找到" << endl; } per.print(); cout << endl << "--------" << endl; tree.print(); cout << endl; T.print(); cout << endl; per.print(); cout << endl; return 0; }

【数据结构|二叉排序/搜索树类模板】第一次写，有问题请见谅。