再分享二叉树结点类的实现
对二叉树的周游时我们提到了结点类的虚基类,在这里我们要重定义一个类来实现二叉树的结点类,其定义如下:
////////////////////////////////////////////////////////////////////////
//虚基类的定义
////////////////////////////////////////////////////////////////////////
template
class BinNode
{
public:
virtual type& GetNodeValue() =0; //得到结点数值.
virtual void SetNodeValue(type&) =0; //设置结点数值.
virtual BinNode
virtual BinNode
virtual void SetLeftNode(BinNode
virtual void SetRightNode(BinNode
virtual bool IsLeaf() =0; //如果是叶结点,那么返回true.
};
////////////////////////////////////////////////////////////////////////
//结点类的定义
////////////////////////////////////////////////////////////////////////
template
class BinNodePtr :public BinNode
{
public:
BinNodePtr();
BinNodePtr(const type&,BinNodePtr * =NULL,BinNodePtr * =NULL);
type& GetNodeValue();
void SetNodeValue(const type&);
BinNode
BinNode
void SetLeftNode(BinNode
void SetRightNode(BinNode
bool IsLeaf();
private:
type data; //数值.
BinNodePtr
BinNodePtr
};
template
BinNodePtr
{
left=right=NULL; //初始化成一个叶结点.
}
template
BinNodePtr
BinNodePtr
{
data=val;
left=l;
right=r;
}
template
type& BinNodePtr
{
return data;
}
template
void BinNodePtr
{
data=val;
}
template
BinNode
{
return (BinNode
}
template
BinNode
{
return (BinNode
}
template
void BinNodePtr
{
left=(BinNodePtr
}
template
void BinNodePtr
{
right=(BinNodePtr
}
template
bool BinNodePtr
{
return (left==NULL && right==NULL);
}
上面用纯虚类BinNode派生出一个结点类,可以看出该结点类适合于大多数的二叉树的实现,它不仅包含了组成二叉树所必须的左子结点以及右子结点的指针,而且包含了数据域.那么分支结点的left或right或两者的值是指向具体的子结点的,但是叶结点却不用有该两个域,所以判断叶结点的方法是用left==NULL && right==NULL来实现的.
但是很多时候都只在叶结点中保存数值,而分支结点只是表示结构的关系而已,那么此时再用上面定义的类来实现二叉树的话势必太浪费内存空间,因为分支结点的data域以及叶结点的left和right域就变得没有意义,而且二叉树的结点很多时就会浪费掉非常多的空间.所以我们想出一个办法,用两个类来分别表示分支结点以及叶结点.
下面举一个非常简单的例子,即表达式树.任何算符表达式都可以用树来保存所有的操作数以及运算符,然而表达式树的特点是:只有叶结点保存操作数,而所有的分支结点用来保存运算符,而一个子结点有两个叶结点时两个叶结点上保存的操作数由子结点中保存的运算符进行连接.知道了表达式树的定义以后,我们来实现一下4x(2x+a)-c这个表达式的树形结构:
(-)
/ \
/ \
(*) (c)
/ \
/ \
(*) (+)
/ \ / \
(4) (x) (*) (a)
/ \
(2) (x)
从上面的树形结构可以看出,有4,x,2,x,c一共五个叶结点和六个分支结点,如果再用上面的结点定义来实现的话,空间代价就会非常大,那么我们这里可以重新定义一个结点类,来满足我们的要求.那么我们只定义一个结点类,如何判断要处理的结点是分支还是叶结点呢?有人可能会马上想到IsLeaf函数,不错,这个函数可以判断某个结点是分支还是叶结点,但是如果只用该函数来判断的话,那么我们的类应该如何定义呢?作为第一种区分叶结点以及分支结点的方法,我们这里使用共同体类型来区分.请看下面的新类的定义:
/////////////////////////////////////////////////////////////////////
//对用共用体区分分支以及叶结点的方法的类的定义.
/////////////////////////////////////////////////////////////////////
enum NodeType{Leaf,Internal};
template
class VarBinNode
{
public:
NodeType myType; //该结点是分支还是叶结点.
union
{
struct //结构体定义了一个分支结点.
{
VarBinNode
VarBinNode
char opx; //运算符,用一个char类型表示.
}intl;
type data; //定义了一个叶结点.表示操作数.
};
VarBinNode(const type&); //初始化叶结点构造函数.
VarBinNode(char,VarBinNode
bool IsLeaf(); //叶结点的话,返回true.
VarBinNode
VarBinNode
};
template
VarBinNode
{
myType=Leaf; //为叶结点.
data=val; //操作数赋值.
}
template
VarBinNode
{
myType=Internal; //为分支结点.
opx=op; //运算符
intl.left=l;
intl.right=r; //左右子结点或者是叶结点.
}
template
bool VarBinNode
{
return myType==Leaf; //返回是否是叶结点.
}
template
VarBinNode
{
return intl.left;
}
template
VarBinNode
{
return intl.right;
}
///////////////////////////////////////////////////////////////////////
//下面是一个测试程序.
///////////////////////////////////////////////////////////////////////
void traverse(VarBinNode
{
if(subRoot==NULL)
return; //如果树为空,那么返回.
if(subRoot->IsLeaf())
cout<<"Leaf:"<
else
{
cout<<"Internal:"<
traverse(subRoot->GetLeftNode()); //符.
traverse(subRoot->GetRightNode()); //以前序周游法对树进行周游.
}
}
从上面的代码可以看出,我们使用了一个内嵌的共用体进行区分分支以及叶结点的域,并且用一个枚举类型的变量区分两种结点.这种方法简单,但有一个明显的缺点:由于共用体类型的变量的内存空间是占用最多域的成员的内存空间,那么不管结点是分支还是叶结点,共同体都要占相同的内存空间,那么在共用体中定义的两个成员内存空间差距较大(例如本例中的结构体变量以及int类型变量),也会浪费掉很多空间,在本例中很明显可以看出,结构体类型变量成员的内存空间大于int类型,那么在叶结点远远多于分支结点时,就会形成内存的浪费.这样一来,相比第一种通用形式来说没有多少提高,所以在实际应用一般不会使用这种类.
本文来源 我爱IT技术网 http://www.52ij.com/jishu/1716.html 转载请保留链接。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-