今天我也遇到这道题了，经过我的研究，我觉得应该是如下的解答：
首先画出该树 ：如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示：
注意这里的指针域为左边表示第一个孩子*firstchild，右边表示兄弟*nextsibling
紧接着就涉及到了树与二叉树的转换：
核心思想：左子树放孩子，右子树放兄弟，则有如图所示的二叉树：
下面是一个用递归方法
编的二叉树遍历程序，供lz参考。
#include
<stdio.h>//头文件
#include
<stdlib.h>
#include
<malloc.h>
typedef
struct
bitnode
{
char
data
struct
bitnode
*lchild,*rchild
}
bitnode,*bitree//定义结点类型
bitree
createbitree()//创建树
{
char
pbitree
t
scanf("%c",&p)
if(p=='
')
t=null
else
{
t=(bitnode
*)malloc(sizeof(bitnode))//为结点开辟空间
t->data=p
t->lchild=createbitree()
t->rchild=createbitree()
}
return
(t)
}
void
preorder(bitree
t)//
先序
{
if(t!=null)
{
printf("%c",t->data)
preorder(t->lchild)
preorder(t->rchild)
}
}
void
inorder(bitree
t)//
中序
{
if(t!=null)
{
inorder(t->lchild)
printf("%c",t->data)
inorder(t->rchild)
}
}
void
postorder(bitree
t)//
后序
{
if(t!=null)
{
postorder(t->lchild)
postorder(t->rchild)
printf("%c",t->data)
}
}
void
main()//主函数
{
bitree
ta
ta=createbitree()
printf("先序遍历:")
printf("\n")
preorder(ta)
printf("\n")
printf("中序遍历:")
printf("\n")
inorder(ta)
printf("\n")
printf("后序遍历:")
printf("\n")
postorder(ta)
}
由于二叉查找树中对信息进行了排序，因而按顺序列出说有的关键字会很简单，递归过程如下：
毫无疑问，该过程能够解决将关键字排序列出的问题。正如我们前面看到的，这类例程当用到树的时候称为中序遍历（由于它依序列出了关键字，因此是有意义的）。中序遍历的一般策略是首先遍历左子树，然后是当前节点，最后遍历右子树。这个算法的有趣部分除它简单的特性外，还在于其总的运行时间是 。这是因为在树的每一个节点处运行的工作都是常数时间的。每一个节点访问依次，而在每一个节点进行的工作是检测是否为 NULL，建立两个过程调用并执行 PrintElement 。由于在每个节点的工作花费常数时间以及总共有 N 个节点，因此运行时间为 。
有时我们需要先处理两棵子树然后才能处理当前节点。例如，为了计算一个节点的高度，我们需要知道它的两棵子树的高度。如下计算高度的例程：
由于检查一些特殊的情况总是有益的（当涉及递归时尤其重要），因此要注意这个例程声明树叶的高度为零，这是正确的。这种一般的遍历顺序叫做后序遍历。因为在每个节点的工作花费常数时间，所以总的运行时间也是 。
第三种常用的遍历方案为先序遍历（preorder traversal）。这里，当前节点在其儿子节点之前处理。这种遍历可以利用节点深度标志每一个节点。
所有这些例程都有一个共有的想法，那就是首先处理 NULL 的情形，然后才是其余的工作。注意，此处缺少一些额外的变量。这些例程仅仅传递了树，并没有声明或是传递任何额外的变量。程序越紧凑，一些愚蠢的错误出现的可能就越小。
第四种遍历用得很少，叫做层序遍历（level-order-traversal）。在层序遍历中，所有深度为 D 的节点要在深度为 D+1 的节点之前处理。层序遍历与其他类型的遍历不同的地方在于它不是递归实施的；它用到队列，而不使用递归所默示的栈。
