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

检查完全很容易:
按此处的定义.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();
}