数据结构学习之二叉树(实践篇)(二)
[cpp]
/* bitree_destroy */
void bitree_destroy(BiTree *tree)
{
/* Remove all the nodes from the tree */
bitree_rem_left(tree, NULL);
memset(tree, 0, sizeof(BiTree) );
return;
}
先删除二叉树的所有结点，然后清空二叉树结构体。
3、二叉树插入操作(bitree_ins_left及bitree_ins_right)
先是插入左子树操作：
[cpp]
/* bitree_ins_left */
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data)
{
BiTreeNode *new_node, **position;
if( node == NULL )
{
if( bitree_size(tree) > 0 )
return -1;
position = &tree->root;
}
else
{
if( bitree_left(node) != NULL )
return -1;
position = &node->left;
}
/* Allocate storage for the node */
new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode));
if( new_node == NULL )
return -1;
/* insert the node into the tree */
new_node->data = (void *)data;
new_node->left = NULL;
new_node->right = NULL;
*position = new_node;
tree->size++;
return 0;
}
接着是插入右子树操作：
[cpp]
/* bitree_ins_right */
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data)
{
BiTreeNode *new_node, **position;
if( node == NULL )
{
if( bitree_size(tree) > 0 )
return -1;
position = &tree->root;
}
else
{
if( bitree_right(node) != NULL )
return -1;
position = &node->right;
}
/* allocate the storage for the node. */
new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode));
if( new_node == NULL )
return -1;
new_node->data = (void *)data;
new_node->left = NULL;
new_node->right = NULL;
*position = new_node;
tree->size++;
return 0;
}
通过代码可以看出，这两个函数的实现几乎一样，我们这里只需要学会其内在思想：
(1) 找准需要插入的位置：是在根结点位置，当前结点的左指针还是右指针位置。
(2) 分配新结点，在适当的地方插入结点： *position = new_node完成了这个插入操作
(3) 更新二叉树size域。
4、二叉树删除操作(bitree_rem_left及bitre_rem_right)
先是删除左子树操作：
[cpp]
/* bitree_rem_left */
void bitree_rem_left(BiTree *tree, BiTreeNode *node)
{
BiTreeNode **position;
/* Do not allow removal from an empty tree. */
if( bitree_size(tree) == 0 )
return;
if( node == NULL )
{
position = &tree->root;
}
else
{
position = &node->left;
}
/* Remove the nodes. */
if( *position != NULL )
{
bitree_rem_left(tree, *position);
bitree_rem_right(tree, *position);
if( tree->destroy != NULL )
{
tree->destroy((*position)->data);
}
free(*position);
*position = NULL;
/* adjust the size */
tree->size--;
}
return;
}
接着是删除右子树操作：
[cpp]
/* bitree_rem_right */
void bitree_rem_right(BiTree *tree, BiTreeNode *node)
{
BiTreeNode **position;
if( bitree_size(tree) == 0 )
return;
if( node == NULL )
{
position = &tree->root;
}
else
{
position = &node->right;
}
/* Remove the nodes */
if