我是理解和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的新手。我在搜索一些教程后嘗試實(shí)現(xiàn)樹數(shù)據(jù)結(jié)構(gòu)?？雌饋聿诲e(cuò)，但我不明白這里有點(diǎn)奇怪的遞歸行為。有人可以幫助我理解代碼。我已經(jīng)包含了一些打印語句來理解遞歸流程，但無法理解為什么沒有返回當(dāng)前引用？public class TreeCheck {Node root;private Node addRecursive(Node current, int value) {if (current == null) { return new Node(value);}if (value < current.value) { current.left = addRecursive(current.left, value);} else if (value > current.value) { current.right = addRecursive(current.right, value);} else { // value already exists return current;}System.out.println("current is "+current.value); //Please compare in the image why the return current;}public void add(int value) {root = addRecursive(root, value);System.out.println("value is "+root.value);} public static void main(String h[]){ TreeCheck bt = new TreeCheck(); bt.add(6); bt.add(4); bt.add(8); bt.add(3); bt.add(5); bt.add(7); bt.add(9); } class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null;}}為什么 current 語句被打印兩次并且總是只在 current 有時(shí)被重新分配時(shí)才返回根元素？
1 回答
慕運(yùn)維8079593
TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超5個(gè)贊
由于以下原因，它沒有正確打印：
首先，您的添加方法總是打印“值是”+ root.value，這在試圖弄清楚程序如何添加值時(shí)會(huì)造成混淆。
其次，您的 add 方法在插入值后打印，我會(huì)對(duì)其進(jìn)行重組，以便它首先打印要插入的值，然后打印檢查節(jié)點(diǎn)的路徑：
? ? public void add(int value) {
? ? // you always printed out the value of the root node with every call to this method
? ? // I updated it to reflect the input argument
? ? System.out.println("\nvalue is " + value);
? ? root = addRecursive(root, value);
}
現(xiàn)在每個(gè)塊都是自己的插入，程序流程更容易追蹤。
Next: current 實(shí)際上打印正確，只是順序相反。假設(shè)您要插入 5，當(dāng)前要打印的節(jié)點(diǎn)將是：5 的父節(jié)點(diǎn)，即 4，然后是 4 的父節(jié)點(diǎn)，即 6。
此圖像可能有助于可視化樹（抱歉我的手寫丑陋）
如果要更改順序，請(qǐng)這樣做（將 current 的打印放在 if 語句之前）：
? ? private Node addRecursive(Node current, int value) {
? ? if (current == null) {
? ? ? ? return new Node(value);
? ? }
? ? System.out.println("current is " + current.value);
? ? if (value < current.value) {
? ? ? ? current.left = addRecursive(current.left, value);
? ? } else if (value > current.value) {
? ? ? ? current.right = addRecursive(current.right, value);
? ? } else {
? ? ? ? // value already exists
? ? ? ? return current;
? ? }
? ? return current;
}
此外，如果您想查看插入二叉搜索樹是否有效，您可以使用此方法按升序打印您的樹：
? ? public void inOrderPrint(Node node){
? ? if (node.left != null) {
? ? ? ? inOrderPrint(node.left);
? ? }
? ? System.out.println(node.value);
? ? if (node.right != null) {
? ? ? ? inOrderPrint(node.right);
? ? }
}
在你的 main 中這樣稱呼它：
? ? public static void main(String h[]) {
? ? TreeCheck bt = new TreeCheck();
? ? bt.add(6);
? ? bt.add(4);
? ? bt.add(8);
? ? bt.add(3);
? ? bt.add(5);
? ? bt.add(7);
? ? bt.add(9);
? ? System.out.println("-------");
? ? bt.inOrderPrint(bt.root);
}
我希望這對(duì)您有所幫助，并且我已經(jīng)解釋清楚了。
翻過高山走不出你
TA貢獻(xiàn)1875條經(jīng)驗(yàn) 獲得超3個(gè)贊
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
瀏覽上面的文章應(yīng)該有所幫助?？鞓穼W(xué)習(xí)??！
添加回答
舉報(bào)
0/150
提交
取消