二叉樹(shù)筆試題總結(jié)
基本性質(zhì)相關(guān)
基本性質(zhì)
性質(zhì) 1 在二叉樹(shù)的第 層上至多有 個(gè)結(jié)點(diǎn)。
性質(zhì) 2 深度為 的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)。
性質(zhì) 3 對(duì)任何一棵二叉樹(shù) ，如果其終端結(jié)點(diǎn)數(shù)為 ，度為 2 的結(jié)點(diǎn)數(shù)為 ，則 。
性質(zhì) 4 具有 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為
常考題
完全二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)
一棵完全二叉樹(shù)上有 1001 個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是？
利用性質(zhì) 3，可以知道
對(duì)于該題，因?yàn)榻Y(jié)點(diǎn)數(shù)為奇數(shù)，因此 ，所以有 。因此，。
二叉樹(shù)的高/深度
一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹(shù)的高 為？
利用性質(zhì) 4，可以知道若該二叉樹(shù)最小深度（盡量為“滿”的二叉樹(shù)）為 ，同時(shí)也可以每個(gè)結(jié)點(diǎn)都只有一個(gè)孩子，因此也可以為 1025，結(jié)果為 11~1025 之間。
樹(shù)的葉子結(jié)點(diǎn)數(shù)
在一棵度為 4 的樹(shù) T 中，如有 20 個(gè)度為 4 的結(jié)點(diǎn)，10 個(gè)度為 3 的結(jié)點(diǎn)，1 個(gè)度為 2 的結(jié)點(diǎn)，10 個(gè)度為 1 的結(jié)點(diǎn)，則樹(shù) T 的葉結(jié)點(diǎn)個(gè)數(shù)是？
因此該題
遍歷相關(guān)
遍歷
二叉樹(shù)的遍歷有先序遍歷、中序遍歷、后序遍歷三種。二叉樹(shù)是遞歸定義的，因此二叉樹(shù)的遍歷也是遞歸的。這里的先、中、后是指根的先中后，即先遍歷根、中間遍歷根、最后遍歷根的意思！
先序遍歷二叉樹(shù)的操作定義如下：
若二叉樹(shù)為空，則空操作；否則
(1) 訪問(wèn)根結(jié)點(diǎn)；
(2) 先序遍歷左子樹(shù)；
(3) 先序遍歷右子樹(shù)。
中序遍歷二叉樹(shù)的操作定義如下：
若二叉樹(shù)為空，則空操作；否則
(1) 中序遍歷左子樹(shù)；
- 訪問(wèn)根結(jié)點(diǎn)；
(3) 中序遍歷右子樹(shù)。
后序遍歷二叉樹(shù)的操作定義如下：
若二叉樹(shù)為空，則空操作；否則
(1) 后序遍歷左子樹(shù)；
(2) 后序遍歷右子樹(shù)；
(3) 訪問(wèn)根結(jié)點(diǎn)。
常考題：根據(jù)遍歷序列確定二叉樹(shù)
由二叉樹(shù)的先序序列和中序序列，或由其后序序列和中序序列可以唯一確定一棵二叉樹(shù)。
由先序序列和中序序列確認(rèn)二叉樹(shù)
先序序列第一個(gè)結(jié)點(diǎn)一定是二叉樹(shù)的根結(jié)點(diǎn)，在中序序列中找到根結(jié)點(diǎn)，其左邊為左子樹(shù)子孫，右邊為右子樹(shù)子孫；
遞歸遞歸遞歸。
由后序序列和中序序列確認(rèn)二叉樹(shù)
后序序列的最后一個(gè)結(jié)點(diǎn)一定是二叉樹(shù)的根結(jié)點(diǎn)，在中序序列中找到根結(jié)點(diǎn)，其左邊為左子樹(shù)子孫，右邊為右子樹(shù)子孫；
遞歸遞歸遞歸。