首先我想问为什么要用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=0i<input.lengthi++)

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

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

for(int i=0i<input.lengthi++){

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

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

}

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

//******************************************************************************************************//

//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40

private Object data//数据元数

private BinTree left,right//指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX]//层次遍历时保存各个节点

int front//层次遍历时队首

int rear//层次遍历时队尾

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=0rear=1

while(front<rear)

{

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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0)

return -1

levelInTree = leftLevel<rightLevel?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()

{

String innerNode = ""

if(this == null)

return

//若本节点是叶节点，则将其移走

if(left==null&&right == null)

{

System.out.print(this + " ")

data = null

return

}

//移走左子树若其存在

if(left!=null){

left.defoliate()

left = null

}

//移走本节点，放在中间表示中跟移走...

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

}

你的程序有诸多问题，你的程序运行时候应该也会报错的吧？

这个写法不是很通用，不过我还是按照你的源码修改成了你想要的结果。

结构上基本一致，可实现基本已经面目全非了。

我用字符串代替了手工输入，你要是喜欢手工输入，你可以把我那个注释掉，用你自己的……

以下是修改后可用的代码：

import java.util.*

class Node {

Node left

Node Right

char data// 节点数据

void print() {

System.out.println(data + "")

}

public Node() {

this.left = null

this.Right = null

}

public Node(char data) {

this.left = null

this.Right = null

this.data = data

}

}

class BTree {

static Node root = new Node()// 为根节点分配空间

static char ch[]// 输入的字符串

static int i = 0

static Node CreateTree()// 先序建立二叉树

{

Node node = null

if (ch[i] == '#') {

node = null

i++

}else {

node = new Node()

node.data = ch[i]

i++

node.left = CreateTree()

node.Right = CreateTree()

}

return node

}

static public void preorder(Node node)// 先序遍历二叉树

{

if (node != null) {

node.print()

preorder(node.left)

preorder(node.Right)

} else {

System.out.println("Tree node is empty")

}

}

}

public class Tree {

public static void main(String args[]) {

Scanner reader = new Scanner(System.in)

BTree.ch = new char[16]

BTree.ch[0] = 'a'

// 读取输入字符数组，以*结尾

BTree.ch = "ABC##DE#G##F###".toCharArray()

//for (int i = 0(BTree.ch[i] = reader.next().charAt(0)) != '*'i++){}

BTree.root = BTree.CreateTree()

BTree.preorder(BTree.root)

}

}

---