实验 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;