DSA 樹
樹
樹資料結構與連結串列類似，它包含資料，並且可以連結到其他節點。
我們之前已經介紹過陣列、連結串列、棧和佇列等資料結構。這些都是線性結構，意味著每個元素都在序列中緊隨另一個元素。然而，樹不同。在樹中，單個元素可以有多個“下一個”元素，從而允許資料結構向各個方向分支。
這個資料結構被稱為“樹”，因為它看起來像一棵樹，只是顛倒過來的，就像下面的圖片一樣。
樹資料結構在許多情況下都很有用
- 分層資料：檔案系統、組織模型等。
- 資料庫：用於快速檢索資料。
- 路由表：用於網路演算法中的資料路由。
- 排序/搜尋：用於對資料進行排序和搜尋資料。
- 優先佇列：優先佇列資料結構通常使用樹來實現，例如二叉堆。
樹的術語和規則
透過使用下面的互動式樹視覺化，學習用於描述樹資料結構的詞彙。
樹中的第一個節點稱為根節點。
連線一個節點到另一個節點的連結稱為邊。
父節點連結到其子節點。父節點的另一個說法是內部節點。
一個節點可以有零個、一個或多個子節點。
一個節點只能有一個父節點。
沒有連結到其他子節點的節點稱為葉子或葉節點。
樹的高度是從根節點到葉節點的最大邊數。上圖的高度是 2。
節點的高度是節點與葉節點之間的最大邊數。
樹的大小是樹中節點的數量。
樹的型別
樹是計算機科學中的一種基本資料結構，用於表示分層關係。本教程涵蓋了幾種關鍵的樹型別。
二叉樹：每個節點最多有兩個子節點，即左子節點和右子節點。這種結構是二叉搜尋樹和 AVL 樹等更復雜樹型別的基礎。
二叉搜尋樹（BST）：一種二叉樹，其中對於每個節點，左子節點的值較低，而右子節點的值較高。
AVL 樹：一種二叉搜尋樹，它會自我平衡，使得對於每個節點，左子樹和右子樹的高度差最多為一。透過在插入或刪除節點時進行旋轉來維持這種平衡。
這些資料結構中的每一種都在接下來的頁面中進行了詳細描述，包括動畫和如何實現它們。
