具有結點的二叉樹可有多少種形態,具有四個結點的二叉樹可有多少種形態

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

1樓:幻雪狼狐

根據 卡特蘭數 公式:

f(n)= (2*n)! / (n! * (n+1)!),!為階乘。

所以 f(4) = 14。

具有4個節點的二叉樹有14中形態。

2樓:

設具有n個節點的二叉樹的形態有f(n)種,則f(0)=0,f(1)=1

具有四個節點的二叉樹,包含一個根節點與3個子節點,可以分以下幾類:

左子樹0個節點,右子樹3個節點,此時二叉樹的形態有f(0)+f(3)左子樹1個節點,右子樹2個節點,此時二叉樹的形態有f(1)+f(2)左子樹2個節點,右子樹1個節點,此時二叉樹的形態有f(2)+f(1)左子樹3個節點,右子樹0個節點,此時二叉樹的形態有f(3)+f(0)故f(4)=2f(0)+2f(1)+2f(2)+2f(3)而f(2)=2f(0)+2f(1)=2

f(3)=2f(0)+2f(1)+2f(2)=6所以f(4)=18,即具有四個節點的二叉樹有18種。

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

3樓:

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的結點;

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

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

4樓:油條大巴

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種形態的二叉樹

#     #      #       #        #

/     /      /       /        /

#     #      #       #        #

/     /      / \       \        \

#     #      #   #       #        #

/       \                  \      /

#         #                  #    #

#        #        #         #       #

\        \        \         \       \

#        #        #         #       #

\        \      / \       /       /

#        #    #   #     #       #

\      /              /         \

#    #              #           #

#        #        #        #

/ \      / \      / \      / \

#   #    #   #    #   #    #   #

/          \          /          \

#            #        #            #

5樓:阪本大佬

四個節點可以構成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,則無右孩子。

6樓:祝濯

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

按二叉樹的定義,具有4個結點的二叉樹有( )種?

7樓:滑茗緒惜兒

結點全部在左子樹的情況:00

0000

0000

0000

0000

00共5種,同理結點都在右子樹也有5種。

結點在左右子樹的情況:00

0000

0000

0000

00共4種,所以共有14種。

8樓:匿名使用者

應該有10種吧。只有左子樹的有3種,只有右子樹的也是3種,有左右子樹的有4種。

9樓:一研為定吧

3個結點的二叉樹有5種,多增加一個根節點之後,可以有左右不同的3結點二叉樹,回所以左右分別有單個3結點子樹的答二叉樹有

2*5=10種;除此之外,3個結點可以構造成2結點子樹和單節點子樹,所有不同共有4種。

綜上,具有4個結點的二叉樹有14種。

10樓:小張你好

第一層左右都有的:4種;

兩層結構、第一層只有一側的:2種;

有三層結構的:4種;

共10種。

11樓:超級

14c(n;2n)/(n+1)

具有三個節點的二叉樹有幾種形態?哪幾種?

12樓:

要作圖的,有兩層來的,自有三層的,

兩層的有:母節點是a,a的左子節點為b,a的右子節點為c三層的有:

1、母節點是a,a的右子節點為b,b的右子節點為c2、母節點是a,a的右子節點為b,b的左子節點為c3、母節點是a,a的左子節點為b,b的右子節點為c4、母節點是a,a的左子節點為b,b的左子節點為c仔細看,分清左右,然後邊看邊做圖,一下就畫出來了

13樓:四字多一半

字母只是代號,重在節點在圖中的位置,對於兩層的,作圖只有一種結果,即深度為2層的滿二叉樹。

按照二叉樹的定義,具有三個結點的二叉樹有()種形態?

14樓:紅咲

選b5種

兩層的有一種

三層的第一層是根,第二層兩種情況,第三層兩種情況。1*2*2=4所以1+4=5種

樓上是否明白二叉樹形態……

知道 二叉樹有n個節點 求這種二叉樹有幾種形態?

15樓:假面

記n個節點的二叉樹形態個數為a[n]

1)0個節點的二叉樹只有1種形態,a[0]=0;1個節點的二叉樹只有1種形態,a[1]=1

2)n個節點(n>=2)的二叉樹有 a[n] = ∑ [m=0到n-1] ( a[m]*a[n-m-1] ) ,求和的每一項,分別表示根的左子樹為m個節點、右子樹為 n-m-1個節點的情況

剛好就是catalan數,直接用catalan數的公式:h(n)=c(2n,n)/(n+1)

擴充套件資料:

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

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

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

性質:(3) 對於任意一棵二叉樹,如果其葉結點數為n0,而度數為2的結點總數為n2,則n0=n2+1;

(5)有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,則無右孩子。

(6)給定n個節點,能構成h(n)種不同的二叉樹。

h(n)為卡特蘭數的第n項。h(n)=c(2*n,n)/(n+1)。

(7)設有i個枝點,i為所有枝點的道路長度總和,j為葉的道路長度總和j=i+2i

遍歷是對樹的一種最基本的運算,所謂遍歷二叉樹,就是按一定的規則和順序走遍二叉樹的所有結點,使每一個結點都被訪問一次,而且只被訪問一次。由於二叉樹是非線性結構,因此,樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設l、d、r分別表示遍歷左子樹、訪問根結點和遍歷右子樹, 則對一棵二叉樹的遍歷有三種情況:dlr(稱為先根次序遍歷),ldr(稱為中根次序遍歷),lrd (稱為後根次序遍歷)。

在後序線索樹中找到結點的後繼分三種情況:

1 若結點是二叉樹的根,則其後繼為空;

2 若結點是其雙親的右孩子,或是其雙親的左孩子且其雙親沒有右子樹,則其後繼即為雙親結點;

3 若結點是其雙親的左孩子,且其雙親有右子樹,則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

具有結點的完全二叉樹的深度為,具有256個結點的完全二叉樹的深度為 。

根據 二叉樹的第i層至多有2 i 1 個結點 深度為k的二叉樹至多有2 k 1個結點 根結點的深度為1 這個性質 因為2 9 1 700 2 10 1 所以這個完全二叉樹的深度是10,前9層是一個滿二叉樹,這樣的話,前九層的結點就有2 9 1 511個 而第九層的結點數是2 9 1 256 所以第十...

設一棵完全二叉樹有結點,則該完全二叉樹的深度為,有葉子結點

一杯酒蘭子 256。二叉樹 binary tree 是指樹中節點的度不大於2的有序樹,它是一種最簡單且最重要的樹。二叉樹的遞迴定義為 二叉樹是一棵空樹,或者是一棵由一個根節點和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹 左子樹和右子樹又同樣都是二叉樹 二叉樹 binary tree 是樹...

二叉樹後續線索樹的問題,後序後繼線索二叉樹中找後繼的集中情況

後序遍歷 若二叉樹非空,則依次執行如下操作 遍歷左子樹 遍歷右子樹 訪問根結點。所以從根結點開始 樹的判斷都是從根開始 如這裡的a,這裡有左右子樹b c,但是在訪問b的時候,發現b有左子樹d,所以d比b先,d有左子樹e e有右子樹f,所以f比e先,e比d先,訪問完b後,訪問c,c有右子樹g,先訪問g...