「java树实现」java如何实现树结构

博主:adminadmin 2022-11-23 17:15:08 48

今天给各位分享java树实现的知识,其中也会对java如何实现树结构进行解释,如果能碰巧解决你现在面临的问题,别忘了关注本站,现在开始吧!

本文目录一览:

如何用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实现与几种遍历

二叉树的定义

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

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

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

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

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

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

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

具体实现看下图:

用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实现树形结构?

[java] view plain copy

package com.tree.test;

import java.sql.Connection;

import java.sql.DriverManager;

import java.sql.PreparedStatement;

import java.sql.ResultSet;

import java.sql.SQLException;

import java.sql.Statement;

public class Test {

public static void main(String[] args){

showTree();

}

public static void showTree(){

Connection conn=null;

ResultSet  rs = null;

Statement stmt=null;

try {

Class.forName("com.mysql.jdbc.Driver");

conn=DriverManager.getConnection("jdbc:mysql://localhost/tree?user=rootpassword=root");

/*stmt=conn.createStatement();

rs=stmt.executeQuery("select * from country where pid=0");

while(rs.next()){

System.out.println(rs.getString("actile"));*/

tree(conn,0,0);

// }

} catch (Exception e) {

// TODO Auto-generated catch block

e.printStackTrace();

}finally {

try {

if(rs != null) {

rs.close();

rs = null;

}

if(stmt != null) {

stmt.close();

stmt = null;

}

if(conn != null) {

conn.close();

conn = null;

}

} catch (SQLException e) {

e.printStackTrace();

}

}

}

public static void tree(Connection conn,int id,int level){

Statement stmt = null;

ResultSet rs = null;

try {

stmt = conn.createStatement();

String sql = "select * from country where pid = " + id;

rs = stmt.executeQuery(sql);

while(rs.next()) {

StringBuffer strPre = new StringBuffer("");

for(int i=0; ilevel; i++) {

strPre.append("    ");

}

System.out.println(strPre + rs.getString("actile"));

if(rs.getInt("is_leaf") != 0)

tree(conn, rs.getInt("id"), level + 1);

}

} catch (SQLException e) {

e.printStackTrace();

} finally {

try {

if(rs != null) {

rs.close();

rs = null;

}

if(stmt != null) {

stmt.close();

stmt = null;

}

} catch (SQLException e) {

e.printStackTrace();

}

}

}

数据库

[sql] view plain copy

create database tree;

use tree;

create table country

(

id int primary key auto_increment,

pid int,

actile varchar(40),

is_leaf int

);

insert into country values(1,0, '中国',1);

insert into country values(2,1,'北京',0);

insert into country values(3,0,'美国',1);

insert into country values(4,3,'纽约',0);

insert into country values(5,1,'浙江',1);

insert into country values(6,5,'杭州',1);

insert into country values(7,6,'滨江',0);

java实现tree树性能如何

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

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

关于java树实现和java如何实现树结构的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。

The End

发布于:2022-11-23,除非注明,否则均为首码项目网原创文章,转载请注明出处。