二叉树插入问题.....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链接。尝试这样的事情：&nbsp; &nbsp; &nbsp; &nbsp; if(newnode.key <= n.key)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(n.lc==null){n.lc = newnode; break;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n = n.lc;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("left");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(n.rc==null){n.rc = newnode; break;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n = n.rc;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("right");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp;

Answer 2

如果使用递归呢？认识起来就更清楚了。public final class BinaryTree {&nbsp; &nbsp; private static final boolean ADD_TO_PARENT = true;&nbsp; &nbsp; private static final boolean ALREADY_ADDED = false;&nbsp;&nbsp; &nbsp; private Node root;&nbsp; &nbsp; public void add(int key, String value) {&nbsp; &nbsp; &nbsp; &nbsp; Node node = new Node(key, value);&nbsp; &nbsp; &nbsp; &nbsp; if (add(node, root) == ADD_TO_PARENT)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; root = node;&nbsp; &nbsp; }&nbsp; &nbsp; private static boolean add(Node node, Node parent) {&nbsp; &nbsp; &nbsp; &nbsp; if (parent == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return ADD_TO_PARENT;&nbsp; &nbsp; &nbsp; &nbsp; if (node.key <= parent.key) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (add(node, parent.left) == ADD_TO_PARENT)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent.left = node;&nbsp; &nbsp; &nbsp; &nbsp; } else if (add(node, parent.right) == ADD_TO_PARENT)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent.right = node;&nbsp; &nbsp; &nbsp; &nbsp; return ALREADY_ADDED;&nbsp; &nbsp; }&nbsp; &nbsp; public static final class Node {&nbsp; &nbsp; &nbsp; &nbsp; private final int key;&nbsp; &nbsp; &nbsp; &nbsp; private final String value;&nbsp; &nbsp; &nbsp; &nbsp; private Node left;&nbsp; &nbsp; &nbsp; &nbsp; private Node right;&nbsp; &nbsp; &nbsp; &nbsp; public Node(int key, String value) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.key = key;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.value = value;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return value + " is " + key;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}