由結點可以構造出()種不同形態的二叉樹

時間 2021-06-13 06:41:24

1樓:

14種。

公式:b[n] = c[n,2n] / (n+1)其中,組合數c[n,2n]的n為上標,2n為下標,將n=4代入公式,b[4] = c[4,8] / (4+1) = 8! / (4!

* 4! * 5) = 8*7*6/(4*3*2) = 14

所以,由4個結點可以構造出 14 種不同形態的二叉樹。

一棵深度為k,且有2^k-1個節點的二叉樹,稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中,除最後一層外,若其餘層都是滿的,並且最後一層或者是滿的,或者是在右邊缺少連續若干節點,則此二叉樹為完全二叉樹。

擴充套件資料:相關術語

樹的結點(node):包含一個資料元素及若干指向子樹的分支;

孩子結點(child node):結點的子樹的根稱為該結點的孩子;

雙親結點:b 結點是a 結點的孩子,則a結點是b 結點的雙親;

兄弟結點:同一雙親的孩子結點; 堂兄結點:同一層上結點;

祖先結點: 從根到該結點的所經分支上的所有結點;

子孫結點:以某結點為根的子樹中任一結點都稱為該結點的子孫;

結點層:根結點的層定義為1;根的孩子為第二層結點,依此類推;

樹的深度:樹中最大的結點層;

結點的度:結點子樹的個數;

樹的度: 樹中最大的結點度;

葉子結點:也叫終端結點,是度為 0 的結點;

分枝結點:度不為0的結點;

有序樹:子樹有序的樹,如:家族樹;

無序樹:不考慮子樹的順序。

2樓:油條大巴

n個節點的二叉樹有多少種形態?

公式: b[n] = c[n,2n] / (n+1)

其中, 組合數c[n,2n]的n為上標, 2n為下標

將n=4代入公式,b[4] = c[4,8] / (4+1) = 8! / (4! * 4! * 5) = 8*7*6/(4*3*2) = 14

所以,由4個結點可以構造出 14 種不同形態的二叉樹.

對於上述公式的詳細介紹,可以搜尋 [ n個節點的二叉樹有多少種形態 ]

或者,搜尋 [ catalan數 —— 卡特蘭數 ]

另外,可以驗證: 由3個結點可以構造出多少種不同形態的二叉樹?

將n=3代入公式,b[3] = c[3,6] / (3+1) = 6! / (3! * 3! * 4) = 6*5/(3*2) = 5

所以,由3個結點可以構造出5種不同形態的二叉樹.

附: 4個結點對應的14種形態的二叉樹

#     #      #       #        #

/     /      /       /        /

#     #      #       #        #

/     /      / \       \        \

#     #      #   #       #        #

/       \                  \      /

#         #                  #    #

#        #        #         #       #

\        \        \         \       \

#        #        #         #       #

\        \      / \       /       /

#        #    #   #     #       #

\      /              /         \

#    #              #           #

#        #        #        #

/ \      / \      / \      / \

#   #    #   #    #   #    #   #

/          \          /          \

#            #        #            #

3樓:阪本大佬

四個節點可以構成14種。

公式:b[n] = c[n,2n] / (n+1)

將n=4帶入上述公式,可以得出,組合數c[n,2n]的n為上標,2n為下標,將n=4代入公式,b[4] = c[4,8] / (4+1) = 8! / (4! * 4!

* 5) = 8*7*6/(4*3*2) = 14。

擴充套件資料

二叉樹不是樹的一種特殊情形,儘管其與樹有許多相似之處,但樹和二叉樹有兩個主要差別:

1、樹中結點的最大度數沒有限制,而二叉樹結點的最大度數為2;

2、樹的結點無左、右之分,而二叉樹的結點有左、右之分。

有n個結點的完全二叉樹各結點如果用順序方式儲存,則結點之間有如下關係:若i為結點編號則

如果i>1,則其父結點的編號為i/2;如果2*i<=n。

則其左孩子(即左子樹的根結點)的編號為2*i;若2*i>n,則無左孩子;如果2*i+1<=n,則其右孩子的結點編號為2*i+1;若2*i+1>n,則無右孩子。

4樓:祝濯

5種,圖例以符號表樹形,0是結點,*是佔位符沒有意義 ***0 **/*\ *0***0 ****0 ***/ **0 */ 0 **0 */ 0 *\ **0 0 *\ **0 */ 0 0 *\ **0 ***\ ****0

資料結構問題 由4個節點可以構造出多少種不同的二叉樹?

5樓:仁昌居士

由4個節點可以構造出14種不同

的二叉樹。二叉樹節點公式:b[n] = c[n,2n] / (n+1)。

二叉樹組合數c[n,2n]的n為上標,2n為下標,將n=4代入公式,可以得出,b[4] = c[4,8] / (4+1) = 8! / (4! * 4!

* 5) = 8*7*6/(4*3*2) = 14。

6樓:城興有焦卯

看了你上面的理解,你可能認為1節點和2、3、4節點不同,其實4個節點是相同的。例如:12

\\34

\\21

\\43

這兩個是相同的,因為節點是相同的!所以你上面的理解有重複出現的情況,所以才會多!

由3 個結點可以構造出多少種不同的二叉樹

7樓:千天玉斯魁

5種。看一下這裡的說明

標準表示式為f(n)

=f(n-1)f(0)

+f(n-2)f(1)

+f(n-3)f(2)

+...

+f(1)f(n-2)

+f(n-1)f(0)。

8樓:angela韓雪倩

能組成5種形態的二叉樹。

當n=1時,只有1個根節點,則只能組成1種形態的二叉樹,令n個節點可組成的二叉樹數量表示為h(n),則h(1)=1。

當n=2時,1個根節點固定,還有n-1個節點,可以作為左子樹,也可以作為右子樹,即:h(2)=h(0)*h(1)+h(1)*h(0)=2,則能組成2種形態的二叉樹。這裡h(0)表示空,所以只能算一種形態,即h(0)=1。

當n=3時,1個根節點固定,還有n-1=2個節點,可以在左子樹或右子樹,即:h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5,則能組成5種形態的二叉樹。

以此類推,當n>=2時,可組成的二叉樹數量為h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)種。

即符合catalan數的定義,可直接利用通項公式得出結果。

遞迴式:h(n)=h(n-1)*(4*n-2)/(n+1)。

該遞推關係的解為:h(n)=c(2n,n)/(n+1)(n=1,2,3,...)

由n個節點可以構造出幾個不同的二叉排序樹

9樓:卿桉軟體資源分享

你的問題實際上就是n結點能構成多少種二叉樹(一般二叉排序樹的可能形態數和二叉樹一樣)。答案是c(2n, n)/(n+1)種。

例如:4個結點有14種望採納

10樓:

catalan數 可以去查一下 很多組合數學的問題都與此相關 括號匹配 進出棧 多邊形劃分為三角形等問題

11樓:月洋晨

應該是13個吧 你可以畫出來看看

12樓:匿名使用者

n個節點能夠構bai成的不同形狀的du二叉樹的種zhi類為c(2n,n)/(n+1),其中c是指排列組合dao裡面的組合數

可以由f(0) = f(1) = 1

f(n) = f(n-1)f(0) + f(n-2)f(1) + ... + f(0)f(n-1) 推匯出來版

這裡還提到了排序權樹,但是我看不出排序在這裡有什麼作用。二叉樹的形狀定下來的話,對於指定的n個數,往裡面填的方式也就定下來了。所以答案應該是一樣的

13樓:劉旗

眼瞎嘛?說的是二叉排序樹

14樓:陽光的凌寶寶

在windows xp中的資料夾**功能,它提供了更豐富的內容比供使用者選擇原來的圖示影象資源新增

由3 個結點可以構造出多少種不同的二叉樹

15樓:渠子美莊晟

您好!如果是說結構的話,應該是5種沒錯!

如果不是5的話那麼應該abc

是二叉樹

的值問你可以構成幾個不同值的數,

這個問題的答案是12

希望對您有幫助!

1.由三個結點可以構造多少個不同的二叉樹?(原因)

16樓:桐菊汗姬

沒看到你那第二個問題,

「二叉樹根結點的層次為0」

我不明白為什麼根結點的層次會是0的呢?

根結點的層次應該是1才對的。

我那答案是層次1的。

17樓:匿名使用者

1.由三個結點可來以構造5個不同自

的二叉樹,

1個頂點,剩下2個,只有左子樹2種,只有右子樹2種,左右子樹都有1個2.二叉樹根結點的層次為0,對含有100個結點的二叉樹,可能最大樹深度和最小樹深度分別是?和 ?

解答: 最大深度,就是隻有一邊的時候,1層1個節點,有100深度。

最小深度,就是完全二叉樹的時候,除葉結點可能不滿外,其他都滿的,└log2 n┘+1 =7

這個是性質:具有n個結點的完全二叉樹的深度為 └log2 n┘+1

18樓:

1)每個節點沒有區別抄的可以構造5種

(1)滿樹 1種

(2)單子樹的4種 根 左 左;根左右;根右左;跟右右;

有區別(不同節點在不同位置算一種,

由於每種樹形有三個位置,故,每種樹形有p(3,3)種方法,安排每個節點的位置) 共有每個5*p(3,3)=5*6=30種2)含有100個結點的二叉樹,可能最大樹深度和最小樹深度分別是100 (每個節點只有一個子樹),最小深度為 log2(100-1) =7(向上取整2^6=64,2^7=128;64<100<128 )

根結點為0不算葉點的深度為最大99,最小6 算葉子結點100,7

如何判斷物質是由分子或原子或離子構

有離子構成的 看物質裡有沒有活潑金屬和非金屬,有的話,一般就是離子構成 有分子構成的 如果物質中都是非金屬,則一般是分子構成。但是其中有幾種要記住的,雖然沒有金屬,但是是有原子構成的 c sio2 sic 初三化學 怎樣判斷一個物質是由分子構成還是由原子離子構成 挑戰高度 稀有氣體 金屬 某些固態非...

細菌病毒是生命嗎,是不是也是由原子或分子構成 如是應比原子或分子大,是什麼原子或分子

細菌是單細胞生物。它的分子構成和植物動物細胞的構成沒有太大的差別,都有蛋白質和核酸還有各種代謝產物。基本上也都是c h o n p s k na cl ca.等等元素構成。病毒比較特殊,關於它是不是生命還是有不同的說法的。有些人認為它有遺傳物質,能夠繁衍後代,是生物。有些人認為它是個 半生物 只有在...

鋼筋混凝土是什麼材料,混凝土是由哪些材料構成的

這是由一定規格的鋼筋為骨架,在澆灌以一定比例的水泥 沙子和卵石配比成的混凝土,而成的鋼筋混凝土結構,構件。是建築的主要原材料。主要是結構中的抗拉材料。鋼筋混凝土是指通過在混凝土中加入鋼筋鋼筋網 鋼板或纖維而構成的一種組合材料與之共同工作來改善混凝土力學性質的一種組合材料。特性混凝土是水泥 通常矽酸鹽...