二叉树插入问题。。。。。insert（）仅将新节点放入根节点的子节点

Question

当我使用insert（）将新节点插入到二叉树中时，它只在子节点的位置插入新节点，即使根节点已经有左、右子节点。它不是访问子节点来创建更深层次的二叉树。

抱歉英语不好。

class Node
{
    int key;
    String value;
    Node lc = null;
    Node rc = null;

    Node(int k,String v)
    {   
        key = k;
        value = v;
    }

    public String toString()
    {
        return value + "is" + key;
    }
}

class BT
{
    Node root;
    public void insert(int k,String v)
    {
        Node newnode = new Node(k,v);

        if(root == null)
        {   
            System.out.println("root");
            root = newnode; 
            return;
        }

        Node n = root;
        while(n != null)
        {

            if(newnode.key <= n.key)
            { 
                n = n.lc;
                System.out.println("left");
                if(n==null){n = newnode; break;}
            }
            else
            { 
                n = n.rc;
                System.out.println("right");
                if(n==null){n = newnode; break;}
             } 

        }   
        System.out.println("loop ended");

        return;
    }


    }

    public class test
    {
    public static void main(String arg[])
    {
        BT list = new BT();

        list.insert(19,"one");
        list.insert(67,"sixtyseven");
        list.insert(5,"five");
        list.insert(12,"twelve");
        list.insert(67,"sixtyseven");

    }
}

Answer 1

使用递归怎么样？认识到这一点要清楚得多。

public final class BinaryTree {

    private static final boolean ADD_TO_PARENT = true;
    private static final boolean ALREADY_ADDED = false; 

    private Node root;

    public void add(int key, String value) {
        Node node = new Node(key, value);

        if (add(node, root) == ADD_TO_PARENT)
            root = node;
    }

    private static boolean add(Node node, Node parent) {
        if (parent == null)
            return ADD_TO_PARENT;
        if (node.key <= parent.key) {
            if (add(node, parent.left) == ADD_TO_PARENT)
                parent.left = node;
        } else if (add(node, parent.right) == ADD_TO_PARENT)
            parent.right = node;

        return ALREADY_ADDED;
    }

    public static final class Node {

        private final int key;
        private final String value;
        private Node left;
        private Node right;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return value + " is " + key;
        }
    }

}

Answer 2

您永远不会更改lc和rc链接。试试这样的东西：

        if(newnode.key <= n.key)
        { 
            if(n.lc==null){n.lc = newnode; break;}
            n = n.lc;
            System.out.println("left");
        }
        else
        { 
            if(n.rc==null){n.rc = newnode; break;}
            n = n.rc;
            System.out.println("right");
         }