樹的概念

樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因 為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：每個(gè)結(jié)點(diǎn)有零個(gè)或多 個(gè)子結(jié)點(diǎn)；沒有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié) 點(diǎn)可以分為多個(gè)不相交的子樹

一些基本概念

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；
• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)；
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)；
• 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；
• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。

二叉樹概念

概念

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹 的二叉樹組成。

二叉樹的特點(diǎn)：

每個(gè)結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。

二叉樹的子樹有左右之分，其子樹的次序不能顛倒。

特殊的二叉樹

滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是 說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。

完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對 應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

二叉樹的性質(zhì)

非空二叉樹上葉子結(jié)點(diǎn)數(shù)等于度為 2 的結(jié)點(diǎn)數(shù)加 1 。

非空二叉樹上第 K 層上至多有2^(k-1) 個(gè)結(jié)點(diǎn)（K >= 1）。

高度為 H 的二叉樹至多有 2^H-1個(gè)結(jié)點(diǎn)。

對完全二叉樹按從上到下、從左到右的順序依次編號(hào) 1 ， 2 ， … , N ， 則有以下的關(guān)系：

• 當(dāng) i > 1 時(shí)，結(jié)點(diǎn) i 的雙親結(jié)點(diǎn)編號(hào)為 ，即當(dāng) i 為偶數(shù)時(shí)，且雙親結(jié)點(diǎn)的編號(hào)為 i / 2 ，它是雙親結(jié)點(diǎn)的左孩子；當(dāng) i 為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為 ( i -1) / 2 ，它是雙親結(jié)點(diǎn)的右孩子。
• 當(dāng) 2i <= N ，結(jié)點(diǎn) i 的左孩子編號(hào)為 2i ，否則無左孩子。
• 當(dāng) 2i + 1 <= N 時(shí)，結(jié)點(diǎn) i 的右邊的孩子為 2i + 1 ，否則無右邊的孩子。
• 結(jié)點(diǎn) i 所在的層次（深度）為 。
• 具有N 個(gè)（N>0）結(jié)點(diǎn)的完全二叉樹的高度為 或者

二叉樹的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左向右存儲(chǔ)完全二叉樹
二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為 i 的結(jié)點(diǎn)元素存儲(chǔ)在某個(gè)數(shù)組下標(biāo)為 i -1 的分量中，
然后通過一些方法確定結(jié)點(diǎn)在邏輯上的父子和兄弟關(guān)系。

依據(jù)二叉樹的性質(zhì)，“ 完全二叉樹 ” 和“ 滿二叉樹 " 采用順序存儲(chǔ)比較合適，樹中結(jié)點(diǎn)的序號(hào)可以
唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的關(guān)系。

對于一般的二叉樹，為了讓數(shù)組下標(biāo)能反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只能添加一些并不存在的空結(jié)點(diǎn)讓其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，再存儲(chǔ)到一維數(shù)組的相應(yīng)分量中。然而，在最壞的情況下，一個(gè)高度為 H 且只有 H 個(gè)結(jié)點(diǎn)的單支樹卻需要占據(jù)接近 個(gè)存儲(chǔ)單元。

二叉樹的順序存儲(chǔ)如下圖所示（其中 NO表示并不存在的空結(jié)點(diǎn)）

鏈?zhǔn)酱鎯?chǔ)

由于順序存儲(chǔ)對空間利用率較低，因此，一般二叉樹都采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)是指用一個(gè)鏈表來存儲(chǔ)一棵二叉樹，二叉樹中每一個(gè)結(jié)點(diǎn)用鏈表的一個(gè)鏈結(jié)點(diǎn)來存儲(chǔ)。在二叉樹中，結(jié)點(diǎn)結(jié)構(gòu)通常包括“ 若干數(shù)據(jù)域 ”及 “ 若干指針域 ”。二叉鏈表至少包含 3 個(gè)域：數(shù)據(jù)域 data 、左指針域 lchild 、右指針域 rchild ，如下圖所示：

總結(jié)

以上是生活随笔為你收集整理的再谈二叉树（二叉树概念，二叉树的性质，二叉树的存储结构）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。