正文
avl树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);
}
}
相关问答
Q1: 简单的JAVA多叉树问题实现
TreeNode.java
/*
* Copyright Walker Studio
* All Rights Reserved.
*
* 文件名称avl树java代码实现： TreeNode.java
* 摘 要：
* 作 者： Walker
* 创建时间： 2013-03-19
*/
package com.walker.commons.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.commons.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.commons.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"));
}
/**
* 生成一颗多叉树avl树java代码实现，根节点为root
*
* @param treeNodes 生成多叉树avl树java代码实现的节点集合
* @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()))
{
//找到对应avl树java代码实现的父亲
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()));
}
}
Q2: 二叉平衡树 avl树
哇，大学时代的习题来了，好久没做过这东东了
不知道生锈没有。
二叉平衡树是指左右两子树的深度之差不超过一层的二叉树；
先定义数据结构:
public Class TreeNode{
int value=0;//值
public TreeNode left;//左子树
public TreeNode right;//右子树
}
树的存储： 以一维数组进行存储
[1][2][3][4][5][6][7][8][9][10][11][12][13][14]
树的插入: 直接插入追加到数组后面，这样就能保证是二叉平衡树
[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15]
为什么？ 有什么规律可循？
如何生成平衡树？
A： 1节点为第根节点， 2，3节点分别为1节点的左右子树
B： 2节点时, 4，5节点分别为 2节点的左右子树
C： 3节点时, 6，7节点分别为 3节点的左右子树
D： 4节点时, 8，9节点分别为 4节点的左右子树
E: 5节点时，10，11节点分别为5节点的左右子树
... 以此类推，得到公式： （很重要!!!!）
公式： 某个节点位置值为 N ，则
它的左子节点位置 = N*2；
它的右子节点位置 = N*2+1;
以此公式可生成上述二叉树便是二叉平衡树；
Step1:先生成该数组
TreeNode[] nodes=new TreeNode[];
nodes[0]=null;// 第0个节点不要，因为0不满足公式，直接从1开始
for(int i=1;i nodes.length;i++){
nodes[i]=new TreeNode();
nodes[i].value=i;
}
Step2: 通过该数组构建成二叉平衡树：
//从1开始遍历，因为0比较特殊不满足公式。所以让1号元素做为树根，0号空缺
for(int i=1;inodes.length;i++){
if(i*2nodes.length nodes[i*2]!=null){
nodes[i].left= nodes[i*2];
}
if((i*2+1)nodes.length nodes[i*2+1]!=null){
nodes[i].right=nodes[i*2+1]
}
}
构建完成！
插入操作：
插入时，直接在 nodes[]数组的末尾追加即可！很方便
排序我的二叉树：
呵呵，不用说，直接用冒泡我快排对nodes[]数组排序就行了
其它删除，查找，都类似。
是不是很方便呢？
记得给会哦，
也许会有其它的解决方案，希望我能抛砖引玉， 哈哈
关于avl树java代码实现和java 树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
