首页 > 代码库 > 树的广义表

树的广义表

人工智能实验课实现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<<")";
	}
}

  

树的广义表