Java 樹結構詳解

什麼是樹(tree)

樹結構是一種廣泛使用於資料結構中的非線性資料結構，用於表示具有階層關係的資料。樹由節點(Node) 和連接節點的邊(Edge)組成。其中，一個樹結構包含一個根節點(Root Node)，以及零個或多個子樹(Subtrees)，每個子樹也是一個樹。樹結構在文件結構、組織架構、資料庫索引等領域有著廣泛的應用。

基本術語

節點(Node):

樹的基本部分，可以有零個或多個子節點。

根節點(Root Node):

樹頂的節點，沒有父節點。

葉節點(Leaf Node):

沒有子節點的節點。

父節點(Parent Node):

若一個節點含有子節點，則該節點被視為父節點。

子節點(Child Node):

節點的直接後裔。

兄弟節點(Sibling Nodes):

具有相同父節點的節點。

深度(Depth):

從根節點到某一節點的邊的數量。

高度(Height):

從某一節點到最遠葉節點的最長路徑的邊的數量。

範例

實作一個二叉樹(Binary Tree)

• 定義

  class TreeNode {
  int value;
  TreeNode left;
  TreeNode right;
  
  public TreeNode(int value) {
      this.value = value;
      this.left = null;
      this.right = null;
       }
  }

• 實作

  class BinaryTree {
      TreeNode root;
  
      public BinaryTree() {
          root = null;
      }
  
      // 插入節點
      public void insert(int value) {
          root = insertRec(root, value);
      }
  
      private TreeNode insertRec(TreeNode root, int value) {
          if (root == null) {
              root = new TreeNode(value);
              return root;
          }
          if (value < root.value)
              root.left = insertRec(root.left, value);
          else if (value > root.value)
              root.right = insertRec(root.right, value);
          return root;
      }
  
      // 中序遍歷
      public void inorder() {
          inorderRec(root);
      }
  
      private void inorderRec(TreeNode root) {
          if (root != null) {
              inorderRec(root.left);
              System.out.print(root.value + " ");
              inorderRec(root.right);
          }
      }
  
      // 添加其他遍歷方法...
  }

• 測試

  public class Main {
      public static void main(String[] args) {
          BinaryTree tree = new BinaryTree();
          tree.insert(50);
          tree.insert(30);
          tree.insert(20);
          tree.insert(40);
          tree.insert(70);
          tree.insert(60);
          tree.insert(80);
  
          System.out.println("中序遍歷的結果：");
          tree.inorder(); // 預期輸出：20 30 40 50 60 70 80
      }
  }