二叉树的构造与遍历方法_二叉树的构造及遍历

二叉树的构造与遍历方法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树的构造及遍历”。

题目

二叉树的构造与遍历方法

一、实验目的通过实验能熟练掌握二叉树的定义、性质和存储结构;二叉树的遍历和线索以及遍历算法的各种描述形式。

二、实验内容

用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。

三、实验步骤

1）定义二叉树和用先序次序构造二叉树。

typedef struct BiTNode { //注意采用的是二叉链表作为二叉树的存储结构

TElemType data;struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;Status CreateBiTree_PreOrder(BiTree &T){ //先序次序构造二叉树

} 2）根据先序遍历、中序遍历和后序遍历的方法编序相应的函数，如： Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //先序遍历

TElemType ch;scanf(“%c”,&ch);if(ch==' ')T=NULL;else {

} return OK;if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree_PreOrder(T->lchild);CreateBiTree_PreOrder(T->rchild);if(T){

}

if((*Visit)(T->data))

if(PreOrderTraverse(T->lchild,Visit))

if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;} return OK;Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //中序遍历

} Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //后序遍历

} if(T!=NULL){

if(PostOrderTraverse(T->lchild,Visit))

if(PostOrderTraverse(T->rchild,Visit))

if((*Visit)(T->data))return OK;if(T!=NULL){

if(InOrderTraverse(T->lchild,Visit))

if((*Visit)(T->data))

if(InOrderTraverse(T->rchild,Visit))return OK;return ERROR;} else return OK;return ERROR;} else return OK;

3、编写各遍历后的输出函数。

Status Disp(TElemType e){ //输出各结点的数据值

} printf(“%3c”,e);return OK;

4、编写主程序调用以上子程序调试实现实验要求的各种遍历。

void main(){

BiTree T;printf(“输入要构造的二叉树：n”);

CreateBiTree(T);printf(“n”);printf(“用先序遍历的方式遍历此二叉树为:n”);PreOrderTraverse(T, printnode);printf(“n”);printf(“用中序遍历的方式遍历此二叉树为:n”);InOrderTraverse(T, printnode);

printf(“n”);printf(“用后序遍历的方式遍历此二叉树为:n”);PostOrderTraverse(T, printnode);printf(“n”);}

四、实验程序

//利用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。#include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define NULL 0 typedef char TElemType;typedef int Status;typedef struct BiTNode {

TElemType data;

struct BiTNode

*lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;int n=0;Status CreateBiTree(BiTree &T)//用先序次序构造二叉树 {

char ch;scanf(“%c”,&ch);

if(ch==' ')T=NULL;else

{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data = ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

return OK;} Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//用先序遍历 {

if(T)

{

if(Visit(T->data))

if(PreOrderTraverse(T->lchild,Visit))

if(PreOrderTraverse(T->rchild,Visit))

return OK;

return ERROR;

}else

return OK;}

Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//中序遍历 { if(T){

if(InOrderTraverse(T->lchild,Visit))

if(Visit(T->data))

if(InOrderTraverse(T->rchild,Visit))

return OK;

return ERROR;

}else

return OK;} Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e))//后序遍历 { if(T){

if(PostOrderTraverse(T->lchild,Visit))

if(PostOrderTraverse(T->rchild,Visit))

if(Visit(T->data))

return OK;

return ERROR;

}else

return OK;} Status printnode(TElemType e){ printf(“ %c”,e);return OK;} void main()

{

BiTree T;printf(“输入要构造的二叉树：n”);

CreateBiTree(T);

} printf(“n”);printf(“用先序遍历的方式遍历此二叉树为:n”);PreOrderTraverse(T, printnode);printf(“n”);printf(“用中序遍历的方式遍历此二叉树为:n”);InOrderTraverse(T, printnode);printf(“n”);printf(“用后序遍历的方式遍历此二叉树为:n”);PostOrderTraverse(T, printnode);printf(“n”);

五、实验的结果：

a b c d f e g

二叉树遍历

目录一 设计思想 ..........................................2 1递归遍历二叉树算法思想：.......................................2 2非递归遍历二叉树算法思想：.................

二叉树遍历课程设计】

数据结构程序设计报告学院： 班级： 学号：姓名：实验名称：二叉树的建立与遍历一、实验目的：1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法；3.掌握二叉树的先序、中序、后序的......

二叉树的遍历

# include # include typedef int Etype; typedef struct BiTNode /* 树结点结构 */{ Etype data;struct BiTNode *lch,*rch;}BiTNode; /* 函数原形声明 */ BiTNode *cr......

二叉树的遍历算法

实验三 二叉树遍历算法一、实验目的1． 进一步理解掌握二叉树二叉链表存储结构。 2． 掌握二叉树遍历的递归与非递归算法。二、实验要求1． 认真阅读和掌握（先序、中序、后序和层次......

第四次实验二叉树遍历

一、二叉链表的声明 .BinaryNode public cla BinaryNode //二叉树的二叉链表结点类，泛型T指//定结点的元素类型 {public T data;//数据域，存储数据元素public BinaryNode left......