实验5_二叉树

第一篇：实验5_二叉树

赣南师范大学数学与计算机科学学院

实 验 报 告 册

课程名称：算法与数据结构

实验项目名称： 实验5.二叉树 实验学时： 4 学生学号与姓名： 实验地点： 数计楼四楼 实验日期： 年 月 日 指导老师：

实验5 二叉树

一、实验目的和要求

（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。

二、实验仪器和设备

Visual C++ 6.0

三、实验内容与过程

1.建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。

2.在第一题基础上，求二叉树中叶结点的个数。3.在第一题基础上，求二叉树的深度。

程序清单： 1.2.3.赣南师范大学数学与计算机科学学院

四、实验结果与分析（程序运行结果及其分析）

五、实验体会（遇到问题及解决办法，编程后的心得体会）

第二篇：第四次实验--二叉树遍历

一、二叉链表的声明.BinaryNode public class BinaryNode //二叉树的二叉链表结点类，泛型T指//定结点的元素类型 {

public T data;

//数据域，存储数据元素

public BinaryNode left, right;

//链域，分别指向左、右孩子结点

//构造结点，参数分别指定元素和左、右孩子结点

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ this.data = data;this.left = left;this.right = right;

}

public BinaryNode(T data)

//构造指定值的叶子结点

{ this(data, null, null);

} publicBinaryNode()

{ this(null, null, null);

}

//可声明以下方法 public String toString()

{ returnthis.data.toString();

}

public boolean equals(Object obj)

//比较两个结点值是否相等，覆盖Object

//类的equals(obj)方法

{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode)obj).data);

}

public booleanisLeaf()

//判断是否叶子结点

{ returnthis.left==null &&this.right==null;

} } 二、二叉树中的遍历方法的声明.BinaryTree public class BinaryTree {

public BinaryNode root;

//根结点，结点结构为二叉链表

public BinaryTree()

//构造空二叉树

{ this.root=null;

}

public booleanisEmpty()

//判断二叉树是否空

{ returnthis.root==null;

}

//二叉树的先根、中根和后根次序遍历算法

public void preOrder()

//先根次序遍历二叉树

{ System.out.print(“先根次序遍历二叉树：

”);preOrder(root);//调用先根次序遍历二叉树的递归方法 System.out.println();

}

public void preOrder(BinaryNode p)

//先根次序遍历以p结点为根的子二叉

//递归方法

{ if(p!=null)

//若二叉树不空

{ System.out.print(p.data.toString()+“ ”);//访问当前结点

preOrder(p.left);

//按先根次序遍历当前结点的左子树，//递归调用 preOrder(p.right);

//按先根次序遍历当前结点的右子树

//递归调用

}

}

public String toString()

//返回先根次序遍历二叉树所有结点的描述字符串

{ returntoString(root);

}

private String toString(BinaryNode p)

//返回先根次序遍历以p为根的子树描述字

//符串，递归算法

{ if(p==null)return “";

return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//递归调用

}

public void inOrder()

//中根次序遍历二叉树

{ System.out.print(”中根次序遍历二叉树：

“);inOrder(root);System.out.println();

}

public void inOrder(BinaryNode p)

//中根次序遍历以p结点为根的子二叉

//递归方法

{ if(p!=null)

{ inOrder(p.left);

//中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+” “);inOrder(p.right);

//中根次序遍历右子树，递归调用

}

}

public void postOrder()

//后根次序遍历二叉树

{ System.out.print(”后根次序遍历二叉树：

“);postOrder(root);System.out.println();

}

public void postOrder(BinaryNode p)

//后根次序遍历以p结点为根的子二叉树，//递归方法

{ if(p!=null)

{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);

}

}

public BinaryTree(T[] prelist, T[] inlist)

//以先根和中根序列构造二叉树

{ this.root = create(prelist, inlist, 0, 0, prelist.length);

} //以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度.//返回所创建子树的根结点

privateBinaryNode create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println();

if(n<=0)return null;

T elem=prelist[preStart];

//根结点值 BinaryNode p=new BinaryNode(elem);

//创建叶子结点 inti=0;while(i

//在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i);

//创建左子树 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//创建右子树 return p;

} private void print(T[] table, int start, int n)

{ for(inti=0;i

}

public BinaryTree(T[] prelist)

//以标明空子树的先根序列构造二叉树

{ this.root = create(prelist);

}

//以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 privateinti=0;privateBinaryNode create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String

{

p = new BinaryNode(elem);

//创建叶子结点 p.left = create(prelist);

//创建p的左子树 p.right = create(prelist);

//创建p的右子树

}

} return p;

}

}

三、运行程序

.BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树

public class BinaryTree_make {

public static BinaryTree make()

//构造给定的一棵二叉树

{ BinaryTreebitree=new BinaryTree();//创建空二叉树

BinaryNodechild_f, child_d, child_b, child_c;//创建4个二叉链表域 child_d = new BinaryNode(”D“, null, new BinaryNode(”G“));child_b = new BinaryNode(”B“, child_d, null);child_f = new BinaryNode(”F“, new BinaryNode(”H“), null);child_c = new BinaryNode(”C“, new BinaryNode(”E“), child_f);bitree.root = new BinaryNode(”小唐“, child_b, child_c);//创建根结点 returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍历二叉树 bitree.inOrder();//中根遍历 bitree.postOrder();

//后根遍历

String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根两种遍历

String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"};

//确定一颗二叉树 BinaryTree bitree1 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍历

bitree1.inOrder();//中根遍历

bitree1.postOrder();

} }

//后根遍历

四、运行结果

五、实验内容

1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历

六、附加实验内容

在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。

七、实验报告要求

1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。

2.心得体会不可为空（可写对此次实验的看法，亦可写自己近来学习数据结构的感受等等，内容不限）

第三篇：实验8 二叉树的基本操作

实验8 二叉树的基本操作

班级: 学号:

一、题目

由数字序列生成二叉树 假设我们有这样的二叉树：

节点的元素(key)是正整数，且互不相同。可能给出这样一个虚拟的树更有利于理解输入。是的，我们的输入是上图的先序遍历；

即,要求根据1 3 0 2 0 0 4 5 0 0 0这样的输入，构造出一棵只含有正整数节点的二叉树。

【输入】

扩展的二叉树的先序遍历 【输出】

构造的简单树的节点个数 【样例输入】 3 0 2 0 0 4 5 0 0 0 【样例输出】

二、程序清单

三、程序调试过程中所出现的错误

四、运行结果（界面）：

五、心得体会

第四篇：实验三 二叉树基本操作与应用实验

实验三

二叉树基本操作与应用实验

第三次实验主要包括两部分内容：1.二叉树基本操作实验；2.二叉树应用—赫夫曼树与赫夫曼编码实验。基本操作包括存储结构建立和遍历算法，本文只给出部分参考程序，请大家尽量完成多数基本操作。

第一部分 基本操作实验

[问题描述] 二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作

1．按先序序列构造一棵二叉链表表示的二叉树T；

2．对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点 的遍历序列；

3．求二叉树的深度，结点数目，叶结点数目； [数据描述] ／／二叉树的二叉链表存储表示 先序遍历二叉树递归算法

6.层次遍历二叉树的非递归算法

7.求二叉树的深度

[说明]

1．按先序次序输入二叉树中结点的值，用‘#’表示空树，对每一个结点应当确定其左右子树的值(为空时必须用特定的空字符占位)，故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定。若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列。

2．为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然后通过函数指针进行函数的调用。读者若有兴趣，可自行编写。

3．c语言函数参数传递，都是以“传值”的方式，故在设计函数时，必须注意参数的传递。若想通过函数修改实际参数的值，则必须用指针变量作参数。具体设计时；读者一定要把指针变量及指针变量指向的值等概念弄清楚。

4．完整参考程序只给出了部分遍历算法，对于其他算法，请读者参照示例，自行编程完成，以加深学习体会。对于二叉链表的建立也是如此，示例中只是给出了先序法建立过程，读者可自行练习中序、后序二叉链表建立法，叶子结点或二叉树结点总数求法等。

第二部分 二叉树应用实验

---------郝夫曼树与郝夫曼编码

[问题描述] 利用HuffMan编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码(复原)。对于有些信道，每端都需要一个完整的编／译码系统。试为这样的信息收发站编写一个Huffman的编／译码系统。给定一组权值{7，9，5，6，10，l，13，15，4，8}．构造一棵赫夫曼树，并计算带权路径长度WPL。

Huffman编码存在磁盘文件中。提出这些要求，是给读者一定的思考空间和提高自己的编程能力的机会。读者需要注意类c语言描述的算法在转变为C源程序时关于函数参数的处理以及其他变量的定义与使用方法。

2．读者可参考此程序，实现Huffman编／译码系统的其他算法，以进一步加深理解和体会。

心得体会

(1)通信领域的编码问题曾经对许多的通信技术专家形成了困扰，后来人们对树型数据结构有了一定的认识之后，才有效地解决了通信的编码需求。它不仅使通信编码的长度缩短，更实际的意义是使整个电文的长度大大缩短了，从而迅速地提高了通信的效率。

(2)树型数据结构不仅使各类实际应用问题找到了一种有效解决途径，而且它也对计算机科学技术本身的发展起到了非常重要的作用，如在编译原理过程中的编码问题，使得编译系统提高了速度。

第五篇：实验3 - 二叉树的建立及基本操作

实验三

实验目的：

二叉树的建立及基本操作

本次实验的主要目的是熟练掌握二叉树的定义、三序（先序、中序、后序）遍历方法，并用遍历思想求解具体二叉树应用问题。通过程序实现，体会递归算法的优缺点。

实验要求：

用C语言编程实现二叉树的基本操作，并完成下述函数功能：(1)CreateBiTree()：根据先序遍历序列生成一棵二叉树(2)Depth()：求此二叉树的深度

(3)CountLeaf()：统计该二叉树中叶子结点的个数(4)InOrderTraverse()：中序遍历二叉树(5)PostOrderTraverse()：后序遍历二叉树

在主函数main()中调用各个子函数完成单链表的基本操作。例： void main(){ BiTree T;CreateBiTree(T);int d= Depth(T);printf(“深度为%d”, d);int num= CountLeaf(T);printf(“叶子结点个数为%d”, num);InOrderTraverse(T);PostOrderTraverse(T);} //注意函数调用时，只传递参数名称，不需要传递参数类型和&符号。

[实现提示] 采用特殊符号，如*号表示空树的情况。

通过输入扩展的先序序列建立一棵二叉树，即，二叉树中结点为空时应输入*符号表示。[测试数据] 由学生自己确定，注意边界数据。

程序检查时，由老师提供用于建树的初始输入序列。

程序源码：（后付纸）程序运行结果：

实验心得体会：

有一些概念不明白，看书之后弄懂了，仔细看了二叉树遍历的知识点，问了同学有了思路。熟悉了二叉树的基本操作，掌握了二叉树实现。