添加並生成二叉查找樹

Question

我在查找如何向二叉搜索樹中添加或插入節點時遇到了一些麻煩。目前我有以下代碼：

public void add(int v) { 
     Node n = new Node(v); 
     if(root==null) 
      root = n; 
     else { 
      Node m = root; 
      while(...) { //not sure what to check 
       if(v < m.value) 
        m = m.left; 
       else 
        m = m.right; 
      } 
      if(...) //not sure what to check 
       m.left = n; 
      else 
       m.right = n; 

     } 
    } 

然後我也想在一定範圍內生成n個節點。我知道如何爲數組做這件事，但我不知道如何去處理BST中的節點。

public void generate(int n, int range) { 

    } 

Answer 1

使用當前的方法，您將需要一個額外的變量來跟蹤父Node

public void add(int v) { 
     Node n = new Node(v); 
     if(root==null) 
      root = n; 
     else { 
      Node m = root,k; 
      while(m!=null) { 
       if(v < m.value){ 
        k=m; 
        m = m.left; 
       } 
       else if(v > m.value){ 
        k=m; 
        m = m.right; 
       }else{ 
        return; //v already exists 
       } 
      } 
      if(v < k.value) 
       k.left=n; 
      else 
       k.right=n; 
     } 
    } 

---

有關範圍內的第二個問題，DrYap指出，一個範圍內和產生的數字每個號碼呼叫add（）

Answer 2

當你插入二叉樹時，你想去，直到你找到一個沒有相應的子節點。然後在該位置插入新節點。

至於從一個範圍填充數字，您生成它們的方式與您對該數組的相同方式相反，但不是插入到數組中，而是您可以使用add方法。

Answer 3

向BST添加值時，橫切樹直到找到空白點並在該點插入新節點。

首先我們從退化情況開始。即，沒有節點並且根是空/空的。

僞代碼：

if root is null then 
    root = new node(value); 
    return; 
end if 

因此，所有我們在這裏做的是建立樹的根節點。它不包含葉節點。

所有後續插入現在要求我們橫切樹。

所以首先我們需要一個起點，它將是根節點。然後我們還需要知道我們是否已經到了一個空白位置，我們可以將新的值插入樹中。這需要跟蹤兩個變量;一個用來保存我們正在檢查的當前節點，另一個用來保存該節點的父節點。

僞代碼：

# initialize tracking variables. 
checkNode = root; 
parentNode = checkNode; 

while checkNode is null do 
    parent = checkNode; # want to save this for when we find a spot to store our new value 
    if valueOf(checkNode) equals value then return # the value is already stored 

    if value < valueOf(checkNode) then 
     # the new value is less than the value stored in this node so continue down the left branch 
     checkNode = checkNode.left 
    else 
     checkNode = checkNode.right # otherwise continue down the right branch 
end while 

# at this point checkNode will be null and parent will be set to a node that can store a new node with our value. 

if value < valueOf(parent) then 
    parent.left = node(value) # store a new node in the left of the found parent node 
else 
    parent.right = node(value) 

我們正在做的是橫切下來的樹比較值被添加到我們正在檢查的節點的值。我們也跟蹤我們正在檢查的節點的父節點，因爲這是我們最終要插入新節點的地方。這是因爲我們在checkNode爲空時結束搜索。