二叉树的构造与遍历方法

题目二叉树的构造与遍历方法一、实验目的通过实验能熟练掌握二叉树的定义、性质和存储结构;二叉树的遍历和线索以及遍历算法的各种描述形式。二、实验内容用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。三、实验步骤1）定义二叉树和用先序次序构造二叉树。typedefstructBiTNode{//注意采用的是二叉链表作为二叉树的存储结构TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree_PreOrder(BiTree&T){//先序次序构造二叉树TElemTypech;scanf(%c,&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;CreateBiTree_PreOrder(T-lchild);CreateBiTree_PreOrder(T-rchild);}returnOK;}2）根据先序遍历、中序遍历和后序遍历的方法编序相应的函数，如：StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//先序遍历if(T){if((*Visit)(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}returnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历if(T!=NULL){if(InOrderTraverse(T-lchild,Visit))if((*Visit)(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//后序遍历if(T!=NULL){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if((*Visit)(T-data))returnOK;returnERROR;}elsereturnOK;}3、编写各遍历后的输出函数。StatusDisp(TElemTypee){//输出各结点的数据值printf(%3c,e);returnOK;}4、编写主程序调用以上子程序调试实现实验要求的各种遍历。voidmain(){BiTreeT;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);}四、实验程序//利用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。#includestdlib.h#includestdio.h#includemalloc.h#defineOK1#defineERROR0#defineOVERFLOW-2#defineNULL0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;intn=0;StatusCreateBiTree(BiTree&T)//用先序次序构造二叉树{charch;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);}returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//用先序遍历{if(T){if(Visit(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//中序遍历{if(T){if(InOrderTraverse(T-lchild,Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//后序遍历{if(T){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}Statusprintnode(TElemTypee){printf(%c,e);returnOK;}voidmain(){BiTreeT;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);}五、实验的结果：abcdfge