當(dāng)我用來insert()將新節(jié)點(diǎn)插入二叉樹時(shí)，即使根節(jié)點(diǎn)已經(jīng)有左右子節(jié)點(diǎn)，它也只會(huì)在子節(jié)點(diǎn)的位置插入新節(jié)點(diǎn)。它不是訪問子節(jié)點(diǎn)來使二叉樹更深層次。抱歉英語(yǔ)不好。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"); }}
2 回答
萬(wàn)千封印
TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個(gè)贊
您永遠(yuǎn)不會(huì)更改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");
}
qq_花開花謝_0
TA貢獻(xiàn)1835條經(jīng)驗(yàn) 獲得超7個(gè)贊
如果使用遞歸呢？認(rèn)識(shí)起來就更清楚了。
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;
}
}
}
添加回答
舉報(bào)
0/150
提交
取消