java - 如何将元素列表添加到二叉搜索 TreeMap 中？

Question

我找到了很多关于如何向二叉搜索树添加元素的源代码，但我找不到以图表形式向二叉搜索树添加元素的说明。

例如，如果给我:{55, 34, 54, 2, 78, 12, 9}

您能一步步向我展示如何将其添加到 BST 中吗？

               x

         b            y
      v     g      h     t

如上面的树形图。 (这只是一个未排序的树示例或其他任何内容)

Answer 1

这是一个简单的实现(即不考虑重新平衡树)。

{34, 54, 2, 78, 12, 9}


         55 <-- root

您获取下一个元素并将其与根进行比较。如果它更大，则将其添加到右侧，否则添加到左侧。

{54, 2, 78, 12, 9}


         55 <-- root
       /
     34

您可以递归地对其他元素执行相同的操作。

{2, 78, 12, 9}


         55 <-- root
       /
     34
       \
       54

<小时/>

{78, 12, 9}


          55 <-- root
        /
      34
     /  \
   2     54

<小时/>

{12, 9}


           55 <-- root
        /        \
      34         78
    /    \
   2      54

<小时/>

{9}


          55 <-- root
        /       \
     34         78
   /     \
  2      54
   \
    12

<小时/>

          55 <-- root
        /       \
     34         78
   /     \
  2      54
   \
    12
   /
  9

如果有不清楚的地方，请告诉我。