計(jì)算機(jī)二級(jí)公共基礎(chǔ)專題探究——二叉樹-文庫吧資料
2025-03-31 07:50本頁面
【正文】 A【解析】本題中前序遍歷為ABDEGCFH，中序遍歷為DBGEAFHC，后序遍歷為DGEBHFCA8完全二叉樹指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。根據(jù)前序序列可知B是CD的根結(jié)點(diǎn)?！窘馕觥壳靶蛐蛄袨锳BCD，可知A為根結(jié)點(diǎn)。前序遍歷描述為：若二叉樹為空，則執(zhí)行空操作。則該二叉樹的深度為（根結(jié)點(diǎn)在第1層） （12）【解析】二叉樹中，度為0的節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1，即n2=n01，葉子節(jié)點(diǎn)即度為0，n0=1，則n2=0，總節(jié)點(diǎn)數(shù)為12=n0+n1+n2=1+n1+0，則度為1的節(jié)點(diǎn)數(shù)n1=11，故深度為12，例6：一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為 （229）【解析】二叉樹中，度為0的節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1，即n2=n01，葉子節(jié)點(diǎn)即度為0，則n2=79，總結(jié)點(diǎn)數(shù)為n0+n1+n2=80+70+79=2293在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。 【解析】度為2的結(jié)點(diǎn)為1－1＝0個(gè)，所以可以知道本題目中的二叉樹的每一個(gè)結(jié)點(diǎn)都有一個(gè)分支，所以共7個(gè)結(jié)點(diǎn)共7層，即度為7例4：某二叉樹中有15個(gè)度為1的結(jié)點(diǎn)，16個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（ 48）。2重點(diǎn)題型：二叉樹的基本性質(zhì)3：在任意一棵二叉樹中，度為0的葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個(gè)例1：某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是（6）例2：一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為（16）【解析】度為2的結(jié)點(diǎn)是5－1＝4個(gè)，所以度為1的結(jié)點(diǎn)的個(gè)數(shù)是25－5－4＝16個(gè)。二叉樹的遍歷：（一般畫個(gè)圖要你把順序?qū)懗鰜恚?）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。二叉樹的特點(diǎn)：（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1