樹結構數據存儲

『壹』 數據結構學習——樹(Tree)

數據結構學習——樹(Tree)

樹是一種重要的非線性數據結構，它模擬了自然界中樹的形態，具有層次性和分支性。以下是關於樹的詳細解析：

一、概述

1. 樹結構

   樹結構之所以稱之為樹結構，是因為它的長相就是一種樹狀結構。每一棵樹都有一個主幹（根節點），每個主幹可以分為許多子干（子節點），每個子干又可以分為許多孫子干（孫節點），以此類推。

   

   優點：便於查找某個節點的所有子節點。

   缺點：需要額外的存儲空間來存儲孩子鏈表，且查找父節點需要遍歷所有節點。

2. 兄弟表示法

   每個節點擁有兩類參數：一類用於存儲自身數據，另一類存儲兄弟節點（即同層次的其他節點）。

   優點：便於查找某個節點的所有兄弟節點。

   缺點：無法直接表示上級和下級節點關系，通常需要結合其他表示法使用。

3. 總結

   在日常開發中，可以根據具體的應用場景選擇合適的樹表示法。不同的表示法可以相互組合，以充分利用各自的優點並彌補彼此的不足。

通過以上內容的學習，可以深入理解樹這種數據結構的基本概念、特點、術語以及存儲結構，為後續的數據結構學習和演算法實現打下堅實的基礎。

『貳』 資料庫物理結構中，存儲著哪幾種形式的數據結構

資料庫物理結構中，主要存儲著以下幾種形式的數據結構：

1. 記錄的存儲方式：

   • 順序存儲：數據按照一定順序連續存儲在磁碟或內存中。
   • B樹結構存儲：一種平衡樹結構，用於存儲和檢索大量有序數據，具有良好的平衡性和查找效率。
   • Hash方法存儲：通過哈希函數將數據映射到特定的存儲位置，實現快速查找。

2. 索引的組織方式：索引是資料庫中用於加速數據檢索的數據結構，如B+樹索引、哈希索引等，它們以不同的方式組織數據以提高查詢效率。

3. 數據存儲記錄結構：這包括數據在物理存儲介質上的具體表示形式，如定長記錄、變長記錄等，以及記錄之間的關聯方式。

4. 壓縮存儲和加密存儲：

   • 壓縮存儲：為了減少存儲空間，數據在存儲前可能會進行壓縮處理。
   • 加密存儲：為了保證數據的安全性，數據在存儲時可能會進行加密處理。

這些數據結構共同構成了資料庫的物理存儲模式，決定了數據在資料庫內部的表示方式和存儲方式。

『叄』 數據結構——樹

一、樹的概念

樹是區別於線性表的另一種數據結構，其本質是結點的有限集。樹的定義包含以下兩點：

• 有且僅有一個特定的稱為根（root）的結點。
• 當結點數量大於1時，其餘結點可分為若干個互不相交的有限集，其中每個集合也可以看作一棵樹，稱之為根的子樹。

1. 度（結點的分類）

• 結點擁有的子樹的數量稱為該結點的度。
• 樹的度則是這棵樹中度最多的結點的度的值。

例如，在圖中，B結點的度為1（因為它只擁有一顆子樹D），而D的度為3（因為它擁有G、H、I三顆子樹）。A結點的度則取決於它擁有的子樹數量。

2. 結點之間的關系

• 結點的子樹的根稱之為該結點的孩子（child結點）。
• 該結點衍生出來的結點稱之為該結點的父母（parent結點）。
• 由同一個結點衍生出的同一層結點互相稱之為兄弟（sibling）。
• 由同一個結點之下的所有結點稱之為子孫。

3. 樹的層與深度

• 結點的層次從根算起，根為第一層，根的孩子為第二層，以此類推。
• 一棵樹的深度是樹中結點層次最大的值，也稱為樹的高度。

二、樹的存儲結構

雙親孩子表示法：

• 把樹中的所有結點的值依次組成一個單鏈表。
• 每個結點定義三個域：數據域、父母指針域、長子（第一個孩子）指針域。
• 如果長子有兄弟，則指針域指向下一個存儲兄弟位置的指針域，否則為空。

三、二叉樹

1. 二叉樹的定義

• 二叉樹由一個根節點和兩顆互不相交的、分別稱為根節點的左子樹和右子樹的二叉樹組成（二叉樹是遞歸定義）。

2. 二叉樹的特點

• 每個結點最多有兩顆子樹。
• 左子樹與右子樹有順序，即使一棵樹中只有一個子樹，也需要判斷是左子樹還是右子樹。

3. 一些特殊的二叉樹

• 斜樹：所有結點都只有左子樹或所有結點都只有右子樹的二叉樹稱為斜樹（斜樹類似於單鏈表）。
• 滿二叉樹：如果一棵二叉樹的所有分支結點都存在左右子樹，並且所有的葉子結點都在同一層，則稱之為滿二叉樹。
• 完全二叉樹：如果每個結點按層序編號與相同層數的滿二叉樹編號一致，則這棵樹稱為完全二叉樹。

4. 二叉樹的性質

• 在二叉樹的第n層上最多有2^(n - 1)個結點。
• 深度為k的二叉樹至多有2^k - 1個結點。
• 一顆二叉樹的葉子結點數為n，度為2的結點數量為m，則n = m + 1。
• 具有n個結點的完全二叉樹深度為log2n + 1。
• 對於一顆結點數量為n的完全二叉樹，n為樹的深度，i為按樹的層為結點編號，則有：

  若i = 1，則此結點為根結點。

  若i > 2^n，則此結點的左孩子不存在。

  若i結點存在右孩子，則右孩子序號為2i + 1。

5. 二叉樹的存儲結構

• 順序存儲結構：將二叉樹中的每一個結點按照滿二叉樹的層次序號進行編號，將空著的編號留空，將結點中的數據存入數組對應編號中。但這種方法浪費存儲空間，只適用於完全二叉樹。
• 二叉鏈表：每個結點定義兩個指針域，分別是lchild（左孩子）和rchild（右孩子）。這種方法適用於任意二叉樹。

6. 二叉樹的遍歷

• 前序遍歷：按照根結點->左子樹->右子樹的順序遍歷。
• 中序遍歷：按照左子樹->根結點->右子樹的順序遍歷。
• 後序遍歷：按照左子樹->右子樹->根結點的順序遍歷。
• 層序遍歷：按照一層一層從左到右的順序依次遍歷樹。

以下是各遍歷方法的圖示：

遞歸遍歷的核心思想是理解遞歸，通過遞歸或棧的思想可以實現二叉樹的遍歷。

『肆』 怎樣在 MySQL 表中存儲樹形結構數據

一般比較普遍的就是四種方法：

（具體見 SQL Anti-patterns這本書）Adjacency List：

每一條記錄存parent_idPath Enumerations：

每一條記錄存整個tree path經過的node枚舉Nested Sets：

每一條記錄存 nleft 和 nrightClosure Table：

維護一個表，所有的tree path作為記錄進行保存。各種方法的常用操作代價見下圖