创建二叉搜索树

Question

到目前为止，我已经算出算法来添加到我的二叉搜索树中，但是我有点难以将它转换为代码。该算法如下：

public void add(int v) { 
Create a new node n to hold value v. 
    If tree is empty 
     Set root to n. 
    Else 
     Create temporary node reference m, initialized to root. 
     Loop looking for a gap (a null left or right pointer) that is on the 
     correct side of m for v 
      If v < m.value, look at the left pointer 
      If v >= m.value, look at the right pointer 
     If pointer on correct side is not null, set m to that child node and 
     continue looking 
      m = m.left or m = m.right 
    The search for insertion position stops when node m has a null pointer on 
    the correct side. 
    Insert the new node n at that position 
     m.left = n or m.right = n 
} 

到目前为止，我有：

public void add(int v) { 
     Node n = new Node(v); 
     if(root==null) 
      root = n; 
     else { 
      Node m = root; 
      while(...) { 
       if(...) 
        m = m.left; 
       else 
        m = m.right; 
      } 
      if(...) 
       m.left = m; 
      else 
       m.right = n; 

     } 
    } 

我相信大多数的这是正确的，但我不知道需要做的地方标记为”什么。 ..“

Answer 1

首先，二叉搜索树不应该有任何重复值，这是您在代码中未实现的重要要求。我最近在学习java中的数据结构时实现了二叉搜索树。这里是我写的代码：

public class OrderedBinaryTree 
{ 
    private int _elementsPresent = 0; 
    private Node _root = null; 
    private int [] _values = null; 
    private class Node 
    { 
     Node _left = null; 
     Node _right = null; 
     Node _parent = null; 
     int _value = 0; 
     public Node(int value,Node parent) 
     { 
      _value = value; 
      _parent = parent; 
     } 
    } 
    public void put(int value) 
    { 
     boolean valueInserted = false; 
     Node temp = _root; 
     while(!valueInserted) 
     { 
      if(_root == null) 
      { 
       _root = new Node(value,null); 
       break; 
      } 
      else if(value == temp._value) 
      { 
       System.out.println("the entered value is already present"); 
       return; 
      } 
      else if(value<=temp._value) 
      { 
       if(temp._left == null) 
       { 
        temp._left = new Node(value,temp); 
        break; 
       } 
       else 
       { 
        temp = temp._left; 
       } 
      } 
      else 
      { 
       if(temp._right == null) 
       { 
        temp._right = new Node(value,temp); 
        break; 
       } 
       else 
       { 
        temp = temp._right; 
       } 
      } 
     } 
     _elementsPresent++; 
    }