数据结构学习之二叉树(实践篇)(四)
return 0;
}
(3)后序遍历二叉树
[cpp]
/* postorder */
int postorder(const BiTreeNode *node, List *list)
{
if( !bitree_is_eob(node) )
{
if( !bitree_is_eob(bitree_left(node)) )
{
if( postorder(bitree_left(node), list) != 0 )
return -1;
}
if( !bitree_is_eob(bitree_right(node)) )
{
if( postorder(bitree_right(node), list) != 0 )
return -1;
}
if( list_ins_next(list, list_tail(list), bitree_data(node)) != 0 )
return -1;
}
return 0;
}
在本例的三种遍历代码中，“访问”的方式是将结点的数据域插入至某一链表结构中。
五、二叉树简单应用
对上述所有二叉树的代码如果未进行使用或验证，无疑是一些基本符号，没有任何的意义，所以本节主要对前面二叉树的各个接口进行简单的应用测试，在进入实际的应用之前，有几个函数需要先实现，如下：
[cpp]
/* destroy */
void destroy(void *data)
{
free(data);
return;
}
这是创建销毁函数的代码，在bitree_init()初始化二叉树时需要传递它的函数入口地址。接着是创建二叉树的函数：
[cpp]
/* create_tree */
int create_tree(BiTree *tree, BiTreeNode *node)
{
int ret;
int *int_ptr = NULL;
char ch;
scanf("%c", &ch);
if( ch == '#' )
{
return 0;
}
int_ptr = (int *)malloc(sizeof(int));
if( int_ptr == NULL )
return -1;
*int_ptr = ch-48;
if( node == NULL )
{
bitree_init(tree, destroy);
ret = bitree_ins_left(tree, NULL, (void *)int_ptr);
if( ret != 0 )
{
free(int_ptr);
return -1;
}
printf("root is %d\n", *(int *)bitree_data(tree->root));
create_tree(tree, tree->
root);
}
else
{
//insert the data into left tree
ret = bitree_ins_left(tree, node, (void *)int_ptr);
if( ret != 0 )
{
free(int_ptr);
return -1;
}
printf("node: %d 's left node is :%d\n", *(int *)bitree_data(node), *(int *)bitree_data(node->left));
ret = create_tree(tree, node->left);
scanf("%c", &ch);
if( ch == '#')
return 0;
int_ptr = (int *)malloc(sizeof(int));
if( int_ptr == NULL )
return -1;
*int_ptr = ch-48;
// insert the data into right tree.
ret = bitree_ins_right(tree, node, (void *)int_ptr);
if( ret != 0 )
{
free(int_ptr);
return -1;
}
printf("node: %d 's right node is :%d\n", *(int *)bitree_data(node), *(int *)bitree_data(node->right));
ret = create_tree(tree, node->right);
}
return 0;
}
它的实现逻辑比较简单，在于采用递归的思想来创建一棵二叉树，并且其递归退出的条件是输入“#”符号，注意：本代码的实现只能插入简单的数字（范围0-9），这对于简单测试来说已经足够了。
下面是具体的关于二叉树各接口代码的简单测试应用，如下：
[cpp]
/* main */
int main(int argc, char **argv)
{
int ret;
int *int_ptr;
BiTree tree1, tree2, tree_merge;
List list;
ListElmt *member;
BiTreeNode *nd;
/* tree1 as follows :
1
/ \
2 5
/ \ / \
3 4 6 7
*/
create_tree(&tree1, NULL); //input "123#4#56#7#"
printf("\nstep1:tree1 build success\n");
/* tree2 as follows:
0
/ \
8 9
/ \ /
6 7 3
*/
i