三、BinTree的实现
1、数据成员
按照上面的设计，BinTree至少需要三个数据成员:
Node * root;
size_t numOfElem;
Compare comp;
2、构造函数
默认构造函数构造一颗空的二叉树：
explicit BinTree(const Compare & srcComp = Compare())
: root(0), numOfElem(0), comp(srcComp){} ;
注意我这里使用了explicit关键字，是为了杜绝从Compare类型到BinTree类型的隐式转换，因为这显然不会是我们想要的
3、复制控制
显而易见的，对于二叉树的复制控制，采用递归是最方便易懂的方法，因此可以定义以下辅助函数
/*
* 以subRoot为根节点，复制srcTree
* 注意本函数不负责清理subRoot原来指向的资源，
* 也不负责numOfElem，comp等对象的调整
*/
template
void BinTree:: /* return type and scope */
sub_Tree_Init(const Node * subRoot,
const Node * srcTreeRoot)
{
if( 0 == srcTreeRoot)
return subRoot = 0;
subRoot = new Node( *srcTreeRoot, comp );
sub_Tree_Init(subRoot->left, srcTreeRoot->left );
sub_Tree_Init(subRoot->right, srcTreeRoot->right);
return;
}
/* 删除以subRoot 为根节点的 subTree
* 同样的，本函数不负责numOfElem, comp等对象的调整
*/
template
void BinTree:: /* return type and scope */
sub_Tree_Del(const Node *subRoot)
{
if (subRoot)
{
sub_Tree_Del(subRoot->left);
sub_Tree_Del(subRoot->right);
delete subRoot;
}
return;
}
到这里，三个复制控制函数只需要负责numOfElem，comp等处理就行了
4、size()
这个是最简单的，直接return numOfElem即可
5、min(), max()
只要理解了二叉树的性质，这个也不难，最左边的节点就是最小节点，最右边的节点为最大节点，min()可以用类似下面的代码实现:
Node * node;
for( node = subRoot; 0 != node->left; node = node->left)
;
return node->data;
6、query()
可以用类似二分查找的方法实现，不过在二叉树里进行二分查找远比在数组中做二分查找来得简单。唯一需要注意的是，因为这里采用模板实现，所以必须要采用二元函数对象(binary functor)Compare来定义比较操作，而不是通常所用的小于号("<")
template
Node * BinTree::
search(const Data& data) const
{
Node * node = root;
Node * pare = 0; /* record the parent of node */
while( 0 != node)
{
pare = node;
if( comp(node->data, data) ) /* 节点上的数据较小 */
node = node->right;
else if( comp(data, node->data) ) /* 节点上的数据较大 */
node = node->left;
else /* 二者相等 */
return node;
}
/* 搜索不成功，返回插入该data时其所应该在的节点的父节点 */
return pare;
}/* search()*/
在这里，我并没有直接定义query函数，而是定义了一个search函数，这个search函数的行为是：如果在二叉树中找到数据为data的节点，则返回该节点，如果没有找到数据为data的节点，则返回(向二叉树中插入data时其所应该在的节点的)父节点
有了这个search函数，结合Node类定义的operator==()函数，可以实现query()函数如下：
bool query(const Data& data ) const
{Node* node = search(data);
if(0 != node) return *node == data; return false; }
因为对任何类型Type，*(static_cast(0))都会引起运行时错误，所以在返回前需要检验node是否为0
7、successor()
在successor函数体中，首先调用search函数找到data所在的节点的位置
(1)、如果在二叉树中存在数据为data的节点x，则可以对其做分析如下：
A、如果该节点x存在右子节点，则successor为其右子树上的最小值
B、如果该节点x没有右子节点，且该树中存在节点x的后继(successor)节点y，则节点y 满足以下条件: a) y是的左子节点是x的祖先节点(这里的祖先节点包括自己及其父节点)，b) y是满足条件a)的最低节点……不知道表述清楚没有，还是看伪代码好了
具体证明请参见《算法导论》，实际上，画个图就出来了
TREE_SUCCESSOR(x)
if(right[x]) != NULL
return TREE-MIN( right[x] )
y = parent[x]
while y != NULL && x=right[y] {
x=y
y=parent[y]
}
return y
(2)如果二叉树中不存在数据为data的节点x，比较data与search函数所返回节点中的数据值，结合情况(1)的讨论，很快就能得到相似的代码，这里不再赘述
注：写到这里的时候，我发现了已经初步测试通过的BinTree隐藏的一个bug: 与min()、max()一样，successor()也需要处理所查询的数据不存在后继的情况(data比二叉树中的所有数据都大)，这时候，该返回什么？在我现有的程序中，这里会产生一个运行时错误(段错误)，懒得去改了，交给下一个版本吧。
8、insert()、remove()函数
因为已经有了search函数，insert函数的实现就比较简单了，将节点与节点用指针连起来即可，需要考虑树为空以及待插入的数据已经存在与树中两种特殊情况。
remove的情况比较复杂，首先当然是以search函数查找待删除的数据所在的节点，如果该数据压根就不存在于二叉树中，那当然是返回false了事，如果存在的话，可以三种情况讨论：
1) 待删除的节点没有子节点，直接将其父节点相应的指针置零，然后回收待删除的节点所占的资源
2) 待删除的节点(设为节点x)有一个子节点，将x的子节点的parent指针指向x的父节点，然后将x的父节点相应的子指针(left或者right)指向x的子节点，最后回收资源
3) 待删除的节点(设为节点x)有两个子节点，我们的做法是删除x的successor节点，然后将所删除的节点中的数据复制到节点x中，这样就等效于删除了x节点，而且保持了二叉树的性质不变(即左边的节点都小于右边的节点)，最后回收所删除的节点所占的资源。
最后，show一下我的remove函数的代码：
template
bool BinTree:: /* return type and scope */
remove(const Data& data)
{
Node *node = search(data);
if(*node == data) /* 主体代码 */
{
/* 指定待删除的节点 */
Node * del;
if(0 == node->left || 0 == node->right)
del = node;
else
del = sub_Tree_Min(node->left);
/*删除*/
Node * child_Of_Del;
if( 0 != del->left )
child_Of_Del = del->left;
else
child_Of_Del = del->right;
/* 将del的子节点的parent指针指向del的父节点,
* 注意这里del是不可能有两个子节点的*/
if( 0 != child_Of_Del) /* del节点有一个子节点 */
child_Of_Del->parent = del->parent;
/* 将del的父节点对应的子指针(left 或者 right)指向del对应的子节点 */
if( 0 == del->parent)
root = child_Of_Del;
else if ( (del->parent)->left ==del)
(del->parent)->left = child_Of_Del;
else
(del->parent)->right = child_Of_Del;
/*
* 处理del != node 的情况
*/
if( del != node )
node->data = del->data;
delete del;
--numOfElem;
return true;
}/* 删除指定数据结束 */
/* 树中不存在数据为data的节点 */
return false;
}/* remove() */
上面的代码没有完全按照前面的分析进行，而是综合了三种情况直接进行控制
阅读(629) | 评论(0) | 转发(0) |
