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( *position != NULL )
{
bitree_rem_left(tree, *position);
bitree_rem_right(tree, *position);
if( tree->destroy != NULL )
{
tree->destroy((*position)->data);
}
free(*position);
*position = NULL;
tree->size--;
}
return;
}
同样的，我们需要掌握其实现的思想：
通过采用递归的思想，后序遍历逐层深入到最底层(深度优先搜索)，从下至上逐一删除各个结点，释放被删除结点的数据域空间，更新二叉树size值大小。注意递归退出的条件:
(1) 树为空时退出
(2) *Position为空时退出
可以思考：为何删除操作不能采用前序或中序遍历
5、二叉树的合并(bitree_merge)
[cpp]
/* bitree_merge */
int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data)
{
/* Initialize the merged tree. */
bitree_init(merge, left->destroy);
/* Insert the data for the root node of the merged tree */
if( bitree_ins_left(merge, NULL, data) != 0 )
{
bitree_destroy(merge);
return -1;
}
/* Merge the two binary trees into a single binary tree */
bitree_root(merge)->left = bitree_root(left);
bitree_root(merge)->right = bitree_root(right);
/* Adjust the size of the new tree */
merge->size = merge->size + bitree_size(left) + bitree_size(right);
/* Do not let the original trees access the merged nodes. */
left->root = NULL;
left->size = 0;
right->root = NULL;
right->size = 0;
return 0;
}
二叉树的合并操作非常简单，有以下几个步骤：
(1) 初始化新二叉树,并插入data域成为新二叉树的根结点
(2) 新二叉树的左指针指向左子树的根结点
(3) 新二叉树的右指针指向右子树的根结点
(4) 新二叉树结点个数 =左、右子树结点之和+1
(5) 对原左、右子树结构体相关域的清空操作。