腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

軟件下載

android MAC 驅(qū)動下載字體下載 DLL

源碼下載

PHP ASP.NET ASP JSP

軟件編程

C# JAVA C 語言 Delphi Android

網(wǎng)絡(luò)編程

PHP ASP.NET ASP JavaScript

在線工具

CSS格式化 JS格式化 Html轉(zhuǎn)化為Js

數(shù)據(jù)庫

MYSQL MSSQL oracle DB2 MARIADB

CMS

PHPCMS DEDECMS 帝國CMS WordPress

常用工具

PHP開發(fā)工具 python Photoshop 必備軟件

C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹

更新時(shí)間：2022年02月24日 16:17:56 作者：檸檬葉子C

在上一章中我們正式開啟了對數(shù)據(jù)結(jié)構(gòu)中樹的講解，介紹了樹的基礎(chǔ)。本章我們將學(xué)習(xí)二叉樹的概念，介紹滿二叉樹和完全二叉樹的定義，并對二叉樹的基本性質(zhì)進(jìn)行一個(gè)簡單的介紹。本章附帶課后練習(xí)

?? 鏈接：C語言數(shù)據(jù)結(jié)構(gòu)系列之樹的概念結(jié)構(gòu)和常見表示方法

0x00 概念

?? 定義：二叉樹既然叫二叉樹，顧名思義即度最大為2的樹稱為二叉樹。它的度可以為 1 也可以為 0，但是度最大為 2 。

?? 一顆二叉樹是節(jié)點(diǎn)的一個(gè)有限集合，該集合：

① 由一個(gè)根節(jié)點(diǎn)加上兩顆被稱為左子樹和右子樹的二叉樹組成

② 或者為空

?? 觀察上圖我們可以得出如下結(jié)論：

① 二叉樹不存在度大于 2 的節(jié)點(diǎn)，換言之二叉樹最多也只能有兩個(gè)孩子。

② 二叉樹的子樹有左右之分，分別為左孩子和右孩子。次序不可顛倒，因此二叉樹是有序樹。

?? 注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

0x01 滿二叉樹

?? 定義：一個(gè)二叉樹，如果每一層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值（均為2），則這個(gè)二叉樹就可以被稱作為 "滿二叉樹" 。

?? 換言之，如果一個(gè)二叉樹的層數(shù)為 $h$ ，且節(jié)點(diǎn)總數(shù)是 $2^h - 1$ ，則他就是一個(gè)滿二叉樹。

?? 計(jì)算公式：

① 已知層數(shù)求總數(shù)： $N = 2^h-1$

② 已知總數(shù)求層數(shù)： $h = log_2(N+1)$

? 十億個(gè)節(jié)點(diǎn)，滿二叉樹是多少層？

?? $2^3^0$ ≈ 10億多

0x02 完全二叉樹

?? 定義：對于深度為 $K$ 的，有 $n$ 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 $K$ 的滿二叉樹中編號從 1 至 $n$ 的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。

?? 前 $h - 1$ 層是滿的，最后一層不滿，但是最后一層從左到右是連續(xù)的。

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。所以，滿二叉樹是一種特殊的完全二叉樹（每一層節(jié)點(diǎn)均為2）。

?? 常識：

① 完全二叉樹中，度為 1 的最多只有 1 個(gè)。

② 高度為 $h$ 的完全二叉樹節(jié)點(diǎn)范圍是 $[ 2^{h-1} - 1 + 1, 2^{h} - 1 ]$

0x03 二叉樹的性質(zhì)

?? 四點(diǎn)規(guī)則：

① 若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則一顆非空二叉樹的第 $i$ 層上最多有 $2^{(i-1)}$ 個(gè)節(jié)點(diǎn)。

② 若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1 ，則深度為 $K$ 的二叉樹最大節(jié)點(diǎn)數(shù)是 $2^h-1$ .

③ 對任何一顆二叉樹，如果度為 0 其葉子結(jié)點(diǎn)個(gè)數(shù)為 $n_0$ ，度為 2 的分支節(jié)點(diǎn)個(gè)數(shù)為 $n_2$ ，則有 $n_0 = n_2 + 1$ 。換言之，度為 0 的永遠(yuǎn)比度為 2 的多一個(gè)葉子結(jié)點(diǎn)。