Как определить, является ли двоичное дерево полным?

Question

Полное двоичное дерево определяется как двоичное дерево, в котором каждый уровень, за исключением, возможно, самого глубокого, полностью заполнен. На самом глубоком уровне все узлы должны быть как можно левее.

Я думаю, что простой рекурсивный алгоритм сможет определить, завершено ли заданное двоичное дерево, но я не могу понять это.

Answer 1

Аналогично:

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right))

У вас есть:

perfect(t) = if (t==NULL) then 0 else { 
                  let h=perfect(t.left)
                  if (h != -1 && h==perfect(t.right)) then 1+h else -1
             }

Где perfect (t) возвращает -1, если листья не все на одной глубине или у любого узла есть только один дочерний элемент; в противном случае возвращается высота.

Редактировать: это для "complete" = "Совершенное двоичное дерево - это полное двоичное дерево, в котором все листья находятся на одной глубине или на одном уровне. 1 (Это также неоднозначно называется полным двоичное дерево.) "( Wikipedia ).

Вот рекурсивная проверка: «Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее». Он возвращает (-1, ложь), если дерево не завершено, в противном случае (высота, полное), если оно есть, с полным == истина, если оно идеально.

complete(t) = if (t==NULL) then (0,true) else { 
                  let (hl,fl)=complete(t.left)
                  let (hr,fr)=complete(t.right)                      
                  if (fl && hl==hr) then (1+h,fr)
                  else if (fr && hl==hr+1) then (1+h,false)
                  else (-1,false)
              }

Answer 2

Самая простая процедура:

1. Найти глубину дерева (простой алгоритм).
2. Подсчет количества узлов в дереве (путем обхода и увеличения счетчика на единицу при посещении любого узла).
3. Для полного двоичного дерева уровня d число узлов равно pow (2, d + 1) -1 .

Если условие удовлетворяет дереву, это полное двоичное дерево, иначе нет.

Это простой алгоритм и превращение его в рабочий код не должно быть проблемой, если вы достаточно хороший кодер.

Answer 3

//Helper function

int depth (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return 0;

   ld=depth(n->left);
   ld=depth(n->right);

   if (ld>rd)
      return (1+ld);
   else
      return (1+rd);

}


//Core function

int isComplete (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return TRUE;

   ld=depth(n->left);
   rd=depth(n->right);

   return(ld==rd && isComplete(n->left) && isComplete(n->right));

}

Answer 4

Вот код C для проверки, завершено ли двоичное дерево:

struct node
{
    int data;
    struct node * left;
    struct node * right;
};
int flag;
int isComplete(struct node *root, int depth)
{
    int ld, rd;
    if (root==NULL) return depth;
    else
    {
        ld =  isComplete(root->left,depth+1);
        rd = isComplete(root->right, depth+1);
        if (ld==-1 || rd==-1) return -1;
        else if (ld==rd) return ld;
        else if (ld==rd-1 && flag==0)
        {
            flag=1;
            return rd;
        }
        else return -1;
    }
}

Как это работает:

• Если глубина левого поддерева совпадает с глубиной правого поддерева, он возвращает глубину до уровня найма.

• если глубина левого поддерева больше глубины правого поддерева, он возвращает глубину правого поддерева вверх по иерархии и включает флаг.

• Если он находит, что глубина левого поддерева, правого поддерева и флага уже установлена, он возвращает -1 по иерархии.

• В конце концов, если функция возвращает -1, это не полное поддерево, иначе возвращаемое значение является минимальной глубиной дерева.

Answer 5

Спасибо за псевдокод @Jonathan Graehl. Я реализовал это на Java. Я проверил это против итеративной версии. Это работает как шарм!

public static boolean isCompleteBinaryTreeRec(TreeNode root){
//      Pair notComplete = new Pair(-1, false);
//      return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);
    return isCompleteBinaryTreeSubRec(root).height != -1;
}

public static boolean isPerfectBinaryTreeRec(TreeNode root){
    return isCompleteBinaryTreeSubRec(root).isFull;
}

public static Pair isCompleteBinaryTreeSubRec(TreeNode root){
    if(root == null){
        return new Pair(0, true);
    }

    Pair left = isCompleteBinaryTreeSubRec(root.left);
    Pair right = isCompleteBinaryTreeSubRec(root.right);

    if(left.isFull && left.height==right.height){
        return new Pair(1+left.height, right.isFull);
    }

    if(right.isFull && left.height==right.height+1){
        return new Pair(1+left.height, false);
    }

    return new Pair(-1, false);
}

private static class Pair{
    int height;         
    boolean isFull;     

    public Pair(int height, boolean isFull) {
        this.height = height;
        this.isFull = isFull;
    }

    public boolean equalsTo(Pair obj){
        return this.height==obj.height && this.isFull==obj.isFull;
    }
}

Answer 6

private static boolean isCompleteBinaryTree(TreeNode root) {

if (root == null) {
    return false;
} else {
    boolean completeFlag = false;
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(root);
    while (!list.isEmpty()) {
        TreeNode element = list.remove(0);
        if (element.left != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.left);
        } else {
            completeFlag = true;
        }
        if (element.right != null) {
            if (completeFlag) {
                return false;
            }
        list.add(element.right);
        } else {
            completeFlag = true;
        }
    }
        return true;
    }
}

Ссылка: Проверьте следующую ссылку для подробного объяснения http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Answer 7

Вы также можете решить эту проблему с помощью обхода порядка уровней. Процедура выглядит следующим образом:

1. Хранить элемент данных узлов, встречающихся в векторе
2. Если узел имеет значение NULL, сохраните специальный номер (INT_MIN)
3. Отслеживание последнего ненулевого посещенного узла - lastentry
4. Теперь пересеките вектор до lastentry. Если вы когда-нибудь встретите INT_MIN, то дерево не будет полным. Иначе это полное двоичное дерево.

Вот код C ++:

Мой узел дерева:

struct node{
    int data;
    node *left, *right;
};

void checkcomplete(){//checks whether a tree is complete or not by performing level order traversal
    node *curr = root;
    queue<node *> Q;
    vector<int> arr;
    int lastentry = 0;
    Q.push(curr);
    int currlevel = 1, nextlevel = 0;
    while( currlevel){
        node *temp = Q.front();
        Q.pop();
        currlevel--;
        if(temp){
            arr.push_back(temp->data);
            lastentry = arr.size();
            Q.push(temp->left);
            Q.push(temp->right);
            nextlevel += 2;
        }else
            arr.push_back(INT_MIN);
        if(!currlevel){
            currlevel = nextlevel;
            nextlevel = 0;
        }
    }
    int flag = 0;
    for( int i = 0; i<lastentry && !flag; i++){
        if( arr[i] == INT_MIN){
            cout<<"Not a complete binary tree"<<endl;
            flag = 1;
        }
    }
    if( !flag )
        cout<<"Complete binary tree\n";
}

Answer 8

Следующий код просто обрабатывает все возможные случаи. Высота дерева достигается по пути, чтобы избежать очередной рекурсии.

enum CompleteType
{
    kNotComplete = 0,
    kComplete = 1, // Complete but not full
    kFull = 2,
    kEmpty = 3
};

CompleteType isTreeComplete(Node* node, int* height)
{
    if (node == NULL)
    {
        *height = 0;
        return kEmpty;
    }

    int leftHeight, rightHeight;

    CompleteType leftCompleteType = isTreeComplete(node->left, &leftHeight);
    CompleteType rightCompleteType = isTreeComplete(node->right, &rightHeight);

    *height = max(leftHeight, rightHeight) + 1;

    // Straight forwardly treat all possible cases
    if (leftCompleteType == kComplete && 
        rightCompleteType == kEmpty &&
        leftHeight == rightHeight + 1)
        return kComplete;

    if (leftCompleteType == Full)
    {
        if (rightCompleteType == kEmpty && leftHeight == rightHeight + 1)
            return kComplete;
        if (leftHeight == rightHeight)
        {
            if (rightCompleteType == kComplete)
                return kComplete;
            if (rightCompleteType == kFull)
                return kFull;
        }
    }

    if (leftCompleteType == kEmpty && rightCompleteType == kEmpty)
        return kFull;

    return kNotComplete;
}

bool isTreeComplete(Node* node)
{
    int height;
    return (isTreeComplete(node, &height) != kNotComplete);
}

Answer 9

int height (node* tree, int *max, int *min) {

  int lh = 0 , rh = 0 ;
  if ( tree == NULL )
    return 0;
  lh = height (tree->left,max,min) ;
  rh = height (tree->right,max,min) ;
  *max = ((lh>rh) ? lh : rh) + 1 ;
  *min = ((lh>rh) ? rh : lh) + 1 ;
  return *max ;
}

void isCompleteUtil (node* tree, int height, int* finish, int *complete) {
  int lh, rh ;
  if ( tree == NULL )
    return ;
  if ( height == 2 ) {
    if ( *finish ) {
      if ( !*complete )
        return;
      if ( tree->left || tree->right )
        *complete = 0 ;
      return ;
    }
    if ( tree->left == NULL && tree->right != NULL ) {
      *complete = 0 ;
      *finish = 1 ;
    }
    else if ( tree->left == NULL && tree->right == NULL )
      *finish = 1 ;
    return ;
  }
  isCompleteUtil ( tree->left, height-1, finish, complete ) ;
  isCompleteUtil ( tree->right, height-1, finish, complete ) ;
}

int isComplete (node* tree) {
  int max, min, finish=0, complete = 1 ;
  height (tree, &max, &min) ;
  if ( (max-min) >= 2 )
    return 0 ;
  isCompleteUtil (tree, max, &finish, &complete) ;
  return complete ;
}

Answer 10

Вы можете сделать это рекурсивно, сравнивая высоты дочерних узлов каждого узла. Может быть не более одного узла, где левый ребенок имеет высоту ровно на один больше, чем у правого ребенка; все остальные узлы должны быть идеально сбалансированы.