二叉樹的概念以及性質(zhì)
2、二叉樹及其基本性質(zhì)
（1）什么是二叉樹
二叉樹是一種很有用的非線性結(jié)構(gòu),它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹,且分別稱為該結(jié)點(diǎn)的左子樹與右子樹.
*：根據(jù)二叉樹的概念可知,二叉樹的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹）或2（有2棵子樹）.
（2）二叉樹的基本性質(zhì)（學(xué)吧學(xué)吧獨(dú)家稿件）
性質(zhì)1 在二叉樹的第k層上,最多有 個(gè)結(jié)點(diǎn).
性質(zhì)2 深度為m的二叉樹最多有個(gè) 個(gè)結(jié)點(diǎn).
性質(zhì)3 在任意一棵二叉樹中,度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè).性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹,其深度至少為 ,其中 表示取 的整數(shù)部分.
3、滿二叉樹與完全二叉樹
滿二叉樹：除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn).
完全二叉樹：除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn).
*：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1.
下圖a表示的是滿二叉樹,下圖b表示的是完全二叉樹：
完全二叉樹還具有如下兩個(gè)特性：
性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 .
性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn),如果從根結(jié)點(diǎn)開始,按層序（每一層從左到右）用自然數(shù)1,2,…,n給結(jié)點(diǎn)進(jìn)行編號,則對于編號為k（k=1,2,…,n）的結(jié)點(diǎn)有以下結(jié)論：
若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn),它沒有父結(jié)點(diǎn)；若k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號為INT(k/2).