我如何合併兩棵二叉樹

我有兩棵二叉樹，我想合併它們。我的第一個問題是，我們是否可以合併兩個二叉樹，如果是的話，我可以如何有效地執行合併操作，以及我可以執行合併操作的各種方法有哪些。 ..？我如何合併兩棵二叉樹

合併二叉樹非常簡單，只需將一個二叉樹的根鏈接爲另一個葉子節點的子節點。你是否有其他想要保存的結構，例如被命令或平衡？ – JGWeissman

讓我們從簡單的無序不平衡樹開始。你說這是微不足道的，所以你可以告訴我它是如何完成的。？ –

2011-08-22 19:40:56

1）將兩個樹平鋪到排序列表中。
2）合併列表你在1 GOT）
3）構造樹出了什麼你2了）

2011-08-22 19:26:40 hari

有沒有複雜性？ –

您可以使用標準的有序步行將樹木平鋪到O（n）時間的列表中。合併兩個排序列表也可以在O（n）時間完成。一旦你合併了列表，你可以在O（n）時間內構建BST，方法是遞歸構造左右兩半的樹，然後將它們粘合在一起。因此整體的複雜性是O（n）。 – templatetypedef

@templatetypedef：謝謝你的回答。是的，複雜性是O（n）。 – hari

This算法可以幫助你。

2011-08-22 19:29:00

與樹木無關。 – SLaks

@SLaks是的。既然我們知道他們是BST，我們可以將這些樹排列成一個排序列表。一旦我們有了2個排序列表，這個算法就適用了。 –

效率討論創建一個新的節點，並在其中一棵樹的頭指向一個尾巴，在其他樹的頭點其它的尾巴。也許你需要澄清你的問題是更具體。你想保留什麼樣的關係？

2011-08-23 07:31:11 jones

樹也是一個圖，所以輸出每棵樹的邊緣頂點對（u，v），然後將這些邊集合合併，並輸出結果圖。

問題在於如何將一棵樹中的頂點映射到另一棵樹頂點（例如，我們在樹1中有邊對（5,9），在樹2中有邊對（5,6），這些5s對應於相同的頂點？）。

使用頂點編號（也許它將數字賦給不完整的二叉樹中的每個頂點，就好像它是一個完整的二叉樹一樣，換句話說就是將任何部分二叉樹中的頂點賦給一個假設該樹是子樹的完整二叉樹），以某種方式提供理想的等價性是有效的。

2015-05-29 03:29:38 user2530580

回答