一、實驗名稱：伸展樹算法設計與實現
二、實驗目的：
1.掌握伸展樹的數據結構。
2.掌握伸展算法的實現。
三、實驗內容
完善下列程序，並回答問題。
1 #include <iostream.h>
2 enum ResultCode{Underflow, Overflow, Success, Duplicate, Fail, NotPresent};
3 template<class T>
4 struct BTNode
5 {//二叉樹結點類
6 BTNode(const T& x){ element=x; lChild=rChild=NULL; }
7 T element;
8 BTNode* lChild,*rChild;
9 };
10 template<class T>
11 class SPTree
12 {//伸展樹類
13 public:
14 SPTree(){root=NULL;}
15 ResultCode Insert(T x);
16 void printTree(){cout<<"該樹的邊分別為："<<endl; printTree(root);};
17 void printTree( BTNode<T>* &p){
18 if(p == NULL) return;
19 if(p->lChild != NULL){
20 cout<<" 從"<<p->element<<"到"<<p->lChild->element<<endl;
21 printTree(p->lChild);
22 }
23 if(p->rChild != NULL){
24 cout<<" 從"<<p->element<<"到"<<p->rChild->element<<endl;
25 printTree(p->rChild);
26 }
27 };
28 void printTree(int level){cout<<"該樹為："; printTree(root, level); cout<<endl;};
29 void printTree( BTNode<T>* &p, int level){
30 if(p == NULL) return;
31 if(p->lChild != NULL){
32 printTree(p->lChild, level+1);
33 }
34 cout<<endl;
35 for(int i = 0; i<level; i++) cout<<" ";
36 cout<<p->element;
37 if(p->rChild != NULL){
38 printTree(p->rChild, level+1);
39 }
40 };
41 protected:
42 BTNode<T>* root;
43 private:
44 ResultCode Insert(BTNode<T>* &p, T x);
45 void LRot(BTNode<T>* &p);
46 void RRot(BTNode<T>* &p);
47 };
48
49 template <class T>
50 void SPTree<T>::LRot(BTNode<T>*& p)
51 { //實現向左旋轉
52 學生自己書寫部分
53 }
54 template <class T>
55 void SPTree<T>::RRot(BTNode<T>*& p)
56 { //實現向右旋轉
57 學生自己書寫部分
58 }
59
60 template <class T>
61 ResultCode SPTree<T>::Insert(T x)
62 {
63 return Insert(root, x);
64 }
65 template <class T>
66 ResultCode SPTree<T>::Insert(BTNode<T>* &p, T x)
67 {
68 學生自己書寫部分
69 }
70
71 void main(){
72 SPTree<int> tree;
73 int ele[30] = {75,89,72,42,18,25,99,90,17,33};
74 int n = 10;
75 for(int i = 0; i < n; i++) tree.Insert(ele[i]);
76 cout<<"---伸展樹程序---"<<endl<<endl;
77 cout<<"依次插入的數為：";
78 for(int j = 0; j < n; j++) cout<<ele[j]<<",";
79 tree.printTree();
80 tree.printTree(0);
81 }
程序問題：
四、實驗小結和心得
