Java实现二叉树,Java实现队列
更新时间:2024-06-23 05:15:01 阅读量: 综合文库 文档下载
- JAVA实现二叉树推荐度:
- 相关推荐
实验 Java 实现二叉树
一、实验目的
利用JAVA的代码实现二叉树的结构
二、实验代码
定义一个结点类:
package com.xiao.tree; /** *
* @author WJQ 树结点类 */
public class TreeNode { /*存数据的*/
private Object value; /*左孩子结点*/
private TreeNode leftChild; /*右孩子结点*/
private TreeNode rightChild; /*以下是setter和getter方法*/ public Object getValue() { return value; }
public void setValue(Object value) { this.value = value; }
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) { this.leftChild = leftChild; }
public TreeNode getRightChild() { return rightChild; }
public void setRightChild(TreeNode rightChild) { this.rightChild = rightChild; } }
定义一个树类:
package com.xiao.tree; /** *
* @author WJQ
* 树的结构,树中只有结点 */
public class Tree { /*结点属性*/
private TreeNode node;
public TreeNode getNode() { return node; }
public void setNode(TreeNode node) { this.node = node; }
}
//定义一个队列类:
package com.xiao.tree; /**
* @author WJQ
* 该类是在向树中加入结点时需要使用的
*/
import java.util.LinkedList;
public class Queue {
private LinkedList list; }
/*一初始化就new一个list*/
public Queue(){
list = new LinkedList(); }
/*结点入队列*/
public void enQueue(TreeNode node){ this.list.add(node); }
/*队首元素出队列*/
public TreeNode outQueue(){
return this.list.removeFirst(); }
/*队列是否为空*/
public boolean isEmpty(){
return this.list.isEmpty(); }
public LinkedList getList() { return list; }
public void setList(LinkedList list) { this.list = list; }
//定义一个二叉树类: package com.xiao.tree; /**
* @author WJQ 二叉树,增加结点,前序遍历,中序遍历,后序遍历 */
public class BinaryTree {
private Tree tree; private Queue queue;
/* 构造函数,初始化的时候就生成一棵树 */ public BinaryTree() { tree = new Tree(); }
/* 向树中插入结点 */
public void insertNode(TreeNode node) {
/* 如果树是空树,则生成一颗树,之后把当前结点插入到树中,作为
根节点 ,根节点处于第0层 */
if (tree.getNode() == null) { tree.setNode(node); return; } else {
/* 根节点入队列 */
queue = new Queue();
queue.enQueue(tree.getNode()); /*
* 队列不空,取出队首结点,如果队首结点的左右孩子有一个为空
的或者都为空,则将新结点插入到相应的左右位置,跳出循环,如果左右孩子都不为空
* ,则左右孩子入队列,继续while循环
*/
while (!queue.isEmpty()) {
TreeNode temp = queue.outQueue(); if (temp.getLeftChild() == null) { temp.setLeftChild(node); return;
} else if (temp.getRightChild() == null) { temp.setRightChild(node); return; } else {
/* 左右孩子不空,左右孩子入队列 */
}
}
}
queue.enQueue(temp.getLeftChild()); queue.enQueue(temp.getRightChild()); } }
/* 中序遍历 */
public void midOrder(TreeNode node) { if (node != null) {
this.midOrder(node.getLeftChild()); System.out.println(node.getValue()); this.midOrder(node.getRightChild()); } }
/* 先序遍历 */
public void frontOrder(TreeNode node) { if (node != null) {
System.out.println(node.getValue()); this.frontOrder(node.getLeftChild()); this.frontOrder(node.getRightChild()); } }
/* 后序遍历 */
public void lastOrder(TreeNode node) { if (node != null) {
this.lastOrder(node.getLeftChild()); this.lastOrder(node.getRightChild()); System.out.println(node.getValue()); } }
public Tree getTree() { return tree; }
最好来一个客户端测试一下:
package com.xiao.tree;
/**
* @author shichao */
public class Client {
public static void main(String[] args) {
/*生成一棵二叉树*/
BinaryTree binaryTree = new BinaryTree(); /*模拟10个结点*/
TreeNode[] nodes = new TreeNode[10];
for (int i = 0; i < nodes.length; i++) { nodes[i] = new TreeNode(); nodes[i].setValue(i);
/*向树中插入结点*/
binaryTree.insertNode(nodes[i]); }
/*先序、中序、后序遍历二叉树*/
System.out.println(\先序遍历。。。。。。。。。。。。。。\);
binaryTree.midOrder(binaryTree.getTree().getNode());
System.out.println(\中序遍历。。。。。。。。。。。。。。\);
binaryTree.frontOrder(binaryTree.getTree().getNode());
System.out.println(\后序遍历。。。。。。。。。。。。。。\);
binaryTree.lastOrder(binaryTree.getTree().getNode()); } }
三、实验结果
输入10个数,0--9的循环,依次用前序 中序 后序遍历,得出的结果如下:
先序遍历。。。。。。。。。。。。。。 7
3 8 1 9 4 0 5 2 6
中序遍历。。。。。。。。。。。。。。 0 1 3 7 8 4 9 2 5 6
后序遍历。。。。。。。。。。。。。。 7 8 3 9 4 1 5 6 2 0
正在阅读:
Java实现二叉树,Java实现队列06-23
2.回归方程复习题09-30
设计链板式输送机传动装置05-23
自制天文望远镜原理 - 图文06-26
华为软件面试03-23
DExcel1108-29
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 实现
- 队列
- Java
- 策马扬鞭争上游
- 高一数学上学期期中考试复习卷1及答案
- 2016—2017学年第二学期小学六年级语文第一次质量检测
- 钢筋类习题
- 结题报告
- ASTM材料查询索引 - 图文
- 市委副书记、市长述职述廉报告
- 实验室管理体系质量手册 - 图文
- 基于胜任力的工程咨询项目经理绩效考核研究
- 心理健康辅导员认证考试试题及答案6套-系列
- 唐山市2017—2018学年度高二年级第一学期期末考试高二英语答案
- 16、河北省衡水中学2012届高三上学期一调考试物理试题
- 小学信息技术三、四年级下册教学计划教案整册(浙江摄影出版社)
- 雷达距离估算
- 风电设备制造项目 - 图文
- 毕业论文答辩开场白大全
- 美术课评课稿
- 应急预案演练记录表
- 黑莓秘籍
- 2018-2024年汽车轮毂行业市场运营模式分析及发展趋势预测研究报