检查 Java 中的二叉树是否已满？

Question

我正在尝试编写一种方法，如果二叉树已满（每个节点有 2 个子节点或 none），则 return 为真，否则为假。这在某些时候有效，但并非全部。关于我出错的地方有什么建议吗？

public static void testNum4()
    {
        System.out.println("How many nodes do you want in your tree?");
        int num=sc.nextInt();
        //TreeNode<Integer> root = TreeUtil.createBalancedNumberTree(num);  Use to test for a balanced tree
        TreeNode<Integer> root = TreeUtil.createIntegerTree(num);
        TreeUtil.displayTreeInWindow(root);
        System.out.println(isFull(root));
        TreeUtil.displayTreeInWindow (root);
    }

    public static boolean isFull(TreeNode<Integer>  root) {
    // pre: root of tree, 0 or more nodes
    // post: returns true if the input tree is a full tree; false otherwise

        if (root!=null) {
            if ((root.getLeft() != null && root.getRight() != null) || (root.getRight() == null && root.getLeft() == null))
            {
                return true;
            }
            else if (root.getLeft()!=null)
            {
                isFull(root.getLeft());
            }
            else if (root.getRight()!=null)
            {
                isFull(root.getRight());
            }
            else 
                return false;

        }
            return false;
    }

Answer 1

您没有完全遍历树。使用递归来命中所有节点。检查根节点。如果没有children，return为真。如果有children，请确保有两个，然后递归检查每个。

Answer 2

尝试在每个语句中添加 return。

    else if (root.getLeft()!=null  && root.getRight()!=null)
    {
        return isFull(root.getLeft()) && isFull(root.getRight());
   }

此外，如果根节点为空，则您的树已满。所以最后的return应该是return true;

Answer 3

问题是 else if 和缺少 return 语句。也不需要检查 null 这么多，并且使用方法使其更具可读性。

public static boolean isFull(TreeNode<Integer> node) {

    if (node == null) return false;

    if (isLeaf(node)) return true;

    return isFull(node.getLeft()) && isFull(node.getRight());
}

public static boolean isLeaf(TreeNode<Integer> node) {
    return node.getRight() == null && node.getLeft() == null;
}

Answer 4

我认为if语句应该如下：

if (root.getRight() == null && root.getLeft() == null)
{
    // The node has no children (full)
    return true;
}
else if (root.getLeft() != null && root.getRight() != null)
{
    // There are two children. Tree is only full if both sub trees are full
    return isFull(root.getLeft()) && isFull(root.getRight());
}
else 
{
    // Only one child
    return false;
}

Answer 5

定义：一棵二叉树 T 是满树，如果每个节点是叶节点或恰好拥有两个子节点。

public static boolean isFull(TreeNode<Integer>  root)
// pre: root of tree, 0 or more nodes
// post: returns true if the input tree is a full tree; false otherwise
{

    if (root!=null)
    {
        if(root.getRight() == null && root.getLeft() == null)
        {
             return true;
        }
        if ((root.getRight() != null && root.getLeft() != null))
        {
            return isFull(root.getLeft())&&isFull(root.getLeft());
        }
    }
    return false;
}

Answer 6

上面的所有算法 return 在这种情况下都是正确的（因为它们不应该）： complete binary tree .所以，希望这会有所帮助：

//-1 means "false"
public boolean full() {
    int high = 0;
    return ( root != null && isFull(root, high) != -1 );
}

public boolean isLeaf() {
    return node.getRight() == null && node.getLeft() == null;
}

private int isFull(TreeNode<T> node, int high)
{
    ++high;
    if (node.isLeaf())
        return high;
    else
    {
        int hLeft=0, hRight=0;
        if(node.getLeft() != null)
            hLeft = isFull(node.getLeft(), high);
        if(node.getRight() != null)
            hRight = isFull(node.getRight, high);

        if ( (hLeft == hRight) && (hLeft != -1) )
            return ++high;
        return -1;
    }
}

检查 Java 中的二叉树是否已满？

Check if a binary tree is full in Java?

java

algorithm

tree