四、遍历二叉树
遍历二叉树是指按照一定的规律，对二叉树的每个结点访问且仅访问一次的处理过程。这里的“访问”是泛指对结点数据的某种处理操作，如可以是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;
}
}
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)，这对于简单测试来说已经足够了。