1. 前言樹是一種很重要的數據結構，最初對數據結構的定義就是指對樹和圖的研究 ， 后來才廣義化了數據結構這個概念 。從而可看出樹和圖在數結構這一研究領域的重要性 。
樹和圖重要的原因是，它讓計算機能建模出現實世界中更多領域里錯綜復雜的信息關系，讓計算機服務這些領域成為可能 。
本文將和大家聊聊樹的基本概念，以及樹的物理存儲結構以及實現 。
2. 基本概念數據結構的研究主要是從 2 點出發：
- 洞悉數據與數據之間的邏輯關系 。
- 設計一種物理存儲方案 。除了存儲數據本身還要存儲數據之間的邏輯關系，并且能讓基于此數據上的算法利用這種存儲結構達到事半功倍的效果 。
文章插圖
完整的
樹結構除了需要描述出數據信息 ， 還需要描述數據與數據之間的關系 。樹結構中，以節點作為數據的具體形態，邊作為數據之間關系的具體形態 。也可以說樹是由很多
節點以及邊組成的集合 。如果一棵樹沒有任何節點，則稱此樹為空樹 。如果樹不為空，則此樹存在唯一的根節點
（root） ， 根節點是整棵樹的起點，其特殊之處在于沒有前驅節點 。如上圖值為董事長的節點 。除此之外，樹中的節點與節點之間會存在如下關系：
- 父子關系：節點的前驅節點稱其為父節點 ， 且只能有一個或沒有（如根節點） 。節點的后驅節點稱其為子節點 ， 子節點可以有多個 。如上圖的
董事長節點是市場總經理節點的父節點，反之 ，市場總經理節點是董事長節點的子節點 。 - 兄弟關系： 如果節點之間有一個共同的前驅（父）節點，則稱這些節點為兄弟節點 。如上圖的
市場總經理節點和運維總經理節點為兄弟關系 。 - 葉節點： 葉節點是沒有后驅（子）節點的節點 。
- 子樹：一棵樹也可以理解是由子節點為根節點的子樹組成，子樹又可以理解為多個子子樹組成…… 所以樹可以描述成是樹中之樹式的遞歸關系 。
T 樹。
文章插圖
可以理解為
T1和T2子樹組成 。
文章插圖
T1、T2又可以認為是由它的子節點為根節點的子子樹組成，以此類推，一直到葉節點為止 。樹的相關概念：
- 節點的度： 一個節點含有子樹的個數稱為該節點的度 。
- 樹的度：一棵樹中，最大的節點的度稱為樹的度 。
- 節點的層次：同級的節點為一個層次 。根節點為第
1層，根的子節點為第2層，以此類推 。 - 樹的高（深）度： 樹中節點最大的層次 。如上圖中的樹的最大層次為
4。
- 無序樹：樹中的結點之間沒有順序關系，這種樹稱為無序樹 。
- 有序樹：樹中任意節點的子節點之間有左右順序關系 。如下圖，任一節點的左子節點值小于右子節點值 。
文章插圖
- 二叉樹：如果任一節點最多只有
2個子節點，則稱此樹結構為二叉樹 。上圖的有序樹也是一棵二叉樹 。
- 完全二叉樹：一棵二叉樹至多只有最下面兩層的節點的子結點可以小于
2。并且最下面一層的節點都集中在該層最左邊的若干位置上 。
- 滿二叉樹：除了葉節點，其它節點的子結點都有
2個 。如上圖中的樹也是滿二叉樹 。
鄰接矩陣和鄰接表的形式存儲樹 。3.1 鄰接矩陣存儲鄰接矩陣是順序表存儲方案 。
3.1.1 思路流程
- 給樹中的每一個節點從小到大進行編號 。如下圖 ， 樹共有
11個節點 。
文章插圖
