个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，
那么，碰巧要找的数字位于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(value>this.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=0i<data.lengthi++)
{
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=1i<data.lengthi++)
{
root.store(data[i])
}
root.find(data[19])
root.preList()
System.out.println()
root.middleList()
System.out.println()
root.afterList()
}
}
做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个insert大量同时顺序自增插入的时候，树就会失去平衡。树的一方为了不让塌陷，会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。import java.util.List
import java.util.LinkedList
public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}
private static List<Node>nodeList = null
private static class Node {
Node leftChild
Node rightChild
int data
Node(int newData) {
leftChild = null
rightChild = null
data = newData
}
}
// 创建二叉树
public void createBintree() {
nodeList = new LinkedList<Node>()
// 将数组的值转换为node
for (int nodeIndex = 0nodeIndex <array.lengthnodeIndex++) {
nodeList.add(new Node(array[nodeIndex]))
}
// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
for (int parentIndex = 0parentIndex <array.length / 2 - 1parentIndex++) {
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)
}
}
// 前序遍历
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)
}
}
首先我想问为什么要用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个元素就是树根，思路大体是这样吧。
