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

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

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

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

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

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

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

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

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

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

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

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

參考答案：C

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

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