天津做网站制作公司,青岛免费模板建站,优质做网站哪家正规,微信网站模板免费下载在有序序列的查找中#xff0c;如果各个元素的查找概率都是一样的#xff0c;那么二分查找是最快的查找算法#xff0c;但是如果查找元素的查找概率是不一样的#xff0c;那么用二分查找就不一定是最快的查找方法了#xff0c;可以通过计算ASL来得知。所以基于这种查找元素… 在有序序列的查找中如果各个元素的查找概率都是一样的那么二分查找是最快的查找算法但是如果查找元素的查找概率是不一样的那么用二分查找就不一定是最快的查找方法了可以通过计算ASL来得知。所以基于这种查找元素概率不想等的有序序列可以通过构造最优二叉树的方法使得该二叉树的带权路径长度最小这样的二叉树的构造代价是非常大的所以用一种近似的算法构造次优查找树该树的带权路径长度近似达到最小。 数据结构中算法描述为 1 #include iostream2 #include cmath3 #include cstdlib4 #include iomanip5 6 using namespace std;7 8 typedef struct treenode9 {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 rootNULL;20 cout初始化成功!endl;21 }22 23 //创建二叉树24 void SecondOptimal(Treep rt, char R[],int sw[], int low, int high)25 {26 //由有序表R[low....high]及其累积权值表sw(其中sw[0]0)递归构造次优查找树T27 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 jlow1; jhigh; j) //选择最小的ΔPi值32 {33 if(abs(dw-sw[j]-sw[j-1]) min)34 {35 ij;36 minabs(dw-sw[j]-sw[j-1]);37 }38 }39 rtnew Treenode;40 rt-dataR[i]; //生成节点41 if(ilow) //左子树为空42 rt-left NULL;43 else //构造左子树44 SecondOptimal(rt-left, R, sw, low, i-1);45 46 if(ihigh) //右子树为空47 rt-right NULL;48 else //构造右子树49 SecondOptimal(rt-right, R, sw, i1, high);50 }//SecondOptimal51 52 //前序遍历二叉树53 void pre_order(Treep rt)54 {55 if(rt)56 {57 coutrt-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 coutrt-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 coutrt-data ;82 }83 }84 85 //查找二叉树中是否存在某元素86 int seach_tree(Treep rt,char key)87 {88 if(rtNULL) 89 return 0; 90 else 91 { 92 if(rt-datakey) 93 {94 return 1;95 }96 else97 {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 low1, high10;
111 int *weight, *sw;
112 char *R;
113
114 Rnew char[high];
115 for(int ilow; ihigh; i)
116 R[i]Ai-1;
117 cout构造次优查找树的点R[]:endl;
118 for(int ilow; ihigh; i)
119 coutsetw(3)R[i] ;
120 coutendl;
121
122 weightnew 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构造次优查找树的点的权值weight[]:endl;
134 for(int ilow; ihigh; i)
135 coutsetw(3)weight[i] ;
136 coutendl;
137
138 swnew int[high];
139 sw[0]0;
140 for(int ilow; ihigh; i)
141 {
142 sw[i]sw[i-1]weight[i];
143 }
144 cout构造次优查找树的点累积权值sw[]:endl;
145 for(int ilow; ihigh; i)
146 coutsetw(3)sw[i] ;
147 coutendl;
148
149 //创建二叉树
150 SecondOptimal(root, R, sw, low, high-1);
151
152 cout前序遍历序列是:endl;
153 pre_order(root);
154 coutendl;
155
156 cout中序遍历序列是:endl;
157 in_order(root);
158 coutendl;
159
160 cout后序遍历序列是:endl;
161 post_order(root);
162 coutendl;
163
164 //查找二叉树中是否存在某元素
165 cout输入要查找的元素!endl;
166 char ch;
167 cinch;
168 if(seach_tree(root,ch)1)
169 coutYesendl;
170 else
171 coutNoendl;
172 while(1);
173 return 0;
174 } 运行结果如下
