java - 创建二叉搜索树

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++;
    }