我想計算二叉樹的正確節點，例如以下一個： 15 /10 \ 14所以我做了以下程序：public class NodeT { int elem; NodeT left; NodeT right; public NodeT(int elem){ this.elem=elem; left=null; right=null; }}public class Tree { public NodeT createTree(){ NodeT root=new NodeT(15); NodeT n1=new NodeT(10); NodeT n4=new NodeT(14); root.left=n1; n1.right=n4; return root; } public int countRight(NodeT root){ if (root==null) return 0; //version 1 else{ return 1+countRight(root.right); } }我通過以下方式調用了我的主程序：Tree tree=new Tree();NodeT root=tree.createTree();System.out.println(tree.countRight(root))此代碼打印 1 作為正確答案，但我不明白為什么會這樣。對于我所看到的 15 的右分支等于 null，因此對遞歸函數 countRight() 的調用應該返回 0 并打印不正確的答案。我見過其他解決方案，我發現為了計算所有節點，他們使用如下解決方案： static int n; public int countRight(NodeT root){ //version 2 if (root==null) return 0; if (root.left!=null){ n=countRight(root.left); } if (root.right!=null){ n++; n=countRight(root.right); } return n; }這對我來說似乎更合法。會不會是第一個版本失敗的情況？
2 回答
莫回無
TA貢獻1865條經驗 獲得超7個贊
像這樣的方法永遠不應該使用靜態字段，或任何與此相關的字段。
right任務是統計正確節點的個數，其實就是統計不為空的節點個數。您實際上并不是在計算節點，而是在計算對節點的引用。
這也意味著您必須掃描所有節點，這意味著該方法必須遍歷左右。
最后，根據定義，根節點不是右節點。
public int countRight(NodeT node) {
if (node == null)
return 0;
if (node.right == null)
return countRight(node.left);
return 1 + countRight(node.left) + countRight(node.right);
}
回首憶惘然
TA貢獻1847條經驗 獲得超11個贊
你的第一個代碼將重新運行 2 不會返回 1 遞歸調用
返回 1+另一個更深層次的調用直到 root.right==null
根據您的結構將導致 2 返回您編碼的樹與您繪制的樹不同
添加回答
舉報
0/150
提交
取消