如何將二叉樹轉換爲具有O(1)額外空間的二叉搜索樹?二叉樹到二叉搜索樹(BST)
1
A
回答
5
將一個無序的二叉樹轉換成一個有序的二叉搜索樹是微不足道的,但要做的更快一點難度。
這是一個天真的實現,應該滿足您的標準,我不會描述實際採取的步驟,只是整體算法。
- 抓鬥從現有的樹隨機葉節點
- 從現有的樹
- 取消鏈接的葉節點使節點新的二叉搜索樹
- 抓住從另一個隨機葉節點所在的根目錄現有樹
- 取消與該節點從現有的樹
- 查找正確的位置,並鏈接節點,到新的二叉搜索樹
- 重複步驟4-6,直到原來的樹是空
你應該只需要幾個變量,就像你解除鏈接的葉節點的父(除非節點具有父鏈接),根節點新樹的結構和一些臨時變量,全部在你的O(1)空間標準中。
這不會產生最佳的二叉搜索樹。爲此,您需要在添加節點之前對節點進行排序,然後按照正確的順序添加它們,或者使用平衡二叉搜索樹,如紅黑樹或松樹樹。
-1
轉換二叉樹雙鏈接列表 - 可以在O(n)的就地完成 在排序使用合併排序,nlogn 轉換列表,背靠着樹 - O(n)的
簡單nlogn解。
相關問題
- 1. 二叉搜索樹bst
- 2. 二叉搜索樹(BST)
- 3. 非遞歸BST(二叉搜索樹)
- 4. 二叉搜索樹
- 5. 二叉搜索樹
- 6. 二叉搜索樹
- 7. 二叉搜索樹
- 8. 二叉搜索樹
- 9. 二叉搜索樹
- 10. 二叉搜索樹
- 11. 二叉搜索樹
- 12. 二叉樹中最大的二叉樹搜索樹
- 13. 方案二叉搜索樹
- 14. 二叉搜索樹更新
- 15. 從二叉搜索樹
- 16. 刪除二叉搜索樹
- 17. 二叉搜索樹,comparsion
- 18. 二叉搜索樹分析
- 19. 清除二叉搜索樹
- 20. 二叉搜索樹問題
- 21. 二叉搜索樹 - PrintInOrder();
- 22. 二叉搜索樹遍歷
- 23. 查找二叉搜索樹
- 24. 在二叉搜索樹
- 25. 創建二叉搜索樹
- 26. 二叉樹搜索類
- 27. 平衡二叉搜索樹
- 28. 二叉搜索樹特例
- 29. 遍歷二叉搜索樹
- 30. 二叉搜索樹問題
我假設你的原始二叉樹沒有被排序呢? – 2010-05-17 10:16:36
是否對二叉樹進行排序? – 2010-05-17 10:21:38
我認爲它不是,否則它已經符合BST的定義。 – 2010-05-17 10:25:01