【数据结构】树的认识
一個人的未來不是預測出來的，而是創造出來的。? ? ? ? ? ? ? ? ? ? ? ? -- 亞當·詹姆斯
目錄
🍁前言：
🍀一.什么是樹？
🍑二.樹有什么用？?
??1. 數據庫
🧡2. 文件系統
💛3. 編程語言
💚4. 網絡
💜5. 人工智能
🍂三.樹的基礎知識
🌳四.樹的存儲結構
🍐1.雙親表示法
🍍2.孩子表示法
🍁3.孩子兄弟表示法
前言：
前面我們學習了，順序表，鏈表，棧和隊列，它們都是一對一的線性結構，但是往往還有一對多的情況，這就是我們今天要學習的一對多的數據結構：樹（Tree）。樹比前面的數據結構學起來要難一點，希望大家能夠反復的學習，達到熟能生巧。
學習樹的知識框架：
🍀一.什么是樹？
想到樹，大家可能都會想到現實中的樹，各種各樣的樹，就像下面這樣，這是一顆很漂亮的樹。
而今天我們要學習的數據結構的樹是怎么樣的呢？
樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
有一個特殊的結點，稱為根結點，根節點沒有前驅結點，除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼。因此，樹是遞歸定義的。
這個結構就是一個樹，它是不是很像現實中的樹，給倒過來的。我想它之所以叫樹，可能也是這個原因吧。?
注意：樹的子樹之間不能有交集。就像下面這樣：
打?的地方，子樹之前發生了交集，這樣是不可以的，如果這樣，它就不能稱作為樹。
🍑二.樹有什么用？?
數據結構樹的應用：
數據結構是計算機科學中重要的一個分支，而樹是其中一種重要且實用的數據結構之一。樹是由一個根節點和若干子節點組成的一種非線性數據結構，被廣泛應用于計算機領域中，特別是在算法設計和數據處理方面。下面我們將詳細介紹樹的應用領域。
注意:下面的樹的應用都是高階的數據結構的樹，C++才會學習。
??1. 數據庫
在數據庫管理系統中，樹被廣泛應用于索引結構。數據庫中的查找過程可以轉化為在樹中查找某個節點的過程。常用的樹結構包括B-樹、B+樹和紅黑樹，這些結構可以高效的處理大量數據，支持高效的檢索和排序。
🧡2. 文件系統
操作系統中的文件系統其實就是一種樹形結構。目錄和文件被視為節點，而目錄之間的關系和文件之間的關系則是樹的關系。基于樹形結構的文件系統使得我們可以很方便地在系統中查找和管理文件。
下面就是操作系統的文件系統，它就是一種樹形的結構，使用樹來實現。
💛3. 編程語言
樹形結構被廣泛運用于編程語言中。AST（抽象語法樹）就是一種常見的語法分析樹，它將程序中的語句和表達式抽象成一個樹形結構，在編譯器中被廣泛使用，可以很方便地實現代碼的詞法分析、語義分析和優化。此外，樹也可以用于構建運行時數據結構，如二叉搜索樹、Trie樹、AVL樹等等。?
💚4. 網絡
在計算機網絡中，樹的結構被廣泛應用于路由器和交換機中。這些設備需要通過識別和分析網絡中的數據包，將它們分配到不同的路由或交換機上進行處理。樹的結構使得這些設備可以很方便地對不同的數據包進行分類、處理和轉發。
💜5. 人工智能
在人工智能中，樹也是非常重要的一種數據結構。決策樹是常用的機器學習算法之一，它通過一系列的二叉樹形結構對數據進行分類和判斷。在處理自然語言、語音識別和圖像處理等領域中，樹結構也被廣泛應用。
總之，數據結構樹在計算機領域中有著非常廣泛的應用，可以用于解決各種問題。從數據庫、文件系統到編程語言、網絡和人工智能等領域，都需要樹這種數據結構來達到高效、快速、準確處理數據的目的。因此，學習并掌握樹這種數據結構非常重要，可以幫助我們更好地理解計算機領域內的各種問題和算法。
🍂三.樹的基礎知識
節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6。
葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I...等節點為葉節點。
非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G...等節點為分支節點。
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點。
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；如上圖：B是A的孩子節點。
兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點。
樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6。
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推。
樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4。
堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點。
節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先。
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林。
總結：上述的這些都是關于樹的一些基礎知識，你不必刻意的去記憶，這些概念就像人類的親緣關系一樣，多看見幾遍也就記住了。
現在我們是先初入樹，先了解一些樹的基本知識，為了方便后面學習二叉樹。
🌳四.樹的存儲結構
說到存儲結構，這就不得不想起之前學過的順序和鏈式兩種存儲結構。先看看順序存儲結構，用一段地址連續的存儲單元依次存儲線性表的數據元素，這對于一對一的線性的數據結構，很容易辦到，但是對于一對多的的樹結構呢？又該如何存儲呢？
樹的某個節點的孩子可能有多個，這就意味著，無論按何種順序將樹中的所有結點存儲到數組中，結點的存儲位置都無法直接反應邏輯關系。因為將數據元素挨個存儲在數組中，我們無法知道他們的關系，誰是誰的孩子，誰又是誰的雙親，完全不知道。顯然這樣存儲樹是不行的。
但是我們充分利用順序和鏈式存儲結構的特點。完全可以實現對樹的存儲結構的表示，接下來我們就會介紹三種表示方法：雙親表示法，孩子表示法，孩子兄弟表示法。
🍐1.雙親表示法
在樹的結構中，除了根結點，每一個結點不一定有孩子結點，但是都會有雙親結點，所以我們就使用雙親表示法來實現。
我們使用一段連續的空間存儲樹的結點，同時在每個結點中，一個是自己的數值域，另一個是自己雙親的下標。
由于根結點沒有雙親，我們約定根結點的雙親結點的下標為-1。
代碼實現：
#define MAX 100 typedef int TETypeData; typedef struct PTnode {TETypeData data;//自己的數據域int parent;//雙親的下標 }PTnode;typedef struct PTree {PTnode arr[MAX];int r;//根的位置int n;//結點數 }PTree;雖然這樣可以很容易表示出來樹的結構，但是如果們要知道某個結點的孩子，或者某個結點的兄弟，這樣無法表示了，所以雙親表示法是有很大弊端的。所以這個表示方法基本上是不用的。
🍍2.孩子表示法
由于一個結點可能有多個子樹，我們可以考慮多重鏈表的方式，即每個結點有多個指針域，其中每個指針指向一顆子樹的根結點，我們把這種方法叫做多重鏈表表示法。
方案一：
一種是指針域的個數就是樹的度，樹的度就是最大的那個結點的度。結構如下圖所示：
可以看出每一個結點的度是不一樣的，^就表示空的指針域，就是浪費的空間。如果每個結點的度相差很小時，這樣的結構也能充分的利用空間。那為什么我們不能按需給分配空間呢？那就有了第二種方案。
方案二：
每個結點的指針域的個數等于該結點的度，這樣就能按需給分配空間了。如下圖所示：
這個方法就減少了空間的浪費了，大大的提高了空間的利用率。但是由于各個結點的鏈表時不同的結構，加上還要維護結點的值，這就非常的麻煩了。所以接下來我們介紹孩子表示法。
具體方法：
我們把每個結點的孩子結點排列起來，以單鏈表的形式給存儲起來，則n個結點有n個孩子鏈表，如果是葉子結點則表示單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲的方式存儲到一個數組中去。
我們設置兩種結點結構，一個是表頭的結構，data存儲數值域，firstchild為頭指針域。
另一個是孩子鏈表。child存儲某個結點在表頭數組中的下標，next指向下一個孩子的指針。
具體結構如下：?
接下來是代碼的實現：
感覺是不錯了，但是還是沒辦法知道某個結點的雙親是誰，上述的表示的方法都是不完美的，總是有缺陷。接下來我們就上孩子兄弟表示法。
🍁3.孩子兄弟表示法
任意一顆樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設置兩個指針，分別指向該結點的第一個孩子和此孩子的右兄弟，我們稱為左孩子右兄弟。它的結構如下：
?
代碼實現：
typedef int TETypeData; typedef struct Tree {TETypeData data;strcut Tree* leftchild;strcut Tree* rightchild; }Tree;可以看出，結點的指針總是指向它的第一個孩子，然后第一個孩子指向它的兄弟，兄弟再指向他的兄弟，以此類推，把整個樹的結構給表示出來。這種方法雖然也不能把某個的結點的雙親表示出來，但是這個表示法把一顆復雜的樹表示為了一顆二叉樹。這就是我們后面的重點內容。
?
?
?
總結
以上是生活随笔為你收集整理的【数据结构】树的认识的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 沃丰科技GaussMind在宠物生活行业
- 下一篇： 国际象棋机器人夹断7岁男孩手指，原因是「