Проверьте, заполнено ли бинарное дерево Java?

Question

Я пытаюсь написать метод, который вернет true, если бинарное дерево заполнено (каждый узел имеет 2 дочерних узла или нет) и false в противном случае. Это работает некоторое время, но не все. Любые предложения о том, где я ошибаюсь?

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

Определения: бинарное дерево 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 2

Вы не полностью пересекаете дерево. Используйте рекурсию, чтобы поразить все узлы. Проверьте корневой узел. Если детей нет, верните истину. Если есть дети, убедитесь, что их два, а затем проверьте каждый из них рекурсивно.

Answer 3

Попробуйте добавить возврат к каждому утверждению.

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

Кроме того, если корневой узел имеет значение NULL, то ваше дерево заполнено. Таким образом, последний возврат должен быть return true;

Answer 4

Проблема 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 5

Я думаю, что если заявления должны быть следующими:

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 6

Все выше Алгоритмы возвращающие в этом случае (так как они не должны): 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; 
    } 
}