关于二叉树,二叉查找树,AVL树的继承关系的问题
我写了一个二叉树类模板:
//点代表省略掉的代码
//Node是一个嵌套类,用于表示二叉树的节点.
template <typename Type>
class Binary_tree
{
public:
...
....
private:
class Node
{
public:
...
Type element;
Node* left;
Node* right;
};
...
....
};
然后用这个二叉树继承出一个二叉查找树Binary_search_tree.
template <typename Type>
class Binary_search_tree:public Binary_tree <Type>
{
public:
..
....
private:
..
....
};
这很简单,只是增加了一些成员函数和重写一些virtual函数.
接下来我想用这个二叉查找树继承出一个AVL树,于是麻烦来了:
为了方便,AVL树的节点中需要添加一个int height数据成员用来表示以这个节点为根的子树的高度,于是很自然的想到了这种继承方法:
template <typename Type>
class AVL_tree:public Binary_search_tree <Type>
{
public:
..
....
private:
class AVL_Node:public Node
{
...
int height;
};
..
....
};
然而,Node里的两个指针仍是指向Node的指针.这意味着我无法使用形如pn-> left-> height的方法来访问height.
如果我为AVL_Node添加两个指向AVL_Node的指针AVL_left和AVL_right,也有很多麻烦:二叉树和二叉查找树中的会改变left和right的函数并不会改变针AVL_left和AVL_right.
如果定义一个新的AVL_Node,而不是从Node继承而来,那二叉树和二叉查找树中的那些函数就都没法使用了.
这该怎么办呢?
[解决办法]
((AVL_Node*)pn-> left)-> height
[解决办法]
或许Binary_Tree的模版可以增加一个参数表示节点类型
template <typename Type>
class Binary_Node
{
public:
...
Type element;
Node* left;
Node* right;
};
template <typename Type, typename _Node = Binary_Node <Type> >
class Binary_tree
{
public:
typedef _Node Node;
....
};
template <typename Type, typename _Node = Binary_Node <Type> >
class Binary_search_tree:public Binary_tree <Type, _Node>
{
....
};
template <typename Type>
class AVL_Node:public Binary_Node <Type>
{
...
int height;
};
template <typename Type>
class AVL_tree:public Binary_search_tree <Type, AVL_Node <Type> >
{
public:
..
....
private:
....
};
