c++ - 检查它是完全二叉树还是完全二叉树或两者都不是

Question

我不熟悉二叉树的概念。我被困在一个问题上很多天了。就是判断给定的树是二叉树还是完全二叉树，或者两者都不是。

我想过很多算法，但没有一个能满足所有情况。我试过谷歌，但没有合适的解决方案。

我想到了使用级别顺序遍历技术，但无法想出在所有节点都已插入队列后如何知道它们的级别。

对于完全二叉树，我尝试计算所有节点的度数是否为 0 或 2，但如果树有某个度数为中间节点，则此逻辑也是错误的。

我使用链表制作了一棵树，基本的 - 左 child ，右 child 关系方式。

对于完全二叉树，我进行了中序遍历并检查了度数是否为 0 或 2，但这是错误的，因为如果在某个较早的级别上存在度数为 0 的节点，则输出也为真。

对于完整的二叉树，我想不出任何合适的东西。

谢谢。

而且我使用的是 C++，所以如果逻辑使用指针就没问题。

Answer 1

检查是否完整很容易:
根据这里的定义。 http://courses.cs.vt.edu/cs3114/Summer11/Notes/T03a.BinaryTreeTheorems.pdf

如果所有节点都有 0 个或两个子节点，则树已满。

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();
}