java 二叉树图形_java实现二叉树以及实例

二叉树的设计与遍历

目的和要求：

(1)正确定义二叉树结点

(2)掌握定义二叉树的方法

(3)掌握采用先序创建二叉树的方法

(4)掌握二叉树的先序、中序和后序遍历算法

实验原理及内容：

(1)二叉树的定义；

(2)采用先序创建二叉树

(3)二叉树的先序、中序和后序遍历算法实现

实验步骤：

(1)二叉树的定义；

(2)采用先序创建二叉树

(3)二叉树的先序、中序和后序遍历算法实现

实验过程：

(一)实训说明

本实训给出了二叉树方法集合，即接口，同时提供了二叉树结点的定义，对于二叉树，提供了先序创建二叉树的方法，通过调用该方法，即可创建二叉树。

要求完成二叉树的先序、中序和后序遍历算法。

第二个代码纯属转载，注转载地址如下：

http://www.cnblogs.com/CherishFX/p/4617105.html

再注：

第一个为学习代码，测试的添加的图形为下面的二叉树。此为按图添加。

第二个为使用代码，添加的图形可以任意。

第一个代码测试类添加的固定代码如下：

第一个学习代码如下：

(1)二叉树结点定义

/*

* 二叉树结点定义

*/

public class TreeNode {

// 属性

private E data; // 结点元素值

private TreeNode lchild; // 左孩子结点

private TreeNode rchild; // 右孩子结点

// get和set方法

public E getData() {

return data;

}

public void setData(E data) {

this.data = data;

}

public TreeNode getLchild() {

return lchild;

}

public void setLchild(TreeNode lchild) {

this.lchild = lchild;

}

public TreeNode getRchild() {

return rchild;

}

public void setRchild(TreeNode rchild) {

this.rchild = rchild;

}

// 构造方法,三个参数

public TreeNode(E data, TreeNode lchild, TreeNode rchild) {

this.data = data;

this.lchild = lchild;

this.rchild = rchild;

}

// 构造方法,三个参数

public TreeNode(E data) {

this.data = data;

this.lchild = this.rchild = null;

}

// 构造方法,无参数

public TreeNode() {

this(null);

}

}

}

(2)二叉树的操作接口定义

public interface IBiTree {

void create(E val, TreeNodel, TreeNode r);//以val为根节点元素，l和r为左右子树构造二叉树

void insertL(E val, TreeNode p);//将元素插入p的左子树

void insertR(E val, TreeNode p);//将元素插入p的右子树

TreeNode deleteL(TreeNode p) ;//删除p的左子树

TreeNode deleteR(TreeNode p);//删除p的右子树

TreeNode search(TreeNode root, E value) ;//在root树中查找结点元素为value的结点

void traverse(TreeNode root, int i);//按某种方式i遍历root二权树

}

(3)二叉树的定义及方法实现

public class LinkBiTree implements IBiTree {

private TreeNode head; // 链表头引用指针

public TreeNode getHead() {

return head;

}

// 构造函数,生成一棵以val为根结点数据域信息，以二叉树lp和rp为左子树和右子树的二叉树。

public LinkBiTree(E val, TreeNode lp, TreeNode rp) {

TreeNode p = new TreeNode(val, lp, rp);

head = p;

}

// 构造函数,生成一棵以val为根结点数据域信息的二叉树

public LinkBiTree(E val) {

this(val, null, null);

}

// 构造函数，生成一棵空的二叉树

public LinkBiTree() {

head = null;

}

// 判断是否是空二叉树

public boolean isEmpty() {

return head == null;

}

// 获取根结点

public TreeNode Root() {

return head;

}

// 获取结点的左孩子结点

public TreeNode getLchild(TreeNode p) {

return p.getLchild();

}

// 获取结点的右孩子结点

public TreeNode getRchild(TreeNode p) {

return p.getRchild();

}

// 创建二叉树

public void create(E val, TreeNode l, TreeNode r) {

TreeNode p = new TreeNode(val, l, r);

head = p;

}

// 将结点p的左子树插入值为val的新结点，

// 原来的左子树成为新结点的左子树

public void insertL(E val, TreeNode p) {

TreeNode name = new TreeNode(val);

TreeNode item = p.getLchild();

p.setLchild(name);

name.setLchild(item);

}

// 将结点p的右子树插入值为val的新结点，

// 原来的右子树成为新结点的右子树

public void insertR(E val, TreeNode p) {

TreeNode name = new TreeNode(val);

TreeNode item = p.getRchild();

p.setRchild(name);

name.setRchild(item);

}

// 若p非空，删除p的左子树

public TreeNode deleteL(TreeNode p) {

if (p == null)

return null;

TreeNode simulation = p.getLchild();

p.setLchild(null);

return simulation;

}

// 若p非空，删除p的右子树

public TreeNode deleteR(TreeNode p) {

if (p == null)

return null;

TreeNode simulation = p.getRchild();

p.setRchild(null);

return simulation;

}

// 编写算法,在二叉树中查找值为value的结点

public TreeNode search(TreeNode root, E value) {

Queue> q = new LinkedList>();

q.add(root);

while (!q.isEmpty()) {

TreeNode simulation = q.poll();

if (simulation.getLchild() != null)

q.add(simulation.getLchild());

if (simulation.getRchild() != null)

q.add(simulation.getRchild());

if (simulation.getData().equals(value))

return simulation;

}

return null;

}

// 判断是否是叶子结点

public boolean isLeaf(TreeNode p) {

Queue> q = new LinkedList>();

q.add(head);

while (!q.isEmpty()) {

TreeNode simulation = q.poll();

if (simulation.getLchild() != null)

q.add(simulation.getLchild());

if (simulation.getRchild() != null)

q.add(simulation.getRchild());

if (simulation.getData().equals(p.getData()) && simulation.getLchild() == null

&& simulation.getRchild() == null)

return true;

}

return false;

}

// 中序遍历

public void inorder(TreeNode p) {

if (p != null) {

inorder(p.getLchild());

System.out.print(p.getData() + " ");

inorder(p.getRchild());

}

return;

}

// 先序遍历

public void preorder(TreeNode p) {

if (p != null) {

System.out.print(p.getData() + " ");

preorder(p.getLchild());

preorder(p.getRchild());

}

return;

}

// 后序列遍历

public void postorder(TreeNode p) {

if (p != null) {

postorder(p.getLchild());

postorder(p.getRchild());

System.out.print(p.getData() + " ");

}

return;

}

// 层次遍历

public void levelOrder(TreeNode p) {

if (p == null)

return;

Queue> q = new LinkedList>();

q.add(head);

while (!q.isEmpty()) {

TreeNode simulation = q.poll();

System.out.print(simulation.getData() + " ");

if (simulation.getLchild() != null)

q.add(simulation.getLchild());

if (simulation.getRchild() != null)

q.add(simulation.getRchild());

}

}

// 遍历二叉树

public void traverse(TreeNode root, int i) {

switch (i) {

case 1:

preorder(root);

break;

case 2:

inorder(root);

break;

case 3:

postorder(root);

break;

case 4:

levelOrder(root);

break;

}

}

}

(4)二叉树测试类

import jsj.hhtc.ds.tree.LinkBiTree;

import jsj.hhtc.ds.tree.TreeNode;

public class TestLinkBiTree {

public static void main(String[] args) {

//构造如图6.5(b)所示二叉树

//以A为根结点的二叉树

LinkBiTree bt = new LinkBiTree('A');

TreeNode root = bt.getHead();

//插入A的左结点B

bt.insertL('B', root);

TreeNode b = root.getLchild();

//插入B的左结点D

bt.insertL('D', b);

TreeNode d = b.getLchild();

//插入B的右结点G

bt.insertR('G', d);

//构造A的右子树

bt.insertR('C', root);

TreeNode c = root.getRchild();

bt.insertL('E', c);

bt.insertR('F', c);

System.out.print("\n先序遍历：");

bt.preorder(root);

System.out.print("\n中序遍历：");

bt.inorder(root);

System.out.print("\n后序遍历：");

bt.postorder(root);

System.out.print("\n层序遍历：");

bt.levelOrder(root);

}

}

第二个代码如下：

(1)二叉树的定义及方法实现

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

import java.util.Stack;

/**

* @author Cherish

* 二叉树的链式存储结构

* @param

*/

public class BinaryTree {

private TreeNode root; //根节点

private List nodeList = null; //二叉树节点的链式结构

public BinaryTree(){

}

public BinaryTree(TreeNode root){

this.root = root;

}

//把一个数组转化为一颗完全二叉树

public TreeNode buildTree(E[] array){

nodeList = new LinkedList();

//将数组中的元素依次转换为TreeNode节点，存放于链表中

for(int i=0; i< array.length; i++){

nodeList.add(new TreeNode(array[i]));

}

//对前(array.length / 2 - 1)个父节点，按照父节点与孩子节点的数字关系建立完全二叉树

//对完全二叉树，按从上到下，从左到右的顺序依次编号0,1,2,3....N,则i>0的节点，其左孩子为(2*i+1)，

//其右孩子为(2*i+2)

for(int j=0; j < (array.length/2-1);j++){

//左孩子

nodeList.get(j).setLchild(nodeList.get(j*2+1));

//右孩子

nodeList.get(j).setRchild(nodeList.get(j*2+2));

}

//最后一个父节点：因为最后一个父节点可能没有右孩子，所以单独处理

int index = array.length/2 -1;

//左孩子

nodeList.get(index).setLchild(nodeList.get(index*2+1));

//右孩子：如果数组的长度为奇数才有右孩子

if(array.length % 2 == 1){

nodeList.get(index).setRchild(nodeList.get(index*2+2));

}

root=nodeList.get(0); //设置根节点

return root;

}

//得到树的高度

public int height(TreeNode node){

if(node == null){

return 0;

}else{

int i = height(node.getLchild());

int j = height(node.getRchild());

return (i

}

}

//得到节点的个数

public int size(TreeNode node){

if(node == null){

return 0;

}else{

return 1+ size(node.getLchild())+size(node.getRchild());

}

}

//递归实现先序遍历 NLR

public void preOrder(TreeNode node){

if(node != null){

System.out.print(node.getData() + " ");

preOrder(node.getLchild());

preOrder(node.getRchild());

}

}

//非递归实现先序遍历 NLR

public void nonRecPreOrder(TreeNode node){

Stack> nodeStack = new Stack>();

TreeNode nodeTemp = node; //nodeTemp作为遍历指针

while(nodeTemp != null || !nodeStack.isEmpty()){ //当nodeTemp非空或栈非空时循环

if(nodeTemp != null){ //根指针非空，遍历左子树

nodeStack.push(nodeTemp); //根指针进栈

System.out.print(nodeStack.peek().getData() + " "); //根指针退栈，访问根节点

nodeTemp = nodeTemp.getLchild(); //每遇到非空二叉树先向左走

}else{ //再向右子树走

nodeTemp = nodeStack.pop();

nodeTemp = nodeTemp.getRchild();

}

}

}

//递归实现中序遍历 LNR

public void inOrder(TreeNode node){

if(node != null){

inOrder(node.getLchild());

System.out.print(node.getData() + " ");

inOrder(node.getRchild());

}

}

//非递归实现中序遍历 LNR

public void nonRecInOrder(TreeNode node){

Stack> nodeStack = new Stack>();

TreeNode nodeTemp = node; //nodeTemp作为遍历指针

while(nodeTemp != null || !nodeStack.isEmpty()){ //当nodeTemp非空或栈非空时循环

if(nodeTemp != null){ //根指针非空，遍历左子树

nodeStack.push(nodeTemp); //根指针进栈

nodeTemp = nodeTemp.getLchild(); //每遇到非空二叉树先向左走

}else{

nodeTemp = nodeStack.pop(); //根指针退栈，访问根节点

System.out.print(nodeTemp.getData() +" ");

nodeTemp = nodeTemp.getRchild(); //再向右子树走

}

}

}

//递归实现后序遍历 LNR

public void postOrder(TreeNode node){

if(node != null){

postOrder(node.getLchild());

postOrder(node.getRchild());

System.out.print(node.getData() + " ");

}

}

//非递归实现后序遍历 LNR

public void nonRecPostOrder(TreeNode node){

Stack> nodeStack = new Stack>();

TreeNode nodeTemp = node; //nodeTemp作为遍历指针

TreeNode preNode = null; //表示最近一次访问的节点

while(nodeTemp != null || !nodeStack.isEmpty()){ //当nodeTemp非空或栈非空时循环

while(nodeTemp != null){ //一直向左走，遍历左子树

nodeStack.push(nodeTemp);

nodeTemp = nodeTemp.getLchild();

}

nodeTemp = nodeStack.peek();

if(nodeTemp.getRchild()==null || nodeTemp.getRchild() == preNode){ //右子树为空或右子树已被访问时，该节点出栈

nodeTemp = nodeStack.pop();

System.out.print(nodeTemp.getData()+" ");

preNode = nodeTemp; //将该节点赋值给最近一个访问节点

nodeTemp = null; //此处很重要，将刚出栈节点设置为空，对应于while循环的条件之一，否则陷入死循环

}else{

nodeTemp = nodeTemp.getRchild(); //遍历右子树

}

}

}

//层次遍历

public void levelOrder(TreeNode root){

Queue> nodeQueue = new LinkedList>();

TreeNode node = null;

nodeQueue.add(root); //将根节点入队

while(!nodeQueue.isEmpty()){ //队列不空循环

node = nodeQueue.peek();

System.out.print(node.getData()+" ");

nodeQueue.poll(); //队头元素出队

if(node.getLchild() != null){ //左子树不空，则左子树入队列

nodeQueue.add(node.getLchild());

}

if(node.getRchild() != null){ //右子树不空，则右子树入队列

nodeQueue.add(node.getRchild());

}

}

}

public static void main(String args[]){

//将一个数组转化为一颗完全二叉树

Object[] array = {1,2,3};

BinaryTree bt = new BinaryTree();

TreeNode root = bt.buildTree(array);

System.out.print("树的高度：");

System.out.println(bt.height(root));

System.out.print("节点的个数：");

System.out.println(bt.size(root));

System.out.println("先序遍历：");

bt.preOrder(root);

System.out.println("\n"+"非递归先序遍历：");

bt.nonRecPreOrder(root);

System.out.println();

System.out.println("中序遍历：");

bt.inOrder(root);

System.out.println("\n"+"非递归中序遍历：");

bt.nonRecInOrder(root);

System.out.println();

System.out.println("后序遍历：");

bt.postOrder(root);

System.out.println("\n"+"非递归后序遍历：");

bt.nonRecPostOrder(root);

System.out.println();

System.out.println("层次遍历：");

bt.levelOrder(root);

//手工构建一颗二叉树

TreeNode nodeA = new TreeNode("A");

TreeNode nodeB = new TreeNode("B");

TreeNode nodeC = new TreeNode("C");

TreeNode nodeD = new TreeNode("D");

TreeNode nodeE = new TreeNode("E");

TreeNode nodeF = new TreeNode("F");

TreeNode nodeG = new TreeNode("G");

TreeNode nodeH = new TreeNode("H");

TreeNode nodeI = new TreeNode("I");

nodeA.setLchild(nodeB);

nodeA.setRchild(nodeD);

nodeB.setRchild(nodeC);

nodeD.setLchild(nodeE);

nodeD.setRchild(nodeF);

nodeF.setLchild(nodeG);

nodeF.setRchild(nodeI);

nodeG.setRchild(nodeH);

System.out.println("\n\n"+"*****************");

System.out.print("树的高度：");

System.out.println(bt.height(nodeA));

System.out.print("节点的个数：");

System.out.println(bt.size(nodeA));

System.out.println("先序遍历：");

bt.preOrder(nodeA);

System.out.println();

System.out.println("中序遍历：");

bt.inOrder(nodeA);

System.out.println();

System.out.println("后序遍历：");

bt.postOrder(nodeA);

System.out.println();

System.out.println("层次遍历：");

bt.levelOrder(nodeA);

}

}(2)二叉树结点

public class TreeNode {

private E data; //数据域

private TreeNode lchild; //左孩子

private TreeNode rchild; //右孩子

TreeNode(){}

TreeNode(E e){

this.data = e;

}

TreeNode(E data,TreeNode lchild, TreeNode rchild){

this.data = data;

this.lchild = lchild;

this.rchild = rchild;

}

public void setData(E data){

this.data = data;

}

public E getData(){

return this.data;

}

public void setLchild(TreeNode lchild){

this.lchild = lchild;

}

public TreeNode getLchild(){

return this.lchild;

}

public void setRchild(TreeNode rchild){

this.rchild = rchild;

}

public TreeNode getRchild(){

return this.rchild;

}

}