数据结构学习之二叉树(实践篇)(三)
( *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) 对原左、右子树结构体相关域的清空操作。
四、遍历二叉树
遍历二叉树是指按照一定的规律，对二叉树的每个结点访问且仅访问一次的处理过程。这里的“访问”是泛指对结点数据的某种处理操作，如可以是printf打印显示，可以是链表的插入操作，也可以是某些数学运算，等等。
遍历的目的：通过一次遍历后，可以使树中结点的非线性结构按访问的先后顺序转变为某种线性序列。如：可以按照访问的先后顺序将数据域逐一填入某一数组中，当然，也可以插入某个链表中，然后通过链表的方式对数据域进行访问。
遍历的次序: DLR先序遍历、LDR中序遍历、LRD后序遍历
可以看出，先、中、后序的遍历主要根据根结点的访问次序命名，而L左结点总是先于R右结点访问。无论是哪种遍历方式，其核心的思想是总是递归，以中序遍历二叉树为例，说明其算法思想：
若二叉树非空，则：
1)中序遍历左子树
2)访问根结点
3)中序遍历右子树
(1)先序遍历二叉树
[cpp]
/* preorder */
int preorder(const BiTreeNode *node, List *list)
{
if( !bitree_is_eob(node) )
{
if( list_ins_next(list, list_tail(list), bitree_data(node) ) != 0 )
{
return -1;
}
if( !bitree_is_eob( bitree_left(node) ) )
{
if( preorder(bitree_left(node), list) != 0 )
return -1;
}
if( !bitree_is_eob( bitree_right(node) ) )
{
if( preorder(bitree_right(node), list) != 0 )
return -1;
}
}
return 0;
}
(2)中序遍历二叉树
[html]
/* inorder */
int inorder(const BiTreeNode *node, List *list)
{
if( !bitree_is_eob(node) )
{
if( !bitree_is_eob(bitree_left(node)) )
{
if( inorder( bitree_left(node), list ) != 0 )
return -1;
}
if( list_ins_next(list, list_tail(list), bitree_data(node)) != 0 )
{
return -1;
}
if( !bitree_is_eob(bitree_right(node)) )
{
if( inorder( bitree_right(node), list ) != 0 )
return -1;
}
}