要检查它是完整的二叉树还是完全二叉树,或者两者都不是

Question

如果是二叉树,我是新概念.我被困在一个问题很多天了.它是为了查找给定的树是二叉树还是完全二叉树,或者两者都不是.

我已经想到了很多算法,但它们都没有满足每一个案例.我试过谷歌,但没有适当的解决方案.

我想过使用Level Order Traversal Technique但是在将所有节点插入队列之后无法知道如何知道它们的级别.

对于完全二进制树,我尝试计算所有节点的度数是0还是2但是如果树有一些具有度的中间节点,则该逻辑也是错误的.

我使用链表制作了一棵树,基本 - 左子,右子关系方式.

对于完全二叉树,我做一个inorder traverl并检查度数是否为0或2,但这是错误的,如果某个节点处于某个较早级别的0度,那么输出也会成立.

对于完整的二叉树,我无法想出任何合适的东西.

谢谢.

我正在使用C++,所以如果逻辑使用指针那么它就没问题了.

Answer 1

检查完全很容易:
按此处的定义.http://courses.cs.vt.edu/cs3114/Summer11/Notes/T03a.BinaryTreeTheorems.pdf

如果所有节点都有0个或2个子节点,则树已满.

bool full(Node* tree)
{
    // Empty tree is full so return true.
    // This also makes the recursive call easier.
    if (tree == NULL)
    {   return true;
    }

    // count the number of children
    int count = (tree->left == NULL?0:1) + (tree->right == NULL?0:1);

    // We are good if this node has 0 or 2 and full returns true for each child.
    // Don't need to check for left/right being NULL as the test on entry will catch
    // NULL and return true.
    return count != 1 && full(tree->left) && full(tree->right);
}

完成有点困难.
但最简单的方法似乎是遍历树的广度(从左到右).在每个节点上,遍历列表的左侧和右侧(即使它们是NULL).在达到第一个NULL之后,应该只剩下要查找的NULL对象.如果在此之后找到非NULL对象,则它不是完整的树.

bool complete(Node* tree)
{
    // The breadth first list of nodes.
    std::list<Node*>  list;
    list.push_back(tree);   // add the root as a starting point.

    // Do a breadth first traversal.
    while(!list.empty())
    {
        Node* next = list.front();
        list.pop_front();

        if (next == NULL)
        {   break;
        }

        list.push_back(next->left);
        list.push_back(next->right);
    }

    // At this point there should only be NULL values left in the list.
    // If this is not true then we have failed.

    // Written in C++11 here.
    // But you should be able to traverse the list and look for any non NULL values.
    return std::find_if(list.begin(), list.end(), [](Node* e){return e != NULL;}) != list.end();
}

Answer 2

一种方法确实可以是级别顺序遍历，正如您所建议的，将其实现为BFS，并将其推送到 (level,node) 的队列对。当且仅当除最后一层之外的每一层的节点数是前一层的节点数的两倍时，树才为满树，或者2^level。

看一下下面的伪代码：

is_full_binary(root) { 
  queue q = new queue()
  q.push(pair(0,root))
  int currentNodes = 0
  int current = 0
  while q.isEmpty() == false { 
    level, node = q.pop()
    q.push(pair(level+1, node.left)) // make sure such exist before...
    q.push(pair(level+1, node.right)) //same here
    if level == current
         currentNodes++
    else {
         if currentNodes != 2^current
              return false
         currentNodes = 0
         current = level
    }
  }
return true
}

上面的伪代码检查每个级别是否恰好有 2^level 节点，如果有则返回 true，否则返回 false - 这意味着它检查树是否已满。

检查它是否未满，但完整需要在最后一个级别做更多的工作 - 并且留给您，它的概念将非常相似。