Java实现二叉树，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

本文来源：https://www.bwwdw.com/article/v923.html