• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            加文

            在這個世界上取得成就的人,都努力去尋找他們想要的機會,如果找不到機會,他們便自己創造機會。 -- 蕭伯納
            隨筆 - 14, 文章 - 56, 評論 - 1, 引用 - 0
            數據加載中……

            1. 與樹有關的概念

            1) 結點的度:結點擁有的子樹數。

            2) 樹的度:樹中所有結點的度的最大值。

            3) 結點的層數:

            4) 樹的深度:樹中結點的最大層數或者稱為樹的高度或者深度。

            5) 葉子結點:度為0的點或者終端節點。

            6) 分支結點:度大于0的結點。

            7) 森林:m棵互不相交的樹的集合為森林

            8) 樹不允許為空。但是二叉樹允許為空,二叉樹不是樹,并且二叉樹是有序樹,左孩子和右孩子是不一樣的。

            2. 二叉樹概念:有限個元素的集合,該集合或者為空、或者有一個稱為根的元素以及兩兩不相交的、分別稱為左子樹和右子樹的組成。

            1) 二叉樹的性質如下:

            ① 二叉樹的第i層,共有2^(i-1)個結點。

            ② 深度為k二叉樹最多有2^k-1個結點。

            ③ 二叉樹中,終端節點的數目為n0;度為1的結點數目為n1,度為2的結點為n2;則n0 = n2+1;

                據此,可以引出一下結論,對于n個結點的完全二叉樹:

            a>,若n為奇數,則樹中只有度為2和度為0的結點。其中度為2的結點數為  (n-1)/2;度為0的結點數為(n-1)/2+1;

            b>,若n為偶數,則樹中除了度為2和度為0的結點結點外,還有度為1的結點1個。

            ④ 如果有一棵n個結點的完全二叉樹,自上自下,同一層自左到右連續給結點編號,則有如下關系:

            a>,若i=1,則結點為i為根結點,若i>1,則結點i的父節點為『i/2』;

            b>,若2i<n,則結點i的左孩子結點為2i;

            c>,若2i+1<n;則結點i的右孩子結點為2i+1;

            d>,若結點i為奇數,則左子樹結點為i-1;

            e>,若結點i為偶數,則右子樹結點為i+1;

            f>,結點i所在的層次為log2i+1;

            由此可以引入如下結論:對于完全二叉樹編號為i的結點有:

            1>,若i<=n/2,則編號為i的結點為分支結點,否則為葉結點

            2>,若n為奇數,則每個分支結點都有左子樹和右子樹;若n為偶數,則編號最大的分支結點只有左子樹。

            ⑤  具有n個結點的完全二叉樹的深度為log2(n+1)(向上取整)

            2) 二叉樹的存儲結構

            ① 二叉樹的順序存儲結構一般適用于完全二叉樹。

            ② 二叉樹的鏈式存儲結構,有二叉鏈表和三叉鏈表。

            3) 二叉樹的遍歷 

            ① 中序遞歸遍歷

            ② 先序遞歸遍歷

            ③ 后序遞歸遍歷

            ④ 中序非遞歸

            ⑤ 后序非遞歸

            ⑥ 先序非遞歸

            ⑦ 層次遍歷

                 4) 線索二叉樹

            3. 樹與森林

            1) 樹的存儲結構

            2) 森林,樹與二叉樹的轉換

            3) 森林與樹的遍歷

            4. 樹的應用

            1) 二叉排序樹

            2) 平衡二叉樹

            3) 哈夫曼樹

            4) 

             

            posted on 2011-10-22 21:30 chxzwj 閱讀(332) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構

            亚洲国产精久久久久久久| 伊人久久综在合线亚洲2019 | 久久99精品国产99久久6| 天天久久狠狠色综合| 久久亚洲色一区二区三区| 久久亚洲精品国产亚洲老地址 | 日韩一区二区久久久久久 | 久久99热只有频精品8| 无码人妻久久一区二区三区蜜桃| 97久久国产露脸精品国产| 精品永久久福利一区二区| 青青青青久久精品国产h| 久久99国产精品久久99小说 | 99久久国产综合精品五月天喷水| 久久九色综合九色99伊人| 久久国产高清字幕中文| 国产偷久久久精品专区 | 久久国产精品一区二区| 思思久久99热免费精品6| 久久精品视频网| 麻豆成人久久精品二区三区免费| 久久综合九色综合久99| 国内精品久久久久伊人av| 色婷婷综合久久久久中文字幕| 国产69精品久久久久777| 91久久精品91久久性色| 国产香蕉久久精品综合网| 久久国产热这里只有精品| 国产精品一久久香蕉国产线看| 久久只有这精品99| 69SEX久久精品国产麻豆| 成人综合久久精品色婷婷| 久久久精品久久久久久 | 波多野结衣AV无码久久一区| 国产免费久久精品99久久| 色偷偷888欧美精品久久久| 色欲av伊人久久大香线蕉影院| 亚洲AV无码久久精品狠狠爱浪潮| 久久久久综合中文字幕| 久久99精品久久久久久野外| 欧美日韩中文字幕久久伊人|