用java编写二叉树代码 java二叉树实现

用java怎么构造一个二叉树？

二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、成都网站设计、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的回民网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

package com.algorithm.tree;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Queue;

import java.util.Scanner;

import java.util.Stack;

import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {

}

public Tree(Node root) {

this.root = root;

}

//创建二叉树

public void buildTree() {

Scanner scn = null;

try {

scn = new Scanner(new File("input.txt"));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

root = createTree(root,scn);

}

//先序遍历创建二叉树

private Node createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {

return null;

} else {

node = new Node((T)temp);

node.setLeft(createTree(node.getLeft(), scn));

node.setRight(createTree(node.getRight(), scn));

return node;

}

}

//中序遍历(递归)

public void inOrderTraverse() {

inOrderTraverse(root);

}

public void inOrderTraverse(Node node) {

if (node != null) {

inOrderTraverse(node.getLeft());

System.out.println(node.getValue());

inOrderTraverse(node.getRight());

}

}

//中序遍历(非递归)

public void nrInOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

System.out.println(node.getValue());

node = node.getRight();

}

}

//先序遍历(递归)

public void preOrderTraverse() {

preOrderTraverse(root);

}

public void preOrderTraverse(Node node) {

if (node != null) {

System.out.println(node.getValue());

preOrderTraverse(node.getLeft());

preOrderTraverse(node.getRight());

}

}

//先序遍历（非递归）

public void nrPreOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

System.out.println(node.getValue());

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

node = node.getRight();

}

}

//后序遍历(递归)

public void postOrderTraverse() {

postOrderTraverse(root);

}

public void postOrderTraverse(Node node) {

if (node != null) {

postOrderTraverse(node.getLeft());

postOrderTraverse(node.getRight());

System.out.println(node.getValue());

}

}

//后续遍历(非递归)

public void nrPostOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

Node preNode = null;//表示最近一次访问的节点

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {

System.out.println(node.getValue());

node = stack.pop();

preNode = node;

node = null;

} else {

node = node.getRight();

}

}

}

//按层次遍历

public void levelTraverse() {

levelTraverse(root);

}

public void levelTraverse(Node node) {

QueueNode queue = new LinkedBlockingQueueNode();

queue.add(node);

while (!queue.isEmpty()) {

Node temp = queue.poll();

if (temp != null) {

System.out.println(temp.getValue());

queue.add(temp.getLeft());

queue.add(temp.getRight());

}

}

}

}

//树的节点

class Node {

private Node left;

private Node right;

private T value;

public Node() {

}

public Node(Node left,Node right,T value) {

this.left = left;

this.right = right;

this.value = value;

}

public Node(T value) {

this(null,null,value);

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public T getValue() {

return value;

}

public void setValue(T value) {

this.value = value;

}

}

测试代码：

package com.algorithm.tree;

public class TreeTest {

/**

* @param args

*/

public static void main(String[] args) {

Tree tree = new Tree();

tree.buildTree();

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

tree.inOrderTraverse();

tree.nrInOrderTraverse();

System.out.println("后续遍历");

//tree.nrPostOrderTraverse();

tree.postOrderTraverse();

tree.nrPostOrderTraverse();

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

tree.preOrderTraverse();

tree.nrPreOrderTraverse();

//

}

}

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实现二叉树

我有很多个(假设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写二叉树

/**

* [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如何创建一颗二叉树

计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

树是由一个或多个结点组成的有限集合，其中：

⒈必有一个特定的称为根(ROOT)的结点；

二叉树

⒉剩下的结点被分成n=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

2.树的深度——组成该树各结点的最大层次。

3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；

4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

树的表示

树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如右图可写成如下形式：

二叉树

(a( b(d,e), c( f( ,g(h,i) ), )))