二叉树结点类的实现
上面部分分析了二叉树结点类的两种实现方法,从上面的分析中可以看出两种方法各有其优点,但是共有的缺点:内存空间浪费始终不能很好的解决.下面是将分支结点类以及叶结点类的定义分开,从而实现了内存空间的最大利用.它首先实现了一个纯虚基类,然后两种结点类都继承了该类,请看下面的代码:
////////////////////////////////////////////////////////////////////
//纯虚基类的定义.
////////////////////////////////////////////////////////////////////
class VarBinNode
{
public:
virtual bool IsLeaf() =0; //如果是叶结点,那么返回true.
};
////////////////////////////////////////////////////////////////////
//叶结点类的定义.
////////////////////////////////////////////////////////////////////
template
class LeafNode :public VarBinNode
{
public:
LeafNode(const type&);
bool IsLeaf();
type& GetNodeValue();
private:
type data;
};
template
LeafNode
{
data=val;
}
template
bool LeafNode
{
return true;
}
template
type& LeafNode
{
return data;
}
////////////////////////////////////////////////////////////////////
//分支结点的定义.
////////////////////////////////////////////////////////////////////
class IntlNode :public VarBinNode
{
public:
IntlNode(const char&,VarBinNode * =NULL,VarBinNode * =NULL);
bool IsLeaf();
VarBinNode* GetLeftNode();
VarBinNode* GetRightNode();
char& GetOperator();
private:
char op;
VarBinNode *left;
VarBinNode *right;
};
IntlNode::IntlNode(const char &opx,VarBinNode *l,VarBinNode *r)
{
op=opx;
left=l;
right=r;
}
bool IntlNode::IsLeaf()
{
return false;
}
VarBinNode* IntlNode::GetLeftNode()
{
return left;
}
VarBinNode* IntlNode::GetRightNode()
{
return right;
}
char& IntlNode::GetOperator()
{
return op;
}
////////////////////////////////////////////////////////////////////
//对上面两个结点的测试程序.
////////////////////////////////////////////////////////////////////
void traverse(VarBinNode *subRoot)
{
if(subRoot==NULL)
return;
if(subRoot->IsLeaf())
cout<<"Leaf:"<<(LeafNode
else
{
cout<<"Internal:"<<(IntlNode*)subRoot->GetOperator()<
traverse(((IntlNode*)subRoot)->GetLeftNode());
traverse(((IntlNode*)subRoot)->GetRightNode());
}
}
从上面的代码可以看出,结点指针是用VarBinNode类的对象,那为什么不用IntlNode类的对象呢?那是因为叶结点不是IntlNode类,所以两种结点类均继承了VarBinNode类,而且用该类的指针作为结点指针,这样可以很容易用强制类型转换转换成相应派生类的对象,至此我们就可很容易解决这一问题了.而虚基类仅声明IsLeaf函数是纯虚函数也就是因为这样,要不然还是没有办法区别该结点是叶结点还是分支结点,因为两种结点的派生函数仅简单的返回一个真或假,没有经过判断.
虽然虚基类可以作为通用的类的对象在两个结点类中互相转换,从而非常巧妙的解决了两种不同类的对象保存在树的结点中,但是如果该结点是分支结点的话,那么IntlNode类中定义的所有成员函数就不被VarBinNode类的对象直接访问,所以要经过一步强制类型转换.而叶结点也是如此,这在traverse函数中可以看得出来.
上面的程序中,traverse函数包含了相对独立的对于两个类的结点的处理的代码,其实有更好的一种方法,那就是在纯虚基类中再添加一个纯虚函数的声明,让两个类分别处理自己的部分,这种方法无非是更好的:
////////////////////////////////////////////////////////////////////
//纯虚基类的定义.
////////////////////////////////////////////////////////////////////
class VarBinNode
{
public:
virtual bool IsLeaf() =0; //如果是叶结点,那么返回true.
virtual void trav() =0; //用于处理每个类的各自结点的操作.
};
////////////////////////////////////////////////////////////////////
//叶结点类的定义.
////////////////////////////////////////////////////////////////////
template
class LeafNode :public VarBinNode
{
public:
LeafNode(const type&);
bool IsLeaf();
type& GetNodeValue();
void trav();
private:
type data;
};
template
LeafNode
{
data=val;
}
template
bool LeafNode
{
return true;
}
template
type& LeafNode
{
return data;
}
template
void LeafNode
{
cout<<"Leaf:"<
}
////////////////////////////////////////////////////////////////////
//分支结点的定义.
////////////////////////////////////////////////////////////////////
class IntlNode :public VarBinNode
{
public:
IntlNode(const char&,VarBinNode * =NULL,VarBinNode * =NULL);
bool IsLeaf();
VarBinNode* GetLeftNode();
VarBinNode* GetRightNode();
char& GetOperator();
void trav();
private:
char op;
VarBinNode *left;
VarBinNode *right;
};
IntlNode::IntlNode(const char &opx,VarBinNode *l,VarBinNode *r)
{
op=opx;
left=l;
right=r;
}
bool IntlNode::IsLeaf()
{
return false;
}
VarBinNode* IntlNode::GetLeftNode()
{
return left;
}
VarBinNode* IntlNode::GetRightNode()
{
return right;
}
char& IntlNode::GetOperator()
{
return op;
}
void IntlNode::trav()
{
cout<<"Internal:"<
if(left)
left->GetLeftNode();
if(right)
right->GetRightNode();
}
void traverse(VarBinNode *subRoot)
{
if(subRoot)
subRoot->trav();
}
这种方法比前一种方法更为简单,至少不用写很多关于类型转换的表达式,而且还简化了两种类的定义.
本文来源 我爱IT技术网 http://www.52ij.com/jishu/1715.html 转载请保留链接。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-