要请检查是否这是一个完全二叉树或完全二叉树或两个都不选

问题描述

我是新用，如果二叉树的概念。我一直停留在多日的问题。这是找到一个给定的树是二叉树或完全二叉树或者两个都不选。

I am new with the concept if binary trees. I have been stuck at a question for many days. It is to find if a given tree is a binary tree or a fully binary tree or neither of the two.

我想到很多算法，但他们没有满足每一宗个案。我试图谷歌，但没有妥善的解决办法。

I have thought of many algorithm but none of them fulfill each and every case.I tried google but there was no proper solution.

我想用等级序遍历技术，但不能想出如何知道thier水平后，所有的节​​点都被插入到队列中。

I thought of using Level Order Traversal Technique but couldn't come up with how to know thier levels after all the nodes have been inserted in the queue.

对于完全二叉树我试着计算，如果所有节点的度是0或2，但这时如果树有度数一些中间节点这个逻辑也是错误的。

For the Fully Binary tree I tried counting if the degree of all the nodes are 0 or 2 but then if the tree has some intermediate node with degree this logic is also wrong.

我已经用链表做一棵树，基本 - 左子右孩子关系的方式

I have made a tree using a linked list, The basic - Left Child, Right Child Relationship way.

对于完全二叉树我做了序traverl和检查的程度如果为0或2，但它是错误的原因，如果有一些早期的水平度0的节​​点，然后还再输出成真。

For the fully binary tree I do a inorder traverl and checked the degree if 0 or 2, but it's wrong cause if there's a node at some earlier level with degree 0 then also then output comes true.

对于完全二叉树我不能想出什么合适的。

For the complete binary tree i couldn't come up with anything proper.

感谢你。

和我使用C ++，所以如果逻辑使用指针，那么这是正常的。

And I am using C++, so if the logic uses pointers then it's alright.

推荐答案

检查是否完整很简单：
通过这里的定义。 http://courses.cs.vt.edu/cs3114/Summer11/Notes/T03a.BinaryTreeTheorems.pdf

Checking for Full is easy:
By the definition here. http://courses.cs.vt.edu/cs3114/Summer11/Notes/T03a.BinaryTreeTheorems.pdf

该树已满如果所有节点都为0或两个孩子。

The tree is full if all nodes have either 0 or two children.

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应该只有空物体留下来的。如果你发现一个非空对象后，这是不是一个完整的树。

Complete is a little harder.
But the easiest way seems to be a breadth first (left to right) traversal of the tree. At each node push both left and right onto the list be traversed (even if they are NULL). After you hit the first NULL there should only be NULL objects left to find. If you find a non NULL object after this it is not a complete tree.

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

这篇关于要请检查是否这是一个完全二叉树或完全二叉树或两个都不选的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！