二叉树插入问题.....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

您永远不会更改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");

         } 

Answer 2

如果使用递归呢？认识起来就更清楚了。

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;

        }

    }

}