二叉树的每个结点至多只有二棵子树(不存在度大于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) ),)))
定义一个结点类：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
HashMap<String, Integer>map = new HashMap<String, Integer>()
Node nodeTree = new Node()
Scanner reader = new Scanner(System.in)
nodeNumber = reader.nextInt()
for(int i = 0i <nodeNumberi++) {
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(HashMap<String, 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())
}
}
