c语言如何实现一棵二叉树的遍历

Python027

c语言如何实现一棵二叉树的遍历,第1张

今天我也遇到这道题了,经过我的研究,我觉得应该是如下的解答:

首先画出该树 :如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示:

注意这里的指针域为左边表示第一个孩子*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)

}