如何檢查樹是否完整？

Question

這是我的A級二叉搜索樹的：

public class BinarySearchTree { 

     class BSTNode { 
       int data; 
       BSTNode rchild; 
       BSTNode lchild; 

       //constructor 
       public BSTNode(int n){ 
         data=n; 
         lchild=rchild=null; 

       } 
     } 

     private BSTNode root; 
     private int size; 

     public BinarySearchTree() { 
       root = null; 
       size = -1; 
     } 

     public boolean insert(int n) { 
       if (root == null) 
         root = new BSTNode(n); 
       else 
         insert(n, root); 
       return true; 
     } 

     private void insert(int n, BSTNode r) { 

       if (r.data > n) 
         if (r.lchild == null) 
           r.lchild = new BSTNode(n); 
         else 
           insert(n, r.lchild); 
       else 

       if (r.data < n) 
         if (r.rchild == null) 
           r.rchild = new BSTNode(n); 
         else 
           insert(n, r.rchild); 


     } 
} 

其實我發現以書面形式來檢查，如果我的樹是完全二叉樹方法的難度。有人可以爲我提供解決方案嗎？

我將遵循以下定義： 完整的二叉樹：除最後一層以外的每個層都完全填充，並且所有節點都是左對齊的。

Answer 1

對於您的BSTNode的實施，您將不得不修改這一點，但我相信這應該適合您的需求。基本思想是遞歸遍歷樹並確保每個子樹都滿足「complete」屬性。

boolean checkBinaryTreeCompleteness(TreeNode root) { 
    if (root != null) { 
    if (root.right == null && root.left == null) { 
     return true; 
    } 
    if (root.right != null && root.left != null) { 
     return checkBinaryTreeCompleteness(root.left) && checkBinaryTreeCompleteness(root.right); 
    } 
    } 
    return false; 
}