1、最优判定树定义：
百度和维基上也没找到定义，可能是这本书独有的，字太多了，我就直接拍图片了。
给定这张表： 如果利用huffman算法(每次找最小的两个结点去构造一个新结点)去生成一颗判定树的话，判定树应该是下图，这并不是最优的 最优的是下图：这颗判定树的比较次要比上面的少 而实现这颗判定树的算法是Hu-Tucker算法: 1）、按初始顺序排列各个结点，作为n颗树。 2）、从头遍历找相邻结点权值之和最小的那一对结点,通过它们生成新结点(那一对结点分别作为左右子女,新结点权值等于左右子女权值之和),用新结点顶替原来两个结点的位置。 3）、重复2）直到只有一颗树。
2、全部代码：
#include<iostream> #include<string> #include<vector> using namespace std; struct Node { string value; double weight; Node *lchild,*rchild; Node(string v,double w) { value = v; weight = w; lchild = rchild = NULL; } }; void createOptimalDecisionTree(Node *&root,vector<string> values,double weights[]) { vector<Node*> nodes; for(int i = 0; i < values.size(); i++) { Node* newNode = new Node(values[i],weights[i]); nodes.push_back(newNode); } int nodeCount = nodes.size(); //当前节点数 while(nodeCount > 1) { double minWeight = 999999; for(int i = 0; i < nodeCount-1 ; i++) { //从0开始遍历计算相邻判定结点weight之和 记录最小和 double sumWeight = nodes[i]->weight + nodes[i+1]->weight; if( sumWeight < minWeight) { minWeight = nodes[i]->weight + nodes[i+1]->weight; //记录最小和 } } for(int i = 0; i < nodeCount-1; i++) { double sumWeight = nodes[i]->weight + nodes[i+1]->weight; if(sumWeight == minWeight)//找到是哪一对 { Node *newNode = new Node("#",minWeight); //创建新结点 newNode->lchild = nodes[i]; newNode->rchild = nodes[i+1]; nodes[i] = newNode; //用新结点取代 前面那个结点的位置 if(nodeCount >= 2) //如果结点个数还大于等于2 { for(i = i + 1 ; i < nodeCount-1; i++) //就把 i后面的结点移前一位 { nodes[i] = nodes[i+1]; } nodeCount--; //结点个数减一 break; } } } } root = nodes[0]; } void printOptimalDecisionTree(Node *root,int k) //打印最优判定树，先打印右子树 { if(root != NULL) { printOptimalDecisionTree(root->rchild,k+5); for(int i = 0; i < k; i++) { cout<<" "; } cout<<root->value<<endl; printOptimalDecisionTree(root->lchild,k+5); } } int main() { vector<string> values = {"[0,60]","[60,70]","[70,80]","[80,90]","[90,100]"}; double weights[] = {0.10,0.20,0.35,0.25,0.10}; Node * root = NULL; createOptimalDecisionTree(root,values,weights); printOptimalDecisionTree(root,0); return 0; }3、结果： 对应的if - else就应该是：
if(score < 80) { if(score < 70) { if(score < 60) { } else { } } else { } } else { if(score < 90) { } else { } }