如何将元素列表添加到二进制搜索树图中

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

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