我是理解和學習數據結構的新手。我在搜索一些教程后嘗試實現樹數據結構。看起來不錯，但我不明白這里有點奇怪的遞歸行為。有人可以幫助我理解代碼。我已經包含了一些打印語句來理解遞歸流程，但無法理解為什么沒有返回當前引用？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 有時被重新分配時才返回根元素？
1 回答
慕運維8079593
TA貢獻1876條經驗 獲得超5個贊
由于以下原因，它沒有正確打印：
首先，您的添加方法總是打印“值是”+ root.value，這在試圖弄清楚程序如何添加值時會造成混淆。
其次，您的 add 方法在插入值后打印，我會對其進行重組，以便它首先打印要插入的值，然后打印檢查節點的路徑：
? ? 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);
}
現在每個塊都是自己的插入，程序流程更容易追蹤。
Next: current 實際上打印正確，只是順序相反。假設您要插入 5，當前要打印的節點將是：5 的父節點，即 4，然后是 4 的父節點，即 6。
此圖像可能有助于可視化樹（抱歉我的手寫丑陋）
如果要更改順序，請這樣做（將 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);
}
我希望這對您有所幫助，并且我已經解釋清楚了。
翻過高山走不出你
TA貢獻1875條經驗 獲得超3個贊
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
瀏覽上面的文章應該有所幫助?？鞓穼W習?。?/p>
添加回答
舉報
0/150
提交
取消