如何将二叉树转换为具有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