今天我也遇到这道题了,经过我的研究,我觉得应该是如下的解答:
首先画出该树 :如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示:
注意这里的指针域为左边表示第一个孩子*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)
}