java - 创建二进制搜索树

到目前为止，我已经找到了可以添加到二进制搜索树中的算法，但是在将其转换为代码方面遇到了一些困难。算法如下：

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;

        }
    }

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

最佳答案

首先，二进制搜索树不应有任何重复的值，这是您尚未在代码中实现的重要要求。我最近在学习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++;
    }