標准BST二叉搜索樹寫法，bst二叉樹寫法
本人最近被各種數據結構的實驗折磨的不要不要的，特別是代碼部分，對數據結構有嚴格的要求，比如寫個BST要分成兩個類，一個節點類，要給樹類，關鍵是所以操作都要用函數完成，也就是在樹類中不能直接操作節點，需要使用節點類中的函數來實現各種操作。
簡直太麻煩，但是花時間寫了也是有好處的，認真寫完絕對幾年忘不了。同時用函數操作數據也更安全，將數據設為私有成員更符合規范。下面給出代碼。
![]()
1 #include<iostream>
2 using namespace std;
3
4 class BinNode {
5 private:
6 int element;
7 BinNode *leftChild;
8 BinNode *rightChild;
9 public:
10 BinNode(int a, BinNode* left, BinNode* right) {
11 element = a;
12 leftChild = left;
13 rightChild = right;
14 }
15 int val() { return element; }
16 BinNode* left() { return leftChild; }
17 void setLeft(BinNode *t) { leftChild=t; }
18 BinNode* right() { return rightChild; }
19 void setRight(BinNode *t) { rightChild = t; }
20 };
21 class BST{
22 private:
23 BinNode *root;
24 BinNode* insertHelp(int x, BinNode* root) {
25 BinNode* t = root;
26 if (t == NULL) { t = new BinNode(x, NULL, NULL); return t; }
27 else if (x < t->val())
28 t->setLeft(insertHelp(x, t->left()));
29 else if (x > t->val())
30 t->setRight(insertHelp(x, t->right()));
31 return t;
32 }
33 void findHelp(const int x, int &count, BinNode* root) {
34 count++;
35 if (root == NULL) { count = 0;return; }
36 else if (root->val() == x) return;
37 if(x<root->val())
38 findHelp(x, count, root->left());
39 if(x>=root->val())
40 findHelp(x, count, root->right());
41 }
42 public:
43 BST() { root = NULL;}
44 ~BST() { clear(root);}
45
46 void clear(BinNode *root) {
47 if (root != NULL) {
48 clear(root->left());
49 clear(root->right());
50 delete root;
51 }
52 }
53 void insert(int& x) {
54 root=insertHelp(x, root);
55 }
56 void find(const int x, int &count) {
57 findHelp(x, count, root);
58 }
59 };
60 int main() {
61 BST a;
62 int n;
63 cout << "請輸入節點個數：" << endl;
64 cin >> n;
65 cout << "依次輸入節點值："<<endl;
66 for (int i = 0;i < n;i++) {
67 int x;cin >> x;
68 a.insert(x);
69 }
70 int num;
71 while ((cout << "請輸入需要查找的值：（ctrl+z結束查找）" << endl)&&(cin>>num)&&num!=EOF){
72 int count=0;
73 a.find(num, count);
74 if (count == 0)
75 cout << "查找失敗！" << endl;
76 else
77 cout << "查找成功！查找次數為：" << count << endl;
78 }
79 system("pause");
80 return 0;
81 }
View Code
下面是實驗報告的文檔地址
http://wenku.baidu.com/view/d97fb2b114791711cd791711
