我在解释有关将元素插入二叉搜索树的某个问题时遇到了麻烦 . 我熟悉预订,后序和顺序遍历,但我不熟悉以下问题:
假设我们按顺序将元素3,5,6,1,2,4,7插入到最初为空的二进制搜索树中 .
如果我只给出了一组按顺序插入的数字,我该如何将它变成二进制搜索树? 3会成为根吗?我会自己 balancer 其他数字到正确的子树吗?在这种情况下难道不会有很多解释吗?是否遵循某种惯例?
谢谢 .
向树中添加项时,不会重新排序现有树 . 新项目仅添加到叶节点 . 这意味着当您第一次添加3时,3将是结果的根节点 . 当你添加5时,它将在3的右边,等等 . 这导致以下树:
3 / \ 1 5 \ / \ 2 4 6 \ 7
如果没有关于如何 balancer 树的规则的任何进一步信息,我将不得不假设它指的是一个“天真的”不 balancer 树 .
所以这:
3 /-----/ \-----\ 1 5 \--\ /--/ \--\ 2 4 6 \-\ 7
是的,3将是根,因为在第一次插入后,整个树只有一个元素 . 保持相同的逻辑,if(number,left,right)表示您获得的节点:
(3 ,,)
(3 ,,(5 ,,))
(3 ,,(5 ,,(6 ,,)))
(3,(1 ,,),(5 ,,(6 ,,)))
(3,(1,,2),(5 ,,(6 ,,)))
(3,(1,,2),(5,(4 ,,),(6 ,,)))
(3,(1,,2),(5,(4 ,,),(6,,7)))
3 回答
向树中添加项时,不会重新排序现有树 . 新项目仅添加到叶节点 . 这意味着当您第一次添加3时,3将是结果的根节点 . 当你添加5时,它将在3的右边,等等 . 这导致以下树:
如果没有关于如何 balancer 树的规则的任何进一步信息,我将不得不假设它指的是一个“天真的”不 balancer 树 .
所以这:
是的,3将是根,因为在第一次插入后,整个树只有一个元素 . 保持相同的逻辑,if(number,left,right)表示您获得的节点:
(3 ,,)
(3 ,,(5 ,,))
(3 ,,(5 ,,(6 ,,)))
(3,(1 ,,),(5 ,,(6 ,,)))
(3,(1,,2),(5 ,,(6 ,,)))
(3,(1,,2),(5,(4 ,,),(6 ,,)))
(3,(1,,2),(5,(4 ,,),(6,,7)))