个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，
那么，碰巧要找的数字位于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)
}
}
计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（leftsubtree）和“右子树”（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)
),
)))
