您的位置:

树的java实现,java生成树

本文目录一览:

二叉树的java实现与几种遍历

二叉树的定义

二叉树(binary tree)是结点的有限集合,这个集合或者空,或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.

从定义可以看出,二叉树包括:1.空树 2.只有一个根节点 3.只有左子树   4.只有右子树  5.左右子树都存在    有且仅有这5种表现形式

二叉树的遍历分为三种:前序遍历 中序遍历 后序遍历

前序遍历:按照“根左右”,先遍历根节点,再遍历左子树 ,再遍历右子树

中序遍历:按照“左根右“,先遍历左子树,再遍历根节点,最后遍历右子树

后续遍历:按照“左右根”,先遍历左子树,再遍历右子树,最后遍历根节点

其中前,后,中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图:

如何用Java实现树形结构啊?

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* 功能:把一个数组的值存入二叉树中,然后进行3种方式的遍历

*

* 参考资料0:数据结构(C语言版)严蔚敏

*

* 参考资料1:

*

* 参考资料2:

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

public class BinTreeTraverse2 {

private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

private static ListNode nodeList = null;

/**

* 内部类:节点

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

public void createBinTree() {

nodeList = new LinkedListNode();

// 将一个数组的值依次转换为Node节点

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

nodeList.add(new Node(array[nodeIndex]));

}

// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树

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

// 左孩子

nodeList.get(parentIndex).leftChild = nodeList

.get(parentIndex * 2 + 1);

// 右孩子

nodeList.get(parentIndex).rightChild = nodeList

.get(parentIndex * 2 + 2);

}

// 最后一个父节点:因为最后一个父节点可能没有右孩子,所以单独拿出来处理

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList

.get(lastParentIndex * 2 + 1);

// 右孩子,如果数组的长度为奇数才建立右孩子

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

nodeList.get(lastParentIndex).rightChild = nodeList

.get(lastParentIndex * 2 + 2);

}

}

/**

* 先序遍历

*

* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void preOrderTraverse(Node node) {

if (node == null)

return;

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

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

/**

* 中序遍历

*

* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void inOrderTraverse(Node node) {

if (node == null)

return;

inOrderTraverse(node.leftChild);

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

inOrderTraverse(node.rightChild);

}

/**

* 后序遍历

*

* 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void postOrderTraverse(Node node) {

if (node == null)

return;

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

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

}

public static void main(String[] args) {

BinTreeTraverse2 binTree = new BinTreeTraverse2();

binTree.createBinTree();

// nodeList中第0个索引处的值即为根节点

Node root = nodeList.get(0);

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

preOrderTraverse(root);

System.out.println();

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

inOrderTraverse(root);

System.out.println();

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

postOrderTraverse(root);

}

}

用java实现二叉树

我有很多个(假设10万个)数据要保存起来,以后还需要从保存的这些数据中检索是否存在某

个数据,(我想说出二叉树的好处,该怎么说呢?那就是说别人的缺点),假如存在数组中,

那么,碰巧要找的数字位于99999那个地方,那查找的速度将很慢,因为要从第1个依次往

后取,取出来后进行比较。平衡二叉树(构建平衡二叉树需要先排序,我们这里就不作考虑

了)可以很好地解决这个问题,但二叉树的遍历(前序,中序,后序)效率要比数组低很多,

public class Node {

public int value;

public Node left;

public Node right;

public void store(intvalue)

right.value=value;

}

else

{

right.store(value);

}

}

}

public boolean find(intvalue)

{

System.out.println("happen" +this.value);

if(value ==this.value)

{

return true;

}

else if(valuethis.value)

{

if(right ==null)returnfalse;

return right.find(value);

}else

{

if(left ==null)returnfalse;

return left.find(value);

}

}

public void preList()

{

System.out.print(this.value+ ",");

if(left!=null)left.preList();

if(right!=null) right.preList();

}

public void middleList()

{

if(left!=null)left.preList();

System.out.print(this.value+ ",");

if(right!=null)right.preList();

}

public void afterList()

{

if(left!=null)left.preList();

if(right!=null)right.preList();

System.out.print(this.value+ ",");

}

public static voidmain(String [] args)

{

int [] data =new int[20];

for(inti=0;idata.length;i++)

{

data[i] = (int)(Math.random()*100)+ 1;

System.out.print(data[i] +",");

}

System.out.println();

Node root = new Node();

root.value = data[0];

for(inti=1;idata.length;i++)

{

root.store(data[i]);

}

root.find(data[19]);

root.preList();

System.out.println();

root.middleList();

System.out.println();

root.afterList();

}

}

java实现tree树性能如何

树与二叉树实现差不多,二叉树类变量里面有两个节点,通过配置一些参数让数据库性能达到最优。

用Java实现的数据树形封装。

java 如何实现树、图结构?

你如果要树形展示,在JSP上只能用树控件,类似dtree.js这种第三方JS包

如果是树体系,JAVA还是面向对象,只能用代码描述出一棵树,包括各个属性,能通过数据体现一个树的体系(子父编号关联),但无法直观的看出图形来