JAVA 實現(xiàn)二叉樹（鏈式存儲結構）

更新時間：2016年07月12日 16:20:45 投稿：lqh

本篇文章主要介紹用JAVA 實現(xiàn)二叉樹,并提供實例.對二叉樹數(shù)據(jù)結構很好的學習實踐,有需要的朋友可以參考下

二叉樹的分類（按存儲結構）

樹的分類（按存儲結構）

　順序存儲（用數(shù)組表示（靜態(tài)二叉樹））
　　　　鏈式存儲

一些特別的二叉根：

完全二叉樹，平衡二叉樹（AVL），線索二叉樹，三叉的（帶父親的指針）
　　　　　　　　　二叉搜索樹或者叫二叉　查找樹（BST）

所用二叉樹如下圖所示：

二叉樹的Java實現(xiàn)（鏈式存儲結構）

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){
    //手動的創(chuàng)建（結構如圖所示）
    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() {
    // 求結點數(shù)
    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) {
    //私有函數(shù): 刪除根為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)