标准BST二叉搜索树写法

  本人最近被各种数据结构的实验折磨的不要不要的,特别是代码部分,对数据结构有严格的要求,比如写个BST要分成两个类,一个节点类,要给树类,关键是所以操作都要用函数完成,也就是在树类中不能直接操作节点,需要使用节点类中的函数来实现各种操作。

  简直太麻烦,但是花时间写了也是有好处的,认真写完绝对几年忘不了。同时用函数操作数据也更安全,将数据设为私有成员更符合规范。下面给出代码。

  

 #include<iostream>
using namespace std; class BinNode {
private:
int element;
BinNode *leftChild;
BinNode *rightChild;
public:
BinNode(int a, BinNode* left, BinNode* right) {
element = a;
leftChild = left;
rightChild = right;
}
int val() { return element; }
BinNode* left() { return leftChild; }
void setLeft(BinNode *t) { leftChild=t; }
BinNode* right() { return rightChild; }
void setRight(BinNode *t) { rightChild = t; }
};
class BST{
private:
BinNode *root;
BinNode* insertHelp(int x, BinNode* root) {
BinNode* t = root;
if (t == NULL) { t = new BinNode(x, NULL, NULL); return t; }
else if (x < t->val())
t->setLeft(insertHelp(x, t->left()));
else if (x > t->val())
t->setRight(insertHelp(x, t->right()));
return t;
}
void findHelp(const int x, int &count, BinNode* root) {
count++;
if (root == NULL) { count = ;return; }
else if (root->val() == x) return;
if(x<root->val())
findHelp(x, count, root->left());
if(x>=root->val())
findHelp(x, count, root->right());
}
public:
BST() { root = NULL;}
~BST() { clear(root);} void clear(BinNode *root) {
if (root != NULL) {
clear(root->left());
clear(root->right());
delete root;
}
}
void insert(int& x) {
root=insertHelp(x, root);
}
void find(const int x, int &count) {
findHelp(x, count, root);
}
};
int main() {
BST a;
int n;
cout << "请输入节点个数:" << endl;
cin >> n;
cout << "依次输入节点值:"<<endl;
for (int i = ;i < n;i++) {
int x;cin >> x;
a.insert(x);
}
int num;
while ((cout << "请输入需要查找的值:(ctrl+z结束查找)" << endl)&&(cin>>num)&&num!=EOF){
int count=;
a.find(num, count);
if (count == )
cout << "查找失败!" << endl;
else
cout << "查找成功!查找次数为:" << count << endl;
}
system("pause");
return ;
}

下面是实验报告的文档地址

http://wenku.baidu.com/view/d97fb2b114791711cd791711

上一篇:2018.09.25 bzoj3572: [Hnoi2014]世界树(虚树+树形dp)


下一篇:微服务架构介绍和RPC框架对比