如何計算二叉樹中「獨子」節點的數量？

Question

注意：這是家庭作業相關的，但我沒有標註它是這樣，因爲「功課」的標籤被標記爲已廢棄

使用下面的類，它實現二叉樹...

（？）

class TreeNode 
{ 
    private Object value; 
    private TreeNode left, right; 

    public TreeNode(Object initValue) 
    { 
    value = initValue; 
    left = null; 
    right = null; 
    } 

    public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) 
    { 
    value = initValue; 
    left = initLeft; 
    right = initRight; 
    } 

    public Object getValue() 
    { 
    return value; 
    } 

    public TreeNode getLeft() 
    { 
    return left; 
    } 

    public TreeNode getRight() 
    { 
    return right; 
    } 

    public void setValue(Object theNewValue) 
    { 
    value = theNewValue; 
    } 

    public void setLeft(TreeNode theNewLeft) 
    { 
    left = theNewLeft; 
    } 

    public void setRight(TreeNode theNewRight) 
    { 
    right = theNewRight; 
    } 

}

我需要計算二叉樹是節點的數目「獨生子女」，這被定義爲沒有從其父所產生另一個節點的節點。

這是我到目前爲止有：

public static int countOnlys(TreeNode t) 
    { 
    if(t == null) 
     return 0; 
    if(isAnOnlyChild(t)) 
     return 1; 
    return countOnlys(t.getLeft()) + countOnlys(t.getRight()); 
    } 

我不知道如何實現boolean方法isAnOnlyChild(TreeNode t)

有人能幫助我嗎？

Answer 1

你是非常接近，有遍歷看起來不錯，但在你的Treenode你沒有一個孩子和它的父母之間的聯繫。所以，如果有兄弟姐妹（正確的孩子）存在，你不能說出一個左小孩。

你可以有一個父Treenode（與左和右），所以你可以檢查給定節點的父節點有多少個孩子。或者按照ajp15243的建議，改爲使用一種方法來檢查給定節點有多少個孩子。

後者的一些僞代碼：

//we still need to check if that only child has its own children 
if hasOnlyChild(t) 
     return 1 + checkOnlys(left) + checkOnlys(right) 
else 
     return checkOnlys(left) + checkOnlys(right) 

Answer 2

的家長都有一個唯一的孩子，如果孩子只有一個非空（這意味着它的孩子中只有一個爲空）：

((t.getLeft() == null || t.getRight() == null)) && !(t.getLeft() == null && t.getRight() == null)

你不考，但是，當您通過遞歸代碼遍歷樹時訪問節點。 （這與訪問者模式相似。）當你坐在父母身上時，你所做的是測試一個獨生子女。它實際上是一個邏輯的排他或測試，因爲只有一個孩子需要非空來檢測這個節點是否只有一個孩子。

所以算法是

1. 訪問樹中的每個節點。
2. 算吧，如果節點只有一個孩子

就是這樣。其餘的是管道。

Answer 3

每當遍歷二叉樹時，都要遞歸思考。這應該工作。

public static int countOnlys(TreeNode t) 
    { 
    if(t == null) 
     return 0; 
    if (t.getLeft()==null&&t.getRight()==null) 
     return 1; 

    return countOnlys(t.getLeft())+countOnlys(t.getRight()); 

    } 

Answer 4

正如你已經注意到了，一個解決方案是數着只有一個孩子的父母的數量。這應該工作：

public static int countOnlys(TreeNode t) 
    { 
    if(t == null || numberOfChildren(t)==0){ 
     return 0; 
    } 
    if(numberOfChildren(t)==1){ 
     return 1+ countOnlys(t.getLeft()) + countOnlys(t.getRight()); 
    } 
     if(numberOfChildren(t)==2){ 
     return countOnlys(t.getLeft()) + countOnlys(t.getRight()); 
    } 
     return 0; 
    } 

public static int numberOfChildren (TreeNode t){ 
    int count = 0; 
    if(t.getLeft() != null) count++; 
    if(t.getRight() != null) count++;  
    return count; 
    } 

Answer 5

公衆詮釋countNode（節點根）{

 if(root == null) 
     return 0; 

    if(root.leftChild == null && root.rightChild == null) 
     return 0; 
    if(root.leftChild == null || root.rightChild == null) 
     return 1 + countNode(root.leftChild) + countNode(root.rightChild); 
    else 
     return countNode(root.leftChild) + countNode(root.rightChild); 

} 

Answer 6

public static int onlyChild(TreeNode t){ 
    int res = 0; 
    if(t != null){ 
     //^means XOR 
     if(t.getLeft() == null^t.getRight() == null){ 
      res = 1; 
     } 

     res += onlyChild(t.getLeft()) + onlyChild(t.getRight())); 
    } 

    return res; 
}