• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      CSP真題——二叉樹(shù)

      2022-09-28 05:31:07高大力
      電腦報(bào) 2022年37期
      關(guān)鍵詞:左向右子樹(shù)二叉樹(shù)

      高大力

      CCF推出CSP認(rèn)證(Certified Softwmare Professional, 軟件能力認(rèn)證),以評(píng)價(jià)計(jì)算機(jī)專(zhuān)業(yè)人士或準(zhǔn)專(zhuān)業(yè)人士計(jì)算機(jī)科學(xué)的基礎(chǔ)能力——算法和編程能力。CSP已成為一些企業(yè)及許多大學(xué)評(píng)價(jià)計(jì)算機(jī)專(zhuān)業(yè)大學(xué)生專(zhuān)業(yè)能力的重要工具。

      這是CSP2021初賽的一道選擇題,涉及知識(shí)點(diǎn)為二叉樹(shù)形態(tài)。

      如果一棵二叉樹(shù)只有根結(jié)點(diǎn),那么這棵二叉樹(shù)高度為1。請(qǐng)問(wèn)高度為5的完全二叉樹(shù)有()種不同的形態(tài)?

      A. 16

      B. 15

      C. 17

      D. 32

      二叉樹(shù)(Binary tree)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。二叉樹(shù)特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹(shù),通常子樹(shù)被稱(chēng)作“左子樹(shù)”(left subtree)和“右子樹(shù)”(right subtree),且左右次序不能顛倒。二叉樹(shù)的第i層至多有2^(i-1)個(gè)結(jié)點(diǎn);深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn);深度為k,有n個(gè)節(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中,序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí),稱(chēng)之為完全二叉樹(shù)。

      滿二叉樹(shù)的特點(diǎn)在于“滿”,即每層的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。

      完全二叉樹(shù)是相對(duì)于滿二叉樹(shù)來(lái)說(shuō)的。二叉樹(shù)是有序樹(shù),對(duì)一棵滿二叉樹(shù)和一棵完全二叉樹(shù)按“自上向下,自左向右”的順序進(jìn)行編號(hào)。完全二叉樹(shù)中的所有結(jié)點(diǎn)的編號(hào)必須和滿二叉樹(shù)的相同編號(hào)的結(jié)點(diǎn)在位置上完全相同。換句話說(shuō),完全二叉樹(shù)的結(jié)點(diǎn)按“自上向下,自左向右”的順序不能中斷。T3 的結(jié)點(diǎn)C 沒(méi)有左葉子,顯然按那個(gè)順序是中斷的。

      回到本題,高度為5的完全二叉樹(shù),在第5層至多有2^(5-1)=16個(gè)節(jié)點(diǎn),從1個(gè)節(jié)點(diǎn)到16個(gè)節(jié)點(diǎn),可以至多有16種形態(tài)。

      猜你喜歡
      左向右子樹(shù)二叉樹(shù)
      黑莓子樹(shù)與烏鶇鳥(niǎo)
      一種新的快速挖掘頻繁子樹(shù)算法
      理想當(dāng)燃
      二叉樹(shù)創(chuàng)建方法
      書(shū)本圖的BC-子樹(shù)計(jì)數(shù)及漸進(jìn)密度特性分析?
      向左向右扭一扭
      日常問(wèn)候用語(yǔ)?《尼山薩滿傳》節(jié)選
      基于覆蓋模式的頻繁子樹(shù)挖掘方法
      一種由層次遍歷和其它遍歷構(gòu)造二叉樹(shù)的新算法
      偏方治療面部神經(jīng)麻痹
      二手房| 宁城县| 玉溪市| 抚顺市| 惠东县| 灵寿县| 于都县| 乌拉特中旗| 长沙县| 浪卡子县| 七台河市| 宁强县| 中卫市| 兴和县| 秦安县| 赤峰市| 濉溪县| 胶州市| 和平区| 靖州| 镇安县| 清丰县| 鄂托克前旗| 洛浦县| 桐城市| 图们市| 平南县| 格尔木市| 白河县| 北安市| 屏边| 松溪县| 盐池县| 巍山| 繁峙县| 东阳市| 济宁市| 嘉善县| 怀仁县| 汉寿县| 台南县|