实验报告课程名称：数据结构上机实验名称：二叉树设计专业班级：计1201指导教师：朱战立学生姓名：张文江学号：201107010122实验三二叉树设计题目：二叉树设计一．问题描述：（1）定义二叉链存储结构。（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、遍历二叉树等）。（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。（4）编写测试主函数并上机运行。打印出运行结果，并结合程序运行结果进行分析。二．基本要求：（1）为统一起见，可建立如图8-22的二叉树。（2）遍历二叉树方法应包括前序、中序、后序方法。（3）提交实验报告。三．算法思想：通过建立二叉树结构完成二叉树的插入，并建立题目要求的二叉树，然后，通过遍历二叉树的方法，遍历二叉树，完成二叉树的打印，最后分析运行结果。四．模块划分：头文件中放二叉树结构和遍历树两种方法各自对应的函数，源文件里存放测试函数。五．数据结构：二叉树结构typedefstructNode{DataTypedata;structNode*leftChild;structNode*rightChild;}BiTreeNode;;六．源程序：遍历树头文件//bianli.hvoidPreOrder(BiTreeNode*t,voidvisit(DataTypeitem)){if(t!=NULL){visit(t->data);PreOrder(t->leftChild,visit);PreOrder(t->rightChild,visit);}}voidInOrder(BiTreeNode*t,voidvisit(DataTypeitem)){if(t!=NULL){InOrder(t->leftChild,visit);visit(t->data);InOrder(t->rightChild,visit);}}voidPostOrder(BiTreeNode*t,voidvisit(DataTypeitem)){if(t!=NULL){PostOrder(t->leftChild,visit);PostOrder(t->rightChild,visit);visit(t->data);}}二叉树结构头文件//tree.htypedefstructNode{DataTypedata;structNode*leftChild;structNode*rightChild;}BiTreeNode;voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}voidDestroy(BiTreeNode**root){if((*root)!=NULL&&(*root)->leftChild!=NULL)Destroy(&(*root)->leftChild);if((*root)!=NULL&&(*root)->rightChild!=NULL)Destroy(&(*root)->rightChild);free(*root);}BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->leftChild;s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t;s->rightChild=NULL;curr->leftChild=s;returncurr->leftChild;}BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;if(curr==NULL)returnNULL;t=curr->rightChild;s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t;s->leftChild=NULL;curr->rightChild=s;returncurr->rightChild;}BiTreeNode*DeleteLeftTree(BiTreeNode*curr){if(curr==NULL||curr->leftChild==NULL)returnNULL;Destroy(&curr->leftChild);curr->leftChild=NULL;returncurr;}BiTreeNode*DeleteRightTree(BiTreeNode*curr){if(curr==NULL||curr->rightChild==NULL)returnNULL;Destroy(&curr->rightChild);curr->rightChild=NULL;returncurr;}测试主函数//ceshi.h#include#includetypedefcharDataType;#include"tree.h"#include"bianli.h"voidVisit(DataTypeitem){printf("%c",item);}voidPrintBiTree(BiTreeNode*bt,intn){inti;if(bt==NULL)return;PrintBiTree(bt->rightChild,n+1);for(i=0;i0){printf("---");printf("%c\n",bt->data);}PrintBiTree(bt->leftChild,n+1);}voidmain(void){BiTreeNode*root,*p,*pp;Initiate(&root);p=InsertLeftNode(root,'A');p=InsertLeftNode(p,'B');InsertLeftNode(p,'D');p=InsertRightNode(p,'E');p=InsertLeftNode(p,'G');p=InsertRightNode(root->leftChild,'C');p=InsertLeftNode(p,'F');InsertRightNode(p,'H');PrintBiTree(root,0);printf("前序遍历：");PreOrder(root->leftChild,Visit);printf("\n中序遍历：");InOrder(root->leftChild,Visit);printf("\n后序遍历：");PostOrder(root->leftChild,Visit);printf("\n");Destroy(&root);Initiate(&root);p=InsertLeftNode(root,'A');p=InsertLeftNode(p,'B');pp=p;p=InsertLeftNode(p,'C');InsertLeftNode(p,'E');InsertRightNode(p,'F');p=InsertRightNode(pp,'D');InsertLeftNode(p,'G');InsertRightNode(p,'H');PrintBiTree(root,0);printf("前序遍历：");PreOrder(root->leftChild,Visit);printf("\n中序遍历：");InOrder(root->leftChild,Visit);printf("\n后序遍历：");PostOrder(root->leftChild,Visit);printf("\n");Destroy(&root);}运行结果：测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。
