如何用java實現(xiàn)二叉樹

import java.util.List;

創(chuàng)新互聯(lián)主要從事網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)古城,十年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):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;

}

}

// 創(chuàng)建二叉樹

public void createBintree() {

nodeList = new LinkedListNode();

// 將數(shù)組的值轉(zhuǎn)換為node

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

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

}

// 對除最后一個父節(jié)點按照父節(jié)點和孩子節(jié)點的數(shù)字關(guān)系建立二叉樹

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);

}

// 最后一個父節(jié)點

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數(shù)，建立右孩子

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);

}

}

輸出結(jié)果：

前序遍歷：

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實現(xiàn)樹形結(jié)構(gòu)啊？

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* 功能：把一個數(shù)組的值存入二叉樹中，然后進行3種方式的遍歷

*

* 參考資料0:數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏

*

* 參考資料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;

/**

* 內(nèi)部類：節(jié)點

*

* @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();

// 將一個數(shù)組的值依次轉(zhuǎn)換為Node節(jié)點

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

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

}

// 對前l(fā)astParentIndex-1個父節(jié)點按照父節(jié)點與孩子節(jié)點的數(shù)字關(guān)系建立二叉樹

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);

}

// 最后一個父節(jié)點:因為最后一個父節(jié)點可能沒有右孩子，所以單獨拿出來處理

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList

.get(lastParentIndex * 2 + 1);

// 右孩子,如果數(shù)組的長度為奇數(shù)才建立右孩子

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

nodeList.get(lastParentIndex).rightChild = nodeList

.get(lastParentIndex * 2 + 2);

}

}

/**

* 先序遍歷

*

* 這三種不同的遍歷結(jié)構(gòu)都是一樣的，只是先后順序不一樣而已

*

* @param node

* 遍歷的節(jié)點

*/

public static void preOrderTraverse(Node node) {

if (node == null)

return;

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

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

/**

* 中序遍歷

*

* 這三種不同的遍歷結(jié)構(gòu)都是一樣的，只是先后順序不一樣而已

*

* @param node

* 遍歷的節(jié)點

*/

public static void inOrderTraverse(Node node) {

if (node == null)

return;

inOrderTraverse(node.leftChild);

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

inOrderTraverse(node.rightChild);

}

/**

* 后序遍歷

*

* 這三種不同的遍歷結(jié)構(gòu)都是一樣的，只是先后順序不一樣而已

*

* @param node

* 遍歷的節(jié)點

*/

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個索引處的值即為根節(jié)點

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多叉樹問題實現(xiàn)

TreeNode.java

/*

*?Copyright?Walker?Studio

*?All?Rights?Reserved.

*?

*?文件名稱：?TreeNode.java

*?摘?要：

*?作?者：?Walker

*?創(chuàng)建時間：?2013-03-19

*/

package?com.walker點抗 mons.data.model;

/**

*?樹節(jié)點

*?

*?@author?Walker

*?@version?1.0.0.0

*/

public?class?TreeNode?

{

/**?節(jié)點Id*/

private?String?nodeId;

/**?父節(jié)點Id*/

private?String?parentId;

/**?文本內(nèi)容*/

private?String?text;

/**

?*?構(gòu)造函數(shù)

?*?

?*?@param?nodeId?節(jié)點Id

?*/

public?TreeNode(String?nodeId)

{

this.nodeId?=?nodeId;

}

/**

?*?構(gòu)造函數(shù)

?*?

?*?@param?nodeId?節(jié)點Id

?*?@param?parentId?父節(jié)點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

*?創(chuàng)建時間：?2013-03-19

*/

package?com.walker點抗 mons.data.model;

import?java.util.ArrayList;

import?java.util.List;

/**

*?多叉樹節(jié)點

*

*?@author?Walker

*?@verion?1.0.0.0

*/

public?class?ManyTreeNode?

{

/**?樹節(jié)點*/

private?TreeNode?data;

/**?子樹集合*/

private?ListManyTreeNode?childList;

/**

?*?構(gòu)造函數(shù)

?*?

?*?@param?data?樹節(jié)點

?*/

public?ManyTreeNode(TreeNode?data)

{

this.data?=?data;

this.childList?=?new?ArrayListManyTreeNode();

}

/**

?*?構(gòu)造函數(shù)

?*?

?*?@param?data?樹節(jié)點

?*?@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

*?創(chuàng)建時間：?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;

/**

?*?構(gòu)造函數(shù)

?*/

public?ManyNodeTree()

{

root?=?new?ManyTreeNode(new?TreeNode("root"));

}

/**

?*?生成一顆多叉樹，根節(jié)點為root

?*?

?*?@param?treeNodes?生成多叉樹的節(jié)點集合

?*?@return?ManyNodeTree

?*/

public?ManyNodeTree?createTree(ListTreeNode?treeNodes)

{

if(treeNodes?==?null?||?treeNodes.size()??0)

return?null;

ManyNodeTree?manyNodeTree?=??new?ManyNodeTree();

//將所有節(jié)點添加到多叉樹中

for(TreeNode?treeNode?:?treeNodes)

{

if(treeNode.getParentId().equals("root"))

{

//向根添加一個節(jié)點

manyNodeTree.getRoot().getChildList().add(new?ManyTreeNode(treeNode));

}

else

{

addChild(manyNodeTree.getRoot(),?treeNode);

}

}

return?manyNodeTree;

}

/**

?*?向指定多叉樹節(jié)點添加子節(jié)點

?*?

?*?@param?manyTreeNode?多叉樹節(jié)點

?*?@param?child?節(jié)點

?*/

public?void?addChild(ManyTreeNode?manyTreeNode,?TreeNode?child)

{

for(ManyTreeNode?item?:?manyTreeNode.getChildList())

{

if(item.getData().getNodeId().equals(child.getParentId()))

{

//找到對應(yīng)的父親

item.getChildList().add(new?ManyTreeNode(child));

break;

}

else

{

if(item.getChildList()?!=?null??item.getChildList().size()??0)

{

addChild(item,?child);

}

}

}

}

/**

?*?遍歷多叉樹?

?*?

?*?@param?manyTreeNode?多叉樹節(jié)點

?*?@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("系統(tǒng)權(quán)限管理",?"root"));

treeNodes.add(new?TreeNode("用戶管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("角色管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("組管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("用戶菜單管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("角色菜單管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("用戶權(quán)限管理",?"系統(tǒng)權(quán)限管理"));

treeNodes.add(new?TreeNode("站內(nèi)信",?"root"));

treeNodes.add(new?TreeNode("寫信",?"站內(nèi)信"));

treeNodes.add(new?TreeNode("收信",?"站內(nèi)信"));

treeNodes.add(new?TreeNode("草稿",?"站內(nèi)信"));

ManyNodeTree?tree?=?new?ManyNodeTree();

System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()));

}

}

說明生活中遇到的二叉樹，用java實現(xiàn)二叉樹. (求源碼，要求簡練、易懂。非常滿意會額外加分)

import java.util.ArrayList;

// 樹的一個節(jié)點

class TreeNode {

Object _value = null; // 他的值

TreeNode _parent = null; // 他的父節(jié)點，根節(jié)點沒有PARENT

ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點

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 {

// 給出寬度優(yōu)先遍歷的值數(shù)組，構(gòu)建出一棵多叉樹

// null 值表示一個層次的結(jié)束

// "|" 表示一個層次中一個父親節(jié)點的孩子輸入結(jié)束

// 如：給定下面的值數(shù)組：

// { "root", null, "left", "right", null }

// 則構(gòu)建出一個根節(jié)點，帶有兩個孩子("left","right")的樹

public Tree( Object[] values ){

// 創(chuàng)建根

_root = new TreeNode( values[0], null );

// 創(chuàng)建下面的子節(jié)點

TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點的父親

//TreeNode nextParent = null;

int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子

//TreeNode lastNode = null; // 最后一個創(chuàng)建出來的TreeNode，用于找到他的父親

for ( int i = 2; i values.length; i++ ){

// 如果null ,表示下一個節(jié)點的父親是當(dāng)前節(jié)點的父親的第一個孩子節(jié)點

if ( values[i] == null ){

currentParent = (TreeNode)currentParent._childList.get(0);

currentChildIndex = 0;

continue;

}

// 表示一個父節(jié)點的所有孩子輸入完畢

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;

}

/**

// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點

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);// 為了避免葉子節(jié)點也會打印null

//打印 parent 同層的節(jié)點的孩子

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++;

}

}

// 遞歸調(diào)用，打印所有節(jié)點

for ( int i = 0; i parent._childList.size(); i++ ){

TreeNode child = (TreeNode)parent._childList.get(i);

printSteps( child, currentDepth+1 );

}

}

// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點

public void printSteps(){

System.out.println(""+_root);

System.out.println(""+null);

printSteps(_root, 1 );

}**/

// 將給定的值做為 parent 的孩子，構(gòu)建節(jié)點

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) );

}

}

看一下吧！這是在網(wǎng)上找的一個例子！看對你有沒有幫助！

名稱欄目：java樹的實現(xiàn)代碼 java樹算法
轉(zhuǎn)載來于：http://www.rwnh.cn/article36/ddjcipg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、搜索引擎優(yōu)化、云服務(wù)器、小程序開發(fā)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)