信息系統(tǒng)管理工程師綜合知識(shí)真題考點(diǎn)：樹(shù)與二叉樹(shù)

樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n≥1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：

每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；沒(méi)有父節(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è)不相交的子樹(shù)。

二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分。

二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根（root）的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。

葉子結(jié)點(diǎn)：一棵樹(shù)當(dāng)中沒(méi)有子結(jié)點(diǎn)（即度為0）的結(jié)點(diǎn)，簡(jiǎn)單的說(shuō)就是一個(gè)二叉樹(shù)任意一個(gè)分支上的終端節(jié)點(diǎn)。稱為葉子結(jié)點(diǎn)，簡(jiǎn)稱“葉子”。 葉子是指度為0的結(jié)點(diǎn)，又稱為終端結(jié)點(diǎn)。

考點(diǎn)相關(guān)真題

樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n≥0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。下面敘述中，（  ）不符合樹(shù)的特點(diǎn)。

(A) 對(duì)于非空樹(shù)，有且僅有一個(gè)根結(jié)點(diǎn)

(B) 除了根結(jié)點(diǎn)，樹(shù)中每個(gè)結(jié)點(diǎn)有唯一的父結(jié)點(diǎn)

(C) 樹(shù)中的每個(gè)結(jié)點(diǎn)至少要有一個(gè)孩子結(jié)點(diǎn)

(D) 樹(shù)中的每個(gè)結(jié)點(diǎn)可以有0個(gè)或多個(gè)孩子結(jié)點(diǎn)

參考答案：C

參考解析：本題考查數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)。

樹(shù)的節(jié)點(diǎn)可以沒(méi)有孩子結(jié)點(diǎn)，沒(méi)有子樹(shù)的節(jié)點(diǎn)被稱為葉子結(jié)點(diǎn)。