二叉树（Binary Tree ）是一种常见的数据结构，在游戏常作为判定树，对AI行为进行控制，如：在当战斗时攻击OR 防御，攻击时，普通攻击OR魔法攻击等等。
二叉树的定义与结构特点，在此就不作说明。
二叉树的一些特性：
1.第i层最多有2^（i-1）个节点（i >=1）;
2.深度为h的二叉树最多有2^h - 1个节点;
3.对于任何一棵二叉树T，如果叶子结点数为N，度为2的结点数为M,则N=M+1;
4.具有n个结点的完全二叉树深度为[㏒<sub>2</sub>n]
二叉树的Java实现：
package com.whs.datastruct;
import java.util.Scanner;
/**
* 二叉树
*
*@author wuhaishengxxx
*
*/
public class BinaryTree {
static Scanners canner=new Scanner(System.in);
// 创建
static class Node {
String value;
Node parent;
Node left;
Node right;
}
// 注意： Java 是值传递，因此在此通过返回值去重新赋值
public static Node createTree(Node tree) {
System.out.println("请输入结点值：");
String s =scanner.nextLine();
if(!"null".equalsIgnoreCase(s)) {
tree=new Node();
tree.value=s;
tree.left= createTree(tree.left);
if(tree.left!=null) {
tree.left.parent=tree;
}
System.out.println(s+" left end");
tree.right= createTree(tree.right);
if(tree.right!=null) {
tree.right.parent=tree;
}
System.out.println(s+" right end");
return tree;
}else{
return null;
}
}
// 先遍历
public static void preOrderTree(Node tree) {
if(tree!=null) {
showTree(tree);
preOrderTree(tree.left);
preOrderTree(tree.right);
}
}
// 用于输出显示
public static void showTree(Node tree) {
if(tree!=null) {
System.out.print("Node:"+tree.value+" ");
System.out.print("{");
if(tree.left!=null) {
System.out.print(" left: "+tree.left.value);
}
if(tree.right!=null) {
System.out.print(" right: "+tree.right.value);
}
System.out.println("}");
}
}
// 中序遍历
publicstaticvoidinOrderTree(Nodetree) {
if(tree!=null) {
inOrderTree(tree.left);
showTree(tree);
inOrderTree(tree.right);
}
}
// 后序遍历
public static void postOrderTree(Node tree) {
if(tree!=null) {
postOrderTree(tree.left);
postOrderTree(tree.right);
showTree(tree);
}
}
// 层次遍历
public static void levelOrderTree(Node tree) {
if(tree!=null) {
if(tree.parent==null) {
showTree(tree);
}
showTree(tree.left);
showTree(tree.right);
levelOrderTree(tree.left);
levelOrderTree(tree.right);
}
}
public static void main(String[] args) {
Node root=null;
root= createTree(root);
System.out.println("先序遍历:");
preOrderTree(root);
System.out.println("中序遍历：");
inOrderTree(root);
System.out.println("后序遍历：");
postOrderTree(root);
System.out.println("层次遍历：");
levelOrderTree(root);
}
}