回覆列表
  • 1 # 使用者7169188564904

    248。

    計算過程如下:

    1、根據二叉樹的性質n0 = n2 + 1,因此度為2的結點數為124-1 = 123。

    2、而完全二叉樹中度為1的結點數最多1個。

    3、因此該完全二叉最多有:124+123+1 = 248個結點。

    完全二叉樹是由滿二叉樹而引出來的。對於深度為K的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。

    1、所有的葉結點都出現在第k層或k-l層(層次最大的兩層)

    2對任一結點,如果其右子樹的最大層次為L,則其左子樹的最大層次為L或L+l。

    3、一棵二叉樹至多隻有最下面的兩層上的結點的度數可以小於2,並且最下層上的結點都集中在該層最左邊的若干位置上,則此二叉樹成為完全二叉樹,並且最下層上的結點都集中在該層最左邊的若干位置上,而在最後一層上,右邊的若干結點缺失的二叉樹,則此二叉樹成為完全二叉樹。

    擴充套件資料:

    本題的另一演算法:

    1、n=n0+n1+n2,n0=n2+1 ==>n=2n0+n1-1 ;

    2、其中在完全二叉樹中, n1或為0或者為1;

    3、要使最多結點,則n1為1, 所以得到節點n=248;

    判斷一棵樹是否是完全二叉樹的思路:

    1、如果樹為空,則直接返回錯;

    2、如果樹不為空:層序遍歷二叉樹;

    3、如果一個結點左右孩子都不為空,則pop該節點,將其左右孩子入佇列;

    4、如果遇到一個結點,左孩子為空,右孩子不為空,則該樹一定不是完全二叉樹;

    5、如果遇到一個結點,左孩子不為空,右孩子為空;或者左右孩子都為空;則該節點之後的佇列中的結點都為葉子節點;該樹才是完全二叉樹,否則就不是完全二叉樹;

  • 中秋節和大豐收的關聯?
  • 波音787最低機場起降等級是什麼?