一、定義

二叉樹可以用以下方式詳細(xì)定義：

• 二叉樹是由節(jié)點(diǎn)構(gòu)成的樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多可以有兩個(gè)子節(jié)點(diǎn)。
• 每個(gè)節(jié)點(diǎn)有以下幾個(gè)屬性：
  • 值：存儲(chǔ)該節(jié)點(diǎn)的數(shù)據(jù)。
  • 左子節(jié)點(diǎn)：有一個(gè)左子節(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)。
• 葉子節(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)數(shù)量可以為0，1或多個(gè)，空的二叉樹也是一棵有效的二叉樹。

二、幾種特殊的二叉樹

1、滿二叉樹，一個(gè)高度為h含有個(gè)結(jié)點(diǎn)的二叉樹

特點(diǎn)：

1.只有最后一層有葉子結(jié)點(diǎn)。

2.不存在度為1的結(jié)點(diǎn)。

3.按層序從1開始編號(hào)，結(jié)點(diǎn)i的左孩子為2i，右孩子為2i+1，父結(jié)點(diǎn)為。

?2、完全二叉樹，與同高的滿二叉樹的子節(jié)點(diǎn)編號(hào)一致

此圖的4層的編號(hào)與上圖的第4層一一對(duì)應(yīng)，稱之為完全二叉樹。

特點(diǎn)：

1.只有最后兩層有葉子結(jié)點(diǎn)。

2.最多存在一個(gè)度為1的結(jié)點(diǎn)。

3.按層序從1開始編號(hào)，結(jié)點(diǎn)i的左孩子為2i，右孩子為2i+1，父結(jié)點(diǎn)為。

4.i<=為分支結(jié)點(diǎn)，i>=為葉子節(jié)點(diǎn)。

?3.二叉排序樹

一棵二叉樹或者是空二叉樹，或者是具有如下性質(zhì)的二叉樹:

左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字;
右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字。

左子樹和右子樹又各是一棵二叉排序樹。

?4.平衡二叉樹，樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1

?三、考點(diǎn)

常見考點(diǎn)1:

設(shè)非空二叉樹中度為0、1和2的結(jié)點(diǎn)個(gè)數(shù)分別為n0、n1,和n2，則n0= n2+1

★★★★★(葉子結(jié)點(diǎn)比二分支結(jié)點(diǎn)多一個(gè))

常見考點(diǎn)2:

二叉樹第i層至多有個(gè)結(jié)點(diǎn)（ i≥1)
m叉樹第i層至多有個(gè)結(jié)點(diǎn)（( i≥1)

常見考點(diǎn)3:

高度為h的二叉樹至多有個(gè)結(jié)點(diǎn)（滿二叉樹)

常見考點(diǎn)4:

具有n個(gè)(n>0）結(jié)點(diǎn)的完全二叉樹的高度h為或

常見考點(diǎn)5：

?

?