代表免費樹到二叉樹

這個練習是從書"algorithms in c++"。假設有這樣一棵免費樹代表免費樹到二叉樹

第一個問題：我們能否將這個自由樹表示爲二叉樹？

我認爲我們不能將這個自由樹表示爲二叉樹，因爲有一些節點有兩個以上的子節點。

第二個問題：我們可以用這棵免費樹表示多少有序樹？

我不明白這個問題。節點中沒有鍵來決定如何創建一個有序的樹。

2016-12-25 Dimitris Dimitriadis

可以代表具有任意數量的每個子節點爲[左孩子右兄弟二叉樹]樹（https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree）。因此，有多於兩個孩子的節點的存在不是拒絕二叉樹作爲你的自由樹的表示的理由。 –

我相信第二個問題是問自己從自由樹開始可以創建多少棵不同的樹，然後向邊添加一個方向性，使得生成的樹是一棵定向的根樹。 – templatetypedef

非常感謝您的回答。我不知道左子右兄弟二叉樹。對於第二個問題，我必須創建有序樹而不是無序樹（根樹）。 –

如果我正確地理解了這個問題，那麼任務就是將樹表示爲二叉樹，即使用二叉樹的數據結構來表示任意樹。從結構上講，這個問題需要一種將任意樹映射到二叉樹的方法。

該技術被描述爲here;基本思想是通過任意選擇的子女來代表節點a的子節點c_1,...c_n，子節點a可以是兩個以上，該子節點成爲a的左子節點。作爲c_1的右邊孩子，下一個孩子c_2被存儲;等等。這意味着對於每個節點，一個孩子存儲在左側子樹中，而在右側子樹中通過總是選擇正確的孩子，存儲孩子的「替代方案」的「兄弟姐妹」。該方法可以描繪如下。請忍受我的相對較差的文字表示。

arbitrary tree 

     a 
/| | \ 
c_1 c_2 c_3 c-4 

binary tree 

    a 
/
c_1 
    \ 
    c_2 
     \ 
     c_3 
      \ 
      c_4

來源

2016-12-25 21:35:36 Codor

謝謝你的回答。 –

代表免費樹到二叉樹

回答

相關問題