JAVA 实现二叉树（链式存储结构）

二叉树的分类（按存储结构）

树的分类（按存储结构）

　顺序存储（用数组表示（静态二叉树））
　　　　  链式存储

一些特别的二叉根：

完全二叉树，平衡二叉树（AVL），线索二叉树，三叉的（带父亲的指针）
　　　　　　　　　   二叉搜索树或者叫二叉　查找树（BST）

 所用二叉树如下图所示：

二叉树的Java实现（链式存储结构）

class TreeNode {
  private int key = 0;
  private String data = null;
  private boolean isVisted = false;
  private TreeNode leftChild = null;
  private TreeNode rightChild = null;

  public TreeNode(){

  }
  public TreeNode(int key, String data){
    this.key = key;
    this.data = data;
    this.leftChild = null;
    this.rightChild = null;
  }
  public int getKey() {
    return key;
  }
  public void setKey(int key) {
    this.key = key;
  }
  public String getData() {
    return data;
  }
  public void setData(String data) {
    this.data = data;
  }
  public TreeNode getLeftChild() {
    return leftChild;
  }
  public void setLeftChild(TreeNode leftChild) {
    this.leftChild = leftChild;
  }
  public TreeNode getRightChild() {
    return rightChild;
  }
  public void setRightChild(TreeNode rightChild) {
    this.rightChild = rightChild;
  }
  public boolean isVisted() {
    return isVisted;
  }
  public void setVisted(boolean isVisted) {
    this.isVisted = isVisted;
  }
}

public class BinaryTree {

  private TreeNode root = null;

  public BinaryTree() {
    root = new TreeNode(1, "rootNode(A)");
  }
  public void createBinTree(TreeNode root){
    //手动的创建（结构如图所示）
    TreeNode newNodeB = new TreeNode(2,"B");
    TreeNode newNodeC = new TreeNode(3,"C");
    TreeNode newNodeD = new TreeNode(4,"D");
    TreeNode newNodeE = new TreeNode(5,"E");
    TreeNode newNodeF = new TreeNode(6,"F");
    root.setLeftChild(newNodeB);
    root.setRightChild(newNodeC);
    root.getLeftChild().setLeftChild(newNodeD);
    root.getLeftChild().setRightChild(newNodeE);
    root.getRightChild().setRightChild(newNodeF);
  }
  public boolean IsEmpty() {
    // 判二叉树空否
    return root == null;
  }

  public int Height() {
    // 求树高度
    return Height(root);
  }

  public int Height(TreeNode subTree) {
    if (subTree == null)
      return 0; //递归结束：空树高度为0
    else {
      int i = Height(subTree.getLeftChild());
      int j = Height(subTree.getRightChild());
      return (i < j) ? j + 1 : i + 1;
    }

  }

  public int Size() {
    // 求结点数
    return Size(root);
  }

  public int Size(TreeNode subTree) {
    if (subTree == null)
      return 0;
    else {
      return 1 + Size(subTree.getLeftChild())
          + Size(subTree.getRightChild());
    }
  }

  public TreeNode Parent(TreeNode element) {
    //返回双亲结点
    return (root == null || root == element) ? null : Parent(root, element);
  }

  public TreeNode Parent(TreeNode subTree, TreeNode element) {

    if (subTree == null)
      return null;
    if (subTree.getLeftChild() == element
        || subTree.getRightChild() == element)
      //找到, 返回父结点地址
      return subTree;
    TreeNode p;
    //先在左子树中找，如果左子树中没有找到，才到右子树去找
    if ((p = Parent(subTree.getLeftChild(), element)) != null)
      //递归在左子树中搜索
      return p;
    else
      //递归在左子树中搜索
      return Parent(subTree.getRightChild(), element);

  }

  public TreeNode LeftChild(TreeNode element) {
    //返回左子树
    return (element != null) ? element.getLeftChild() : null;
  }

  public TreeNode RightChild(TreeNode element) {
    //返回右子树
    return (element != null) ? element.getRightChild() : null;
  }

  public TreeNode getRoot() {
    //取得根结点
    return root;
  }

  public void destroy(TreeNode subTree) {
    //私有函数: 删除根为subTree的子树
    if (subTree != null) {
      destroy(subTree.getLeftChild()); //删除左子树
      destroy(subTree.getRightChild()); //删除右子树
      //delete subTree;       //删除根结点
      subTree = null;
    }
  }

  public void Traverse(TreeNode subTree) {

    System.out.println("key:" + subTree.getKey() + "--name:"
        + subTree.getData());
    Traverse(subTree.getLeftChild());
    Traverse(subTree.getRightChild());
  }

  public void PreOrder(TreeNode subTree) {
    //先根
    if (subTree != null) {
      visted(subTree);
      PreOrder(subTree.getLeftChild());
      PreOrder(subTree.getRightChild());
    }
  }

  public void InOrder(TreeNode subTree) {
    //中根
    if (subTree != null) {
      InOrder(subTree.getLeftChild());
      visted(subTree);
      InOrder(subTree.getRightChild());
    }
  }

  public void PostOrder(TreeNode subTree) {
    //后根
    if (subTree != null) {
      PostOrder(subTree.getLeftChild());
      PostOrder(subTree.getRightChild());
      visted(subTree);
    }
  }
  public void LevelOrder(TreeNode subTree) {
     //水平遍边
  }
  public boolean Insert(TreeNode element){
    //插入
    return true;
  }
  public boolean Find(TreeNode element){
    //查找
    return true;
  }
  public void visted(TreeNode subTree) {
    subTree.setVisted(true);
    System.out.println("key:" + subTree.getKey() + "--name:"
        + subTree.getData());
  }

  public static void main(String[] args) {
    BinaryTree bt = new BinaryTree();
    bt.createBinTree(bt.root);
    System.out.println("the size of the tree is " + bt.Size());
    System.out.println("the height of the tree is " + bt.Height());
    System.out.println("*******先根(前序)[ABDECF]遍历*****************");
    bt.PreOrder(bt.root);
    System.out.println("*******中根(中序)[DBEACF]遍历*****************");
    bt.InOrder(bt.root);
    System.out.println("*******后根(后序)[DEBFCA]遍历*****************");
    bt.PostOrder(bt.root);
  }

}

结果输出：
the size of the tree is 6
the height of the tree is 3
*******先根(前序)[ABDECF]遍历*****************
key:1--name:rootNode(A)
key:2--name:B
key:4--name:D
key:5--name:E
key:3--name:C
key:6--name:F
*******中根(中序)[DBEACF]遍历*****************
key:4--name:D
key:2--name:B
key:5--name:E
key:1--name:rootNode(A)
key:3--name:C
key:6--name:F
*******后根(后序)[DEBFCA]遍历*****************
key:4--name:D
key:5--name:E
key:2--name:B
key:6--name:F
key:3--name:C
key:1--name:rootNode(A)

希望本文对学习JAVA程序设计的同学有所帮助。