3

注意：这是与家庭作业相关的，但我没有这样标记它，因为“家庭作业”标签被标记为过时（？）

使用以下实现二叉树的类...

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)

有人可以帮我吗？

4

6 回答 6

6

您非常接近并且遍历看起来不错，但是在您的 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)
于 2013-02-06T00:26:08.170 回答
2

正如您已经注意到的，一种解决方案是计算只有一个孩子的父母的数量。这应该有效：

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;   
    }
于 2013-02-06T01:13:19.043 回答
1

如果正好有一个孩子是非空的（这意味着它的孩子正好有一个是空的），则父母有一个独生子女：

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

但是，当您在递归代码遍历树时访问该节点时，您不会测试该节点。（这类似于访问者模式。）当您坐在父母身上时，您所做的是测试独生子女。这实际上是一个逻辑异或测试，因为只有一个子节点需要为非 null 才能检测到该节点有唯一的子节点。

所以算法是

  1. 访问树中的每个节点。
  2. 数一下，如果节点只有一个孩子

而已。剩下的就是水管了。

于 2013-02-06T00:13:03.100 回答
1 
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;
}
于 2016-04-30T03:43:33.020 回答
0

每当您遍历二叉树时，请递归思考。这应该有效。

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());

  }
于 2013-02-06T00:14:39.083 回答
-1 
public int countNode(Node root) {

         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);

     }
于 2013-07-02T13:58:53.750 回答