JAVA 完成二叉樹（鏈式存儲構造）

JAVA 完成二叉樹（鏈式存儲構造）。本站提示廣大學習愛好者：（JAVA 完成二叉樹（鏈式存儲構造））文章只能為提供參考，不一定能成為您想要的結果。以下是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法式設計的同窗有所贊助。