12信管实验报告(树与二叉树的基本操作_1)

管理 学院 信管 专业 12（1） 班 学号 3112004734 姓名 协作者： 无 教师评定_________________ 实验题目 树与二叉树的基本操作

实验评分表

序评分项目 号 1 完成度 指导教2 实验内容 师评分标3 实验报告 准 4

总结 评分标准 按要求独立完成实验准备、程序调试、实验报告撰写。 （1） 完成功能需求分析、存储结构设计； （2） 程序功能完善、可正常运行； （3） 测试数据正确，分析正确，结论正确。 满分 20 打分 30 内容齐全，符合要求，文理通顺，排版美观。 40 对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。 10 下述代码尽管输入eclipse或者JC验证，绝无弄虚作假

实验报告

一、 实验目的与要求

1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2. 根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、 实验内容

1. 在一棵二叉链表表示的二叉树中,实现以下操作，并说明采用哪种遍历算法,其他遍历算法是否可行。 （1） 输出叶子结点

//求二叉树叶子结点个数的递归算法

（2） public class leaf {//输出叶子结点 （3） （4） （5） （6） （7） （8） （9） （10） （11） （12） （13） （14） （15） （16） （17）

public static void leaf(BinaryTree bitree){ }

public static void leaf(BinaryNode p){ } }

public static void main(String args[]){

String if(p!=null){

if(p.left==null&&p.right==null){ }

leaf(p.left); leaf(p.right);

System.out.println(p.data+\);

leaf(bitree.root);

prelist[]={\,\,\,null,\,null,null,null,\,\,null,null,\,\

\};//先根遍历序列

（18） （19） （20） （21） （22） （23） （24） （25） （26） （27） （28）

} }

BinaryTree bitree=new BinaryTree(prelist);//以先bitree.preOrder();//先根次序遍历的递归算法 leaf(bitree);

String prelist2[]={\,\,null,null,\};//先根遍历序列

BinaryTree bitree2=new BinaryTree(prelist2);//以bitree2.preOrder();//先根次序遍历的递归算法 leaf(bitree2);

根遍历序列构造的一棵二叉树

先根遍历序列构造的一棵二叉树

运算结果：

(2)求二叉树中叶子节点的个数

//求二叉树中叶子结点的个数的递归算法

public class getLeaves{

public static int getLeaves(BinaryTree bitree){ return getLeaves(bitree.root); }

public static int getLeaves(BinaryNode p){ //int i=0; if(p!=null) {

if(p.left==null&&p.right==null){