首页 > 代码库 > 树的广义表
树的广义表
人工智能实验课实现ID3算法时，需要把最终的决策树输出出来
考虑每个节点的名字长度、孩子个数都不同，直接层级遍历对齐起来很麻烦且容易出现歧义，所以决定用广义表的形式输出决策树
由于广义表中的元素顺序具有相对顺序，所以采用形式Root({weight1}subTree1,{weight2}subTree2,...)来表示树，其中每个subTree都是广义表，{weight}是根和这棵子树相连边的权重值
现在用http://blog.csdn.net/u013018721/article/details/38042561?utm_source=tuicool&utm_medium=referral中给出的ID3决策树实例作为例子说明
此时根节点为“年龄”，则一开始建立的广义表应为“年龄”（{<=30}“长相”子树，{>30}【不见】），其中为了区分，【...】表示叶子
而“长相”子树也是用相同的方法递归地建立，则最终建成的广义表为：
“年龄”（{<=30}“长相”（{帅}“收入”（{高}【见】，{中等}“公务员”（{是}【见】，{不是}【不见】），{低}【不见】），{丑}【不见】），{>30}【不见】）
下面是代码实现，首先构建根节点，再递归地构建所有子树，直到叶子
树节点定义（孩子兄弟表示法）
struct TNode
{
AttrType type; //属性名
AttrValue value,//边权重
res; //数据
TNode *firstchild, *nextsibling;
};
输出广义表实现
void showTreeLists(TNode *T)
{
TNode *p;
if(!T)
return;
//输出边的权重
cout<<"{";
if(T->value!=voi)
cout<<name_map[T->value];
cout<<"}";
//输出节点属性名
if(T->type==contact_lenses)
cout<<name_map[T->res];
else
cout<<type_map[T->type];
//递归构建所有孩子所对应的子树
p = T->firstchild;
if (p)
{
cout<<"(";
while (p)
{
treelists(p);
p = p->nextsibling;
if (p)cout<<‘,‘;
}
cout<<")";
}
}
树的广义表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。