二叉樹未標記節點

可以使用3個未標記節點形成的二叉樹數量。在幾個地方二叉樹未標記節點

答案是5

但根據我的答案應該是1，因爲所有我們將使用三個節點的樹木將是同構的。

2014-02-09 sud_shan

也許你重新思考完整的樹，但一行中的三個節點也是二叉樹。 – vlad

由n個節點構成的樹數等於第n個catalan number。

更確切地說這裏是形成樹木迴歸方程： -

T(n) = sum(T(i)*T(n-1-i)) where i in (0,n-1)

例子： -

考慮5個節點的二叉樹。

保持一個爲根我們可以將其餘4成一子樹如下

（1,3），（2,2），（3,1），其中第一元組是左子樹和第二右子樹

可以進一步具有不同的安排的子樹因此： -

T（5）= T（1）* T（3）+ T（2）* T（2）+ T（ 3）* T（1）

以上方法可以推廣到上面給出的遞推關係，可以作爲加泰羅尼亞數字使用預先數學

你的例子進行評估： -

T(3) = T(1)*T(1) + T(2)*T(0) + T(0)*T(2) 

As T(2) = 2 (1 right aligned & 1 left aligned tree) and T(1) = 1 , T(0) = 1 

T(3) = 1*1 + 2*1 + 1*2 = 5

來源

2014-02-09 05:42:41

請從邏輯上解釋。 –

@ user3288929檢查我的例子 –

二叉樹未標記節點

回答

相關問題