在有序序列的查找中，如果各個元素的查找概率都是一樣的，那么二分查找是最快的查找算法，但是如果查找元素的查找概率是不一樣的，那么用二分查找就不一定是最快的查找方法了，可以通過計算ASL來得知。所以基于這種查找元素概率不想等的有序序列，可以通過構造最優(yōu)二叉樹的方法，使得該二叉樹的帶權路徑長度最小，這樣的二叉樹的構造代價是非常大的，所以用一種近似的算法，構造次優(yōu)查找樹，該樹的帶權路徑長度近似達到最小。

　　數(shù)據(jù)結構中算法描述為：

　　

1 #include <iostream> 2 #include <cmath> 3 #include <cstdlib> 4 #include <iomanip> 5 6 using namespace std; 7 8 typedef struct treenode 9 { 10 char data; 11 int weight; 12 treenode *left; 13 treenode *right; 14 }Treenode,*Treep; 15 16 //初始化二叉樹 17 void init_tree(Treep &root) 18 { 19 root=NULL; 20 cout<<"初始化成功!"<<endl; 21 } 22 23 //創(chuàng)建二叉樹 24 void SecondOptimal(Treep &rt, char R[],int sw[], int low, int high) 25 { 26 //由有序表R[low....high]及其累積權值表sw(其中sw[0]==0)遞歸構造次優(yōu)查找樹T 27 int i = low; 28 //int min = abs(sw[high] - sw[low]); 29 int dw = sw[high] - sw[low-1]; 30 int min = dw; 31 for(int j=low+1; j<=high; ++j) //選擇最小的ΔPi值 32 { 33 if(abs(dw-sw[j]-sw[j-1]) < min) 34 { 35 i=j; 36 min=abs(dw-sw[j]-sw[j-1]); 37 } 38 } 39 rt=new Treenode; 40 rt->data=R[i]; //生成節(jié)點 41 if(i==low) //左子樹為空 42 rt->left = NULL; 43 else //構造左子樹 44 SecondOptimal(rt->left, R, sw, low, i-1); 45 46 if(i==high) //右子樹為空 47 rt->right = NULL; 48 else //構造右子樹 49 SecondOptimal(rt->right, R, sw, i+1, high); 50 }//SecondOptimal 51 52 //前序遍歷二叉樹 53 void pre_order(Treep rt) 54 { 55 if(rt) 56 { 57 cout<<rt->data<<" "; 58 pre_order(rt->left); 59 pre_order(rt->right); 60 } 61 } 62 63 //中序遍歷二叉樹 64 void in_order(Treep rt) 65 { 66 if(rt) 67 { 68 in_order(rt->left); 69 cout<<rt->data<<" "; 70 in_order(rt->right); 71 } 72 } 73 74 //后序遍歷二叉樹 75 void post_order(Treep rt) 76 { 77 if(rt) 78 { 79 post_order(rt->left); 80 post_order(rt->right); 81 cout<<rt->data<<" "; 82 } 83 } 84 85 //查找二叉樹中是否存在某元素 86 int seach_tree(Treep &rt,char key) 87 { 88 if(rt==NULL) 89 return 0; 90 else 91 { 92 if(rt->data==key) 93 { 94 return 1; 95 } 96 else 97 { 98 if(seach_tree(rt->left,key) || seach_tree(rt->right,key)) 99 return 1; //如果左右子樹有一個搜索到，就返回1 100 else 101 return 0; //如果左右子樹都沒有搜索到，返回0 102 } 103 } 104 } 105 106 int main() 107 { 108 Treep root; 109 init_tree(root); //初始化樹 110 int low=1, high=10; 111 int *weight, *sw; 112 char *R; 113 114 R=new char[high]; 115 for(int i=low; i<high; i++) 116 R[i]='A'+i-1; 117 cout<<"構造次優(yōu)查找樹的點R[]:"<<endl; 118 for(int i=low; i<high; i++) 119 cout<<setw(3)<<R[i]<<" "; 120 cout<<endl; 121 122 weight=new int[high]; 123 weight[0]=0; 124 weight[1]=1; 125 weight[2]=1; 126 weight[3]=2; 127 weight[4]=5; 128 weight[5]=3; 129 weight[6]=4; 130 weight[7]=4; 131 weight[8]=3; 132 weight[9]=5; 133 cout<<"構造次優(yōu)查找樹的點的權值weight[]:"<<endl; 134 for(int i=low; i<high; i++) 135 cout<<setw(3)<<weight[i]<<" "; 136 cout<<endl; 137 138 sw=new int[high]; 139 sw[0]=0; 140 for(int i=low; i<high; i++) 141 { 142 sw[i]=sw[i-1]+weight[i]; 143 } 144 cout<<"構造次優(yōu)查找樹的點累積權值sw[]:"<<endl; 145 for(int i=low; i<high; i++) 146 cout<<setw(3)<<sw[i]<<" "; 147 cout<<endl; 148 149 //創(chuàng)建二叉樹 150 SecondOptimal(root, R, sw, low, high-1); 151 152 cout<<"前序遍歷序列是:"<<endl; 153 pre_order(root); 154 cout<<endl; 155 156 cout<<"中序遍歷序列是:"<<endl; 157 in_order(root); 158 cout<<endl; 159 160 cout<<"后序遍歷序列是:"<<endl; 161 post_order(root); 162 cout<<endl; 163 164 //查找二叉樹中是否存在某元素 165 cout<<"輸入要查找的元素!"<<endl; 166 char ch; 167 cin>>ch; 168 if(seach_tree(root,ch)==1) 169 cout<<"Yes"<<endl; 170 else 171 cout<<"No"<<endl; 172 while(1); 173 return 0; 174 }

　　運行結果如下：
　　

總結

以上是生活随笔為你收集整理的次优二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。