二叉排序樹類模板
- 模板類
- 測驗
- 主函式呼叫
模板類
將整個二叉排序樹封裝為一個模板類
剛開始用靜態變數當函式引數默認引數，但所有物件共用一個變數就沒辦法保存多個樹的root了，解決辦法是：把遞回的函式設為私有函式，然后用一個公用的函式去呼叫這個函式，同時給這個函式傳值，這樣用戶就可以直接呼叫函式，而不需要傳任何值，
#include <iostream>
#include<vector>
#include<queue>
using namespace std;
template<typename T>
//luosansui
class TreeNode {
public:
T value;
TreeNode* left;
TreeNode* right;
TreeNode(const T& value) {
this->value = 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<typename T, typename Tclass = Compare>
//二叉查找樹
class BinarySortTree {
private:
TreeNode<T>* root;
TreeNode<T>* nullp;
Tclass compare;
//記錄節點數目
int node_num;
//洗掉用的查找
TreeNode<T>*& _findData(const T& node_value, TreeNode<T>*& node) {
if (node == NULL) {
return nullp;
}
else if (node_value == node->value) {
return node;
}
if (!compare(node_value, node->value)) {
return _findData(node_value, node->right);
}
else {
return _findData(node_value, node->left);
}
}
//普通的查找
bool _find(const T& node_value, TreeNode<T>*& node) {
if (node == NULL) {
return false;
}
else if (node_value == node->value) {
return true;
}
if (!compare(node_value, node->value)) {
return _find(node_value, node->right);
}
else {
return _find(node_value, node->left);
}
}
//析構用的遍歷
void _destruct(TreeNode<T>*& node) {
if (node == NULL)return;
_destruct(node->left);
_destruct(node->right);
delete node;
}
//列印
void _print(TreeNode<T>*& 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<T>(node_value);
return true;
}
else {
TreeNode<T>* tempNode = root;
while (1) {
if (node_value == 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<T>(node_value);
return true;
}
}
else if (compare(node_value, tempNode->value)) {
if (tempNode->left != NULL) {
tempNode = tempNode->left;
}
else {
tempNode->left = new TreeNode<T>(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<T>*& temp = _findData(node_value, root);
if (temp == NULL) {
cout << "無資料可洗掉" << endl;
return false;
}
else {
node_num--;
if (temp->left == NULL && temp->right != NULL) {//僅左空
TreeNode<T>* temp_temp = temp;
temp = temp->right;
delete temp_temp;
}
else if (temp->left != NULL && temp->right == NULL) {//僅右空
TreeNode<T>* temp_temp = temp;
temp = temp->left;
delete temp_temp;
}
else if (temp->left != NULL && temp->right != NULL) {//無空
TreeNode<T>* temp_temp = temp;
TreeNode<T>* 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;
}
else {
delete temp;
temp = NULL;
}
cout << "資料已洗掉" << endl;
return true;
}
}
//獲取節點總數
int getNodeNum() {
return node_num;
}
//獲取ASL，廣度優先遍歷求每層元素個數
int getASL() {
TreeNode<T>* node = root;
if (node == NULL)return 0;
vector<int> layer;
queue<TreeNode<T>*> que_bfs_1;
queue<TreeNode<T>*> que_bfs_2;
que_bfs_1.push(root);
while (!que_bfs_1.empty() || !que_bfs_2.empty()) {
queue<TreeNode<T>*>& temp_que_1 = !que_bfs_1.empty() ? que_bfs_1 : que_bfs_2;
queue<TreeNode<T>*>& 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<int>::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 _find(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<int> 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<char> T;
T.insert('A');
T.insert('C');
if (T.find('A')) {
cout << "A 找到" << endl;
}
else {
cout << "A 未找到" << endl;
}
T.print();
cout << endl << "--------" << endl;
BinarySortTree<person,comp> 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;
}
第一次寫，有問題請見諒，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/232496.html
標籤：其他