java 构建二叉树

首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,

创新互联公司服务项目包括茌平网站建设、茌平网站制作、茌平网页制作以及茌平网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，茌平网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到茌平省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

树是树形的, 似乎不太合适。

其实也可以用数组完成，而且效率更高.

关键是我觉得你这个输入本身就是一个二叉树啊，

String input = "ABCDE F G";

节点编号从0到8. 层次遍历的话:

对于节点i.

leftChild = input.charAt(2*i+1); //做子树

rightChild = input.charAt(2*i+2);//右子树

如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍历input,建立各个节点对象.

LinkedList tree = new LinkedList();

for(int i=0;i input.length;i++)

LinkedList.add(new Node(input.charAt(i)));

然后为各个节点设置左右子树:

for(int i=0;iinput.length;i++){

((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);

((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);

}

这样LinkedList 就存储了整个二叉树. 而第0个元素就是树根，思路大体是这样吧。

写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明

public class BinaryNode {

Object element;

BinaryNode left;

BinaryNode right;

}

import java.util.*;

public class Queue {

protected LinkedList list;

// Postcondition: this Queue object has been initialized.

public Queue() {

list = new LinkedList();

} // default constructor

// Postcondition: the number of elements in this Queue object has been

// returned.

public int size() {

return list.size();

} // method size

// Postcondition: true has been returned if this Queue object has no

// elements. Otherwise, false has been returned.

public boolean isEmpty() {

return list.isEmpty();

} // method isEmpty

// Postconditon: A copy of element has been inserted at the back of this

// Queue object. The averageTime (n) is constant and

// worstTime (n) is O (n).

public void enqueue(Object element) {

list.addLast(element);

} // method enqueue

// Precondition: this Queue object is not empty. Otherwise,

// NoSuchElementException will be thrown.

// Postcondition: The element that was at the front of this Queue object -

// just before this method was called -- has been removed

// from this Queue object and returned.

public Object dequeue() {

return list.removeFirst();

} // method dequeue

// Precondition: this Queue object is not empty. Otherwise,

// NoSuchElementException will be thrown.

// Postcondition: the element at index 0 in this Queue object has been

// returned.

public Object front() {

return list.getFirst();

} // method front

} // Queue class

import java.io.IOException;

public class BinaryTree {

BinaryNode root;

public BinaryTree() {

super();

// TODO 自动生成构造函数存根

root=this.createPre();

}

public BinaryNode createPre()

//按照先序遍历的输入方法，建立二叉树

{

BinaryNode t=null;

char ch;

try {

ch = (char)System.in.read();

if(ch==' ')

t=null;

else

{

t=new BinaryNode();

t.element=(Object)ch;

t.left=createPre();

t.right=createPre();

}

} catch (IOException e) {

// TODO 自动生成 catch 块

e.printStackTrace();

}

return t;

}

public void inOrder()

{

this.inOrder(root);

}

public void inOrder(BinaryNode t)

//中序遍历二叉树

{

if(t!=null)

{

inOrder(t.left);

System.out.print(t.element);

inOrder(t.right);

}

}

public void postOrder()

{

this.postOrder(root);

}

public void postOrder(BinaryNode t)

//后序遍历二叉树

{

if(t!=null)

{

postOrder(t.left);

System.out.print(t.element);

postOrder(t.right);

}

}

public void preOrder()

{

this.preOrder(root);

}

public void preOrder(BinaryNode t)

//前序遍历二叉树

{

if(t!=null)

{

System.out.print(t.element);

preOrder(t.left);

preOrder(t.right);

}

}

public void breadthFirst()

{

Queue treeQueue=new Queue();

BinaryNode p;

if(root!=null)

treeQueue.enqueue(root);

while(!treeQueue.isEmpty())

{

System.out.print(((BinaryNode)(treeQueue.front())).element);

p=(BinaryNode)treeQueue.dequeue();

if(p.left!=null)

treeQueue.enqueue(p.left);

if(p.right!=null)

treeQueue.enqueue(p.right);

}

}

}

public class BinaryTreeTest {

/**

* @param args

*/

public static void main(String[] args) {

// TODO 自动生成方法存根

BinaryTree tree = new BinaryTree();

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

tree.preOrder();

System.out.println();

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

tree.inOrder();

System.out.println();

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

tree.postOrder();

System.out.println();

System.out.println("层次遍历：");

tree.breadthFirst();

System.out.println();

}

}

java一个关于二叉树的简单编程题

定义一个结点类：

public class Node {

private int value;

private Node leftNode;

private Node rightNode;

public Node getRightNode() {

return rightNode;

}

public void setRightNode(Node rightNode) {

this.rightNode = rightNode;

}

public int getValue() {

return value;

}

public void setValue(int value) {

this.value = value;

}

public Node getLeftNode() {

return leftNode;

}

public void setLeftNode(Node leftNode) {

this.leftNode = leftNode;

}

}

初始化结点树：

public void initNodeTree()

{

int nodeNumber;

HashMapString, Integer map = new HashMapString, Integer();

Node nodeTree = new Node();

Scanner reader = new Scanner(System.in);

nodeNumber = reader.nextInt();

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

int value = reader.nextInt();

String str = reader.next();

map.put(str, value);

}

if (map.containsKey("#")) {

int value = map.get("#");

nodeTree.setValue(value);

setChildNode(map, value, nodeTree);

}

preTraversal(nodeTree);

}

private void setChildNode(HashMapString, Integer map, int nodeValue, Node parentNode) {

int value = 0;

if (map.containsKey("L" + nodeValue)) {

value = map.get("L" + nodeValue);

Node leftNode = new Node();

leftNode.setValue(value);

parentNode.setLeftNode(leftNode);

setChildNode(map, value, leftNode);

}

if (map.containsKey("R" + nodeValue)) {

value = map.get("R" + nodeValue);

Node rightNode = new Node();

rightNode.setValue(value);

parentNode.setRightNode(rightNode);

setChildNode(map, value, rightNode);

}

}

前序遍历该结点树：

public void preTraversal(Node nodeTree) {

if (nodeTree != null) {

System.out.print(nodeTree.getValue() + "\t");

preTraversal(nodeTree.getLeftNode());

preTraversal(nodeTree.getRightNode());

}

}

用JAVA写二叉树

/**

* [Tree2.java] Create on 2008-10-20 下午03:03:24

* Copyright (c) 2008 by iTrusChina.

*/

/**

* @author WangXuanmin

* @version 0.10

*/

public class Tree2Bef {

private StringBuffer bef=new StringBuffer();

//传入中序遍历和后序遍历,返回前序遍历字串

public String getBef(String mid, String beh) {

//若节点存在则向bef中添加该节点,继续查询该节点的左子树和右子树

if (root(mid, beh) != -1) {

int rootindex=root(mid, beh);

char root=mid.charAt(rootindex);

bef.append(root);

System.out.println(bef.toString());

String mleft, mright;

mleft = mid.substring(0,rootindex);

mright = mid.substring(rootindex+1);

getBef(mleft,beh);

getBef(mright,beh);

}

//所有节点查询完毕,返回前序遍历值

return bef.toString();

}

//从中序遍历中根据后序遍历查找节点索引值index

private int root(String mid, String beh) {

char[] midc = mid.toCharArray();

char[] behc = beh.toCharArray();

for (int i = behc.length-1; i -1; i--) {

for (int j = 0; j midc.length; j++) {

if (behc[i] == midc[j])

return j;

}

}

return -1;

}

public static void main(String[] args) {

Tree2Bef tree=new Tree2Bef();

String mid="84925163A7B";

String bef="894526AB731";

System.out.println(tree.getBef(mid,bef));

}

}

树结构如图:

1

|-------|

2 3

|---| |---|

4 5 6 7

|-| |-|

8 9 A B

java 由字符串构成的二叉树

java构造二叉树，可以通过链表来构造，如下代码：

public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点 int front;//层次遍历时队首 int rear;//层次遍历时队尾private Object data; //数据元数private BinTree left,right; //指向左,右孩子结点的链public BinTree(){}public BinTree(Object data){ //构造有值结点 this.data = data; left = right = null;}public BinTree(Object data,BinTree left,BinTree right){ //构造有值结点 this.data = data; this.left = left; this.right = right;}public String toString(){ return data.toString();}//前序遍历二叉树public static void preOrder(BinTree parent){ if(parent == null) return; System.out.print(parent.data+" "); preOrder(parent.left); preOrder(parent.right);}//中序遍历二叉树public void inOrder(BinTree parent){ if(parent == null) return; inOrder(parent.left); System.out.print(parent.data+" "); inOrder(parent.right);}//后序遍历二叉树public void postOrder(BinTree parent){ if(parent == null) return; postOrder(parent.left); postOrder(parent.right); System.out.print(parent.data+" ");}// 层次遍历二叉树 public void LayerOrder(BinTree parent){ elements[0]=parent; front=0;rear=1; while(frontrear) { try { if(elements[front].data!=null) { System.out.print(elements[front].data + " "); if(elements[front].left!=null) elements[rear++]=elements[front].left; if(elements[front].right!=null) elements[rear++]=elements[front].right; front++; } }catch(Exception e){break;} }}//返回树的叶节点个数public int leaves(){ if(this == null) return 0; if(left == nullright == null) return 1; return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());}//结果返回树的高度public int height(){ int heightOfTree; if(this == null) return -1; int leftHeight = (left == null ? 0 : left.height()); int rightHeight = (right == null ? 0 : right.height()); heightOfTree = leftHeightrightHeight?rightHeight:leftHeight; return 1 + heightOfTree;}//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层public int level(Object object){ int levelInTree; if(this == null) return -1; if(object == data) return 1;//规定根节点为第一层 int leftLevel = (left == null?-1:left.level(object)); int rightLevel = (right == null?-1:right.level(object)); if(leftLevel0rightLevel0) return -1; levelInTree = leftLevelrightLevel?rightLevel:leftLevel; return 1+levelInTree; }//将树中的每个节点的孩子对换位置public void reflect(){ if(this == null) return; if(left != null) left.reflect(); if(right != null) right.reflect(); BinTree temp = left; left = right; right = temp;}// 将树中的所有节点移走,并输出移走的节点public void defoliate(){ if(this == null) return; //若本节点是叶节点，则将其移走 if(left==nullright == null) { System.out.print(this + " "); data = null; return; } //移走左子树若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本节点，放在中间表示中跟移走... String innerNode += this + " "; data = null; //移走右子树若其存在 if(right!=null){ right.defoliate(); right = null; }} /*** @param args*/public static void main(String[] args) { // TODO Auto-generated method stub BinTree e = new BinTree("E"); BinTree g = new BinTree("G"); BinTree h = new BinTree("H"); BinTree i = new BinTree("I"); BinTree d = new BinTree("D",null,g); BinTree f = new BinTree("F",h,i); BinTree b = new BinTree("B",d,e); BinTree c = new BinTree("C",f,null); BinTree tree = new BinTree("A",b,c); System.out.println("前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍历二叉树结果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍历二叉树结果: "); tree.postOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的层次: "+tree.level("F")); System.out.println("这棵二叉树的高度: "+tree.height()); System.out.println("--------------------------------------"); tree.reflect(); System.out.println("交换每个节点的孩子节点后......"); System.out.println("前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍历二叉树结果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍历二叉树结果: "); tree.postOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的层次: "+tree.level("F")); System.out.println("这棵二叉树的高度: "+tree.height());

建立一个二叉树，附带查询代码，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：二叉树添加和查询方法

package arrays.myArray;

public class BinaryTree {

private Node root;

// 添加数据

public void add(int data) {

// 递归调用

if (null == root)

root = new Node(data, null, null);

else

addTree(root, data);

}

private void addTree(Node rootNode, int data) {

// 添加到左边

if (rootNode.data data) {

if (rootNode.left == null)

rootNode.left = new Node(data, null, null);

else

addTree(rootNode.left, data);

} else {

// 添加到右边

if (rootNode.right == null)

rootNode.right = new Node(data, null, null);

else

addTree(rootNode.right, data);

}

}

// 查询数据

public void show() {

showTree(root);

}

private void showTree(Node node) {

if (node.left != null) {

showTree(node.left);

}

System.out.println(node.data);

if (node.right != null) {

showTree(node.right);

}

}

}

class Node {

int data;

Node left;

Node right;

public Node(int data, Node left, Node right) {

this.data = data;

this.left = left;

this.right = right;

}

}

当前标题：关于java二叉树的代码 关于java二叉树的代码有哪些
URL标题：http://myzitong.com/article/hghood.html