数据结构学习笔记4.2--插入节点

    /**
     * 插入节点，跟查找节点代码类似，只是在遇到null时，将节点插入，修改引用
     * @param id key值
     * @param dd value值
     */
    public void insert(int id, double dd)
    {
        // 插入的节点
        Node newNode = new Node();
        newNode.iData = id;
        newNode.dData = dd;

        // 如果根节点为空，则插入节点为根节点
        if (root == null)
        {
            root = newNode;
        }
        else
        {
            // 当前节点，引用会随在查找变化
            // 由于查找要插入的节点是从根基点开始，所以root引用赋值给current
            Node current = root;

            // 父节点
            // 有父节点的引用，才能够给子节点leftChild或者rightChild赋值
            Node parent;
            
            while (true)
            {
                // 保存父节点的引用，因为后面在查找时，current的引用一定会为null，
                // 此时说明已经找到插入节点的位置了
                parent = current;
                
                // 插入节点在左子树
                if (id < current.iData)
                {
                    current = current.leftChild;
                    if (current == null)
                    {
                        parent.leftChild = newNode;
                        return;
                    }
                }
                // 插入节点在右子树
                else
                {
                    current = current.rightChild;
                    if (current == null)
                    {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }