计软实验报告——二叉树.docx

实验报告:二叉树报告人刘思佳一、实验目的掌握二叉树的存储结构二、实验内容存储1．对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2．按层次输出所有结点。3．输出所有叶子结点。4．将所有左右子树值交换。三、实验步骤和要求1．分别编制实验内容中题2、3、4的三个子程序。2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。4．整理程序清单与所有结果，并写出实验报告。四、实验思路建立二叉树结构：左孩子地址，右孩子地址，结点数值。开始时，建立一个足够大的结构体数组node[100]，有100个元素，用以储存100个结点。定义一个队列queue[100]，用于对节点进行处理。同时建立全局变量front,rear作为首元素和尾元素的坐标。编写进队列函数add，队列初始化函数reset；编写按层输出函数output_layer：将根结点入队列，同时将它的非空左孩子与非空右孩子入队列，然后打印首元素，再将首元素删除。编写输出叶子节点函数output_leaves：入队列方式与上个函数相同，但只将左右孩子均为空的结点打印输出。编写exchange函数，用以实现左右孩子的对调：调换指向左右孩子数值的指针。编写main函数，将output_layer, output_leaves,exchange函数循环调用，直至队列为空。编译，运行。五、程序及运行结果1、程序代码及注释#include stdio.h#include malloc.h#define NULL 0int front=0,rear=0;struct tree//建立结点的结构体{ long data; struct tree *left; struct tree *right;};struct tree *queue[100];void add(struct tree *root)//入队列函数{ rear++; queue[rear]=root; if (rear==100) rear=0;}void output_layer(struct tree *root)//按层输出函数{ if (root-left!=NULL) {add(root-left); if (front==100) front=0;} if (root-right!=NULL) {add(root-right); if (rear==100) rear=0;} printf(%5d,queue[front]-data); queue[front]=NULL; front++;}void output_leaves(struct tree *root)//输出所有叶子结点函数{ if (root-left!=NULL) {add(root-left); if (front==100) front=0;} if (root-right!=NULL) {add(root-right); if (rear==100) rear=0;} if(root-right==NULLroot-left==NULL) printf(%5d,root-data); front++;}void reset()//初始化队列函数{ front=0;rear=0;}void exchange(struct tree *root)//交换左右孩子的函数{ int temp; if(root-right!=NULLroot-left!=NULL) {temp=(root-right)-data; (root-right)-data=(root-left)-data; (root-left)-data=temp;}}void main(){ int i; struct tree node[100];//按图定义所给的二叉树 node[0].data=15; node[0].left=node[1]; node[0].right=node[2]; node[1].data=98; node[1].left=node[3]; node[1].right=node[