java树的实现代码 java树算法
如何用java实现二叉树
import java.util.List;
创新互联主要从事网站设计、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务古城,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575
import java.util.LinkedList;
public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static ListNode nodeList = null;
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]));
}
// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
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);
}
}
// 前序遍历
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
// 中序遍历
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
// 后序遍历
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) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
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);
}
}
输出结果：
前序遍历：
1 2 4 8 9 5 3 6 7
中序遍历：
8 4 9 2 5 1 6 3 7
后序遍历：
8 9 4 5 2 6 7 3 1
如何用Java实现树形结构啊？
package tree;
import java.util.LinkedList;
import java.util.List;
/**
* 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历
*
* 参考资料0:数据结构(C语言版)严蔚敏
*
* 参考资料1：
*
* 参考资料2：
*
* @author ocaicai@yeah点虐 @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点虐 @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多叉树问题实现
TreeNode.java
/*
* Copyright Walker Studio
* All Rights Reserved.
*
* 文件名称： TreeNode.java
* 摘 要：
* 作 者： Walker
* 创建时间： 2013-03-19
*/
package com.walker点抗 mons.data.model;
/**
* 树节点
*
* @author Walker
* @version 1.0.0.0
*/
public class TreeNode
{
/** 节点Id*/
private String nodeId;
/** 父节点Id*/
private String parentId;
/** 文本内容*/
private String text;
/**
* 构造函数
*
* @param nodeId 节点Id
*/
public TreeNode(String nodeId)
{
this.nodeId = nodeId;
}
/**
* 构造函数
*
* @param nodeId 节点Id
* @param parentId 父节点Id
*/
public TreeNode(String nodeId, String parentId)
{
this.nodeId = nodeId;
this.parentId = parentId;
}
public String getNodeId() {
return nodeId;
}
public void setNodeId(String nodeId) {
this.nodeId = nodeId;
}
public String getParentId() {
return parentId;
}
public void setParentId(String parentId) {
this.parentId = parentId;
}
public String getText() {
return text;
}
public void setText(String text) {
this.text = text;
}
}
ManyTreeNode.java
/*
* Copyright Walker Studio
* All Rights Reserved.
*
* 文件名称： ManyTreeNode.java
* 摘 要：
* 作 者： Walker
* 创建时间： 2013-03-19
*/
package com.walker点抗 mons.data.model;
import java.util.ArrayList;
import java.util.List;
/**
* 多叉树节点
*
* @author Walker
* @verion 1.0.0.0
*/
public class ManyTreeNode
{
/** 树节点*/
private TreeNode data;
/** 子树集合*/
private ListManyTreeNode childList;
/**
* 构造函数
*
* @param data 树节点
*/
public ManyTreeNode(TreeNode data)
{
this.data = data;
this.childList = new ArrayListManyTreeNode();
}
/**
* 构造函数
*
* @param data 树节点
* @param childList 子树集合
*/
public ManyTreeNode(TreeNode data, ListManyTreeNode childList)
{
this.data = data;
this.childList = childList;
}
public TreeNode getData() {
return data;
}
public void setData(TreeNode data) {
this.data = data;
}
public ListManyTreeNode getChildList() {
return childList;
}
public void setChildList(ListManyTreeNode childList) {
this.childList = childList;
}
}
ManyNodeTree.java
/*
* Copyright Walker Studio
* All Rights Reserved.
*
* 文件名称： ManyNodeTree.java
* 摘 要：
* 作 者： Walker
* 创建时间： 2013-03-19
*/
package com.walker点抗 mons.data.model;
import java.util.ArrayList;
import java.util.List;
/**
* 多叉树生成、遍历工具
*
* @author Walker
* @version 1.0.0.0
*/
public class ManyNodeTree
{
/** 树根*/
private ManyTreeNode root;
/**
* 构造函数
*/
public ManyNodeTree()
{
root = new ManyTreeNode(new TreeNode("root"));
}
/**
* 生成一颗多叉树，根节点为root
*
* @param treeNodes 生成多叉树的节点集合
* @return ManyNodeTree
*/
public ManyNodeTree createTree(ListTreeNode treeNodes)
{
if(treeNodes == null || treeNodes.size() 0)
return null;
ManyNodeTree manyNodeTree = new ManyNodeTree();
//将所有节点添加到多叉树中
for(TreeNode treeNode : treeNodes)
{
if(treeNode.getParentId().equals("root"))
{
//向根添加一个节点
manyNodeTree.getRoot().getChildList().add(new ManyTreeNode(treeNode));
}
else
{
addChild(manyNodeTree.getRoot(), treeNode);
}
}
return manyNodeTree;
}
/**
* 向指定多叉树节点添加子节点
*
* @param manyTreeNode 多叉树节点
* @param child 节点
*/
public void addChild(ManyTreeNode manyTreeNode, TreeNode child)
{
for(ManyTreeNode item : manyTreeNode.getChildList())
{
if(item.getData().getNodeId().equals(child.getParentId()))
{
//找到对应的父亲
item.getChildList().add(new ManyTreeNode(child));
break;
}
else
{
if(item.getChildList() != null item.getChildList().size() 0)
{
addChild(item, child);
}
}
}
}
/**
* 遍历多叉树
*
* @param manyTreeNode 多叉树节点
* @return
*/
public String iteratorTree(ManyTreeNode manyTreeNode)
{
StringBuilder buffer = new StringBuilder();
buffer.append("\n");
if(manyTreeNode != null)
{
for (ManyTreeNode index : manyTreeNode.getChildList())
{
buffer.append(index.getData().getNodeId()+ ",");
if (index.getChildList() != null index.getChildList().size() 0 )
{
buffer.append(iteratorTree(index));
}
}
}
buffer.append("\n");
return buffer.toString();
}
public ManyTreeNode getRoot() {
return root;
}
public void setRoot(ManyTreeNode root) {
this.root = root;
}
public static void main(String[] args)
{
ListTreeNode treeNodes = new ArrayListTreeNode();
treeNodes.add(new TreeNode("系统权限管理", "root"));
treeNodes.add(new TreeNode("用户管理", "系统权限管理"));
treeNodes.add(new TreeNode("角色管理", "系统权限管理"));
treeNodes.add(new TreeNode("组管理", "系统权限管理"));
treeNodes.add(new TreeNode("用户菜单管理", "系统权限管理"));
treeNodes.add(new TreeNode("角色菜单管理", "系统权限管理"));
treeNodes.add(new TreeNode("用户权限管理", "系统权限管理"));
treeNodes.add(new TreeNode("站内信", "root"));
treeNodes.add(new TreeNode("写信", "站内信"));
treeNodes.add(new TreeNode("收信", "站内信"));
treeNodes.add(new TreeNode("草稿", "站内信"));
ManyNodeTree tree = new ManyNodeTree();
System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()));
}
}
说明生活中遇到的二叉树，用java实现二叉树. (求源码，要求简练、易懂。非常满意会额外加分)
import java.util.ArrayList;
// 树的一个节点
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父节点，根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 给出宽度优先遍历的值数组，构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点，带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );
// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲
for ( int i = 2; i values.length; i++ ){
// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex+1 currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按宽度优先遍历，打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 为了避免叶子节点也会打印null
//打印 parent 同层的节点的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i parent._parent._childList.size() ){// parent 的父亲还有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}
// 递归调用，打印所有节点
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按宽度优先遍历，打印出parent子树所有的节点
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 将给定的值做为 parent 的孩子，构建节点
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}
public static void main(String[] args) {
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
}
}
看一下吧！这是在网上找的一个例子！看对你有没有帮助！
当前题目：java树的实现代码 java树算法
标题路径：http://azwzsj.com/article/ddjcipg.html
