1.有關樹的術語

? ? ? ? 1.結點

? ? ? ? ? ? ? ? 和鏈表類似，樹存儲結構中也將存儲的各個元素稱為“結點”。

? ? ? ? ? ? ? ? 對于樹中某些特殊位置的結點，還可以進行更細致的劃分，比如：

? ? ? ? ? ? ? ? 父結點（雙親結點）、孩子結點和兄弟結點：

? ? ? ? ? ? ? ? ? ? ? ? 樹根結點（簡稱“根節點”）：特指樹中沒有雙親（父親）的結點，一棵樹有且僅有一個跟結點。

? ? ? ? ? ? ? ? ? ? ? ? 葉子結點（簡稱“葉節點”）：特指樹中沒有孩子的結點，一棵樹可以有多個葉子結點。

? ? ? ? 2.子樹

? ? ? ? ? ? ? ? 通常我們將一棵樹中的幾個結點構成的“小樹”稱為這棵樹的“子樹”。

? ? ? ? ? ? ? ? 樹也可以這樣定義：樹是由根節點和若干棵子樹構成的。

? ? ? ? ? ? ? ? 注意：單個結點也可以看作是一棵樹，該節點即為根節點。

? ? ? ? 3.結點的度

? ? ? ? ? ? ? ? ?一個結點擁有有子樹的個數，就稱為該節點的度。

? ? ? ? ? ? ? ? 比較一棵樹中所有結點的度，最大的度即為整棵樹的度。

? ? ? ? 4.結點的層次

? ? ? ? ? ? ? ? 從一課數的樹根開始，樹根所在層為第一層，根的孩子結點所在的層為第二層，依次類推。樹中結點層次的最大值，稱為這棵樹的深度或者高度。

? ? ? ? 5.有序樹和無序數

? ? ? ? ? ? ? ? 如果一棵樹中，各個結點左子樹和右子樹的位置不能交換，那么這棵樹就稱為有序樹。反之，如果樹中結點的左、右子樹可以互換，那么這棵樹就是一顆無序樹。

? ? ? ? ? ? ? ? 在有序樹中，結點最左邊的子樹稱為“第一個孩子”，最右邊的稱為“最后一個孩子”。

? ? ? ? 6.森林

? ? ? ? ? ? ? ? 由m (m >= 0)個互不相交的數組成的集合就稱為森林。

? ? ? ? ? ? ? ? 前面講到，數可以理解為是由根結點和若干子樹構成的，而這若干子樹本身就是一個森林，因此樹還可以理解為是由根結點和森林組成的。

? ? ? ? ?7.空樹

? ? ? ? ? ? ? ? 空樹指的是沒有任何結點的樹，連根結點都沒有。

? ? 總結：樹是一種非線性存儲結構，通常用來存儲邏輯關系為“一對多”的數據。

? ? ? ? ? ? ? ? 使用樹結構存儲的各個結點，他們之前的關系類似于家譜中的成員關系，比如有父子關系、兄弟關系、表兄弟關系等。

2.二叉樹

? ? ? ? 滿足以下兩個條件的數就是二叉樹：

? ? ? ? ? ? ? ? 1.本身是有序樹；

? ? ? ? ? ? ? ? 2.2樹中包含的各個節點的度不能超過 2，即只能是 0、1 或者 2；

二叉樹具有以下幾個性質：

????????1. 二叉樹中，第 i 層最多有 2i-1 個結點。

????????2. 如果二叉樹的深度為 K，那么此二叉樹最多有 2K-1 個結點。

????????3. 二叉樹中，終端結點數（葉子結點數）為 n0，度為 2 的結點數為 n2，則 n0=n2+1。?

????????二叉樹還可以繼續分類，衍生出滿二叉樹和完全二叉樹。

滿二叉樹

????????如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。

???????? 滿二叉樹除了滿足普通二叉樹的性質，還具有以下性質：

????????????????1. 滿二叉樹中第 i 層的節點數為 2i-1 個。

????????????????2. 深度為 k 的滿二叉樹必有 2k-1 個節點 ，葉子數為 2k-1。

????????????????3. 滿二叉樹中不存在度為 1 的節點，每一個分支點中都兩棵深度相同的子樹，且葉子節點都在最底 層。 4. 具有 n 個節點的滿二叉樹的深度為 log2(n+1)。

完全二叉樹

????????如果二叉樹中除去最后一層節點為滿二叉樹，且最后一層的結點依次從左到右分布，則此二

叉樹被稱為 完全二叉樹。

完全二叉樹除了具有普通二叉樹的性質，它自身也具有一些獨特的性質，比如說，n 個結點的完全

二叉 樹的深度為 ?log2n?+1。 對于任意一個完全二叉樹來說，如果將含有的結點按照層次從左到右

依次標號，對于任意一個結點 i ， 完全二叉樹還有以下幾個結論成立：

???????????????? 1. 當 i>1 時，父親結點為結點 [i/2] 。（i=1 時，表示的是根結點，無父親結點）

?????????????????2. 如果 2i>n（總結點的個數） ，則結點 i 肯定沒有左孩子（為葉子結點）；否則其左孩子是結點 2i 。

????????????????3. 如果 2i+1>n ，則結點 i 肯定沒有右孩子；否則右孩子是結點 2i+1 。

總結

以上是生活随笔為你收集整理的【数据结构】树 有关树的认识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。