插入BST

我想要创建BST的可视化，但每插入7个或更少的值后，我在网上找到的每个示例都会停止。假设我正在执行以下序列：插入BST

insert（5），insert（7），insert（9），insert（8），insert（3），insert（2），insert（4），insert （6），插入件（10）。

直到衬套（6），我结束了：

我的主要问题是：我在哪里何去何从？添加到我最左边的叶子还是添加到我的“最低”叶子？

另外：根据维基百科的插入的代码是：

void insert(Node* node, int value) { 
    if (value < node->key) { 
     if (node->leftChild == NULL) 
      node->leftChild = new Node(value); 
     else 
      insert(node->leftChild, value); 
    } else { 
     if(node->rightChild == NULL) 
      node->rightChild = new Node(value); 
     else 
      insert(node->rightChild, value); 
    } 
}

但根据这一点，一旦我在8，我得到插入（3），这将增加3至左8，因为它将比较3与节点9，看到小于点已经被8取代，然后重新运行插入，其中8是节点，并且将3放置为8的左侧子节点。但是，这个只会创建一个列表。

谢谢。

来源

2013-10-08 Will Nasby

事实上，它将是4的左边孩子。 –

你需要允许重复的值吗？如果是这样，考虑为每个节点添加一个计数器，以跟踪该值的出现次数，而不是在您的树中有多个具有该值的“节点”。 – fvrghl

什么似乎误导你是每个插入，你必须从根（在你的情况，是5）开始。所以，让我们上图，并尝试将3你粘贴的算法如下：

3 < 5, we go left and we meet 3 
3 == 3, we go right (here it's the same, the code above says "go right") and we meet 4 
3 < 4, we go left. Since 4 has no left child, 3 becomes its left child.

尝试使用上述算法从零建立自己的树。顺便说一下，你不会发现n> 10个节点的很多例子，因为它们往往会非常长，对读者没有任何好处。

来源

2013-10-08 22:39:03

回答

相关问题