教育改变生活
标题:
【数据结构】二叉树先序遍历递归实现
[打印本页]
作者:
wander
时间:
2023-9-5 15:58
标题:
【数据结构】二叉树先序遍历递归实现
本帖最后由 wander 于 2023-9-5 16:01 编辑
二叉树的先序遍历采用的是递归的思想,因此图1所示的二叉树可以递归实现,其 C 语言实现代码为:
图 1 二叉树
#include
<stdio.h>
#include
<string.h>
#define
TElemType
int
//构造结点的结构体
typedef
struct
BiTNode
{
TElemType data
;
//数据域
struct
BiTNode
*
lchild
,*
rchild
;
//左右孩子指针
}
BiTNode
,*
BiTree
;
//初始化树的函数
void
CreateBiTree
(
BiTree
*
T
)
{
*
T
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
data
=
1
;
(*
T
)->
lchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
rchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
lchild
->
data
=
2
;
(*
T
)->
lchild
->
lchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
lchild
->
rchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
lchild
->
rchild
->
data
=
5
;
(*
T
)->
lchild
->
rchild
->
lchild
=
NULL
;
(*
T
)->
lchild
->
rchild
->
rchild
=
NULL
;
(*
T
)->
rchild
->
data
=
3
;
(*
T
)->
rchild
->
lchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
rchild
->
lchild
->
data
=
6
;
(*
T
)->
rchild
->
lchild
->
lchild
=
NULL
;
(*
T
)->
rchild
->
lchild
->
rchild
=
NULL
;
(*
T
)->
rchild
->
rchild
=(
BiTNode
*)
malloc
(
sizeof
(
BiTNode
));
(*
T
)->
rchild
->
rchild
->
data
=
7
;
(*
T
)->
rchild
->
rchild
->
lchild
=
NULL
;
(*
T
)->
rchild
->
rchild
->
rchild
=
NULL
;
(*
T
)->
lchild
->
lchild
->
data
=
4
;
(*
T
)->
lchild
->
lchild
->
lchild
=
NULL
;
(*
T
)->
lchild
->
lchild
->
rchild
=
NULL
;
}
//模拟操作结点元素的函数,输出结点本身的数值
void
displayElem
(
BiTNode
*
elem
)
{
printf
(
"%d "
,
elem
->
data
);
}
//先序遍历
void
PreOrderTraverse
(
BiTree T
)
{
if
(
T
)
{
displayElem
(
T
);
//调用操作结点数据的函数方法
PreOrderTraverse
(
T
->
lchild
);
//访问该结点的左孩子
PreOrderTraverse
(
T
->
rchild
);
//访问该结点的右孩子
}
//如果结点为空,返回上一层
return
;
}
int
main
()
{
BiTree Tree
;
CreateBiTree
(&
Tree
);
printf
(
"先序遍历:
\n
"
);
PreOrderTraverse
(
Tree
);
}
运行结果:
先序遍历:
1 2 4 5 3 6 7
欢迎光临 教育改变生活 (http://bbs.goldoar.com/)
Powered by Discuz! X3.2