1.【基础题】–判断一棵树是否是完全二叉树。提示：层序遍历变型题。
（1）基础知识 【二叉树】:二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
【满二叉树】:高度为N的满二叉树有2^N- 1个节点的二叉树。
【完全二叉树】: 若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树 【满二叉树是完全二叉树的特例】
（2）判断一棵树是否是完全二叉树的思路 1>如果树为空，则直接返回错 2>如果树不为空：层序遍历二叉树 2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列； 2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树； 2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；
（3）代码实现
#include<iostream> using namespace std; #include<queue> template<class T> struct TreeNode { T data; TreeNode<T>* left; TreeNode<T>* right; TreeNode(const T& x) :data(x) ,left(NULL) ,right(NULL) {} };
---------- template<class T> bool IsComplete(TreeNode<T>* root) { //1.树为空，返回错误 if (root==NULL) { return false; } //2.树不为空 queue<TreeNode<T>*> q; q.push(root); while (!q.empty()) { TreeNode<T>* top=q.front(); //2.1如果该节点两个孩子都有，则直接pop if (top->left&&top->right) { q.pop(); q.push(top->left); q.push(top->right); } //2.2如果该节点左孩子为空，右孩子不为空，则一定不是完全二叉树 if (top->left==NULL&&top->right) { return false; } //2.3如果该节点左孩子不为空，右孩子为空或者该节点为叶子节点，则该节点之后的所有结点都是叶子节点 if ((top->left&&top->right==NULL)||(top->left==NULL&&top->right==NULL)) { q.pop(); //则该节点之后的所有结点都是叶子节点 while (!q.empty()) { top=q.front(); if (top->left==NULL&&top->right==NULL) { q.pop(); } else { return false; } } return true; } } return true; } ----------
//满二叉树 void test1() { // 1 // 2 3 // 4 5 6 7 TreeNode<int>* node1=new TreeNode<int>(1); TreeNode<int>* node2=new TreeNode<int>(2); TreeNode<int>* node3=new TreeNode<int>(3); TreeNode<int>* node4=new TreeNode<int>(4); TreeNode<int>* node5=new TreeNode<int>(5); TreeNode<int>* node6=new TreeNode<int>(6); TreeNode<int>* node7=new TreeNode<int>(7); node1->left=node2; node1->right=node3; node2->left=node4; node2->right=node5; node3->left=node6; node3->right=node7; cout<<IsComplete<int>(node1)<<endl; }
//二叉树为空 void test2() { cout<<IsComplete<int>(NULL)<<endl; } //3.二叉树不为空，也不是满二叉树，遇到一个结点左孩子为空，右孩子不为空 void test3() { // 1 // 2 3 // 4 5 7 TreeNode<int>* node1=new TreeNode<int>(1); TreeNode<int>* node2=new TreeNode<int>(2); TreeNode<int>* node3=new TreeNode<int>(3); TreeNode<int>* node4=new TreeNode<int>(4); TreeNode<int>* node5=new TreeNode<int>(5); TreeNode<int>* node7=new TreeNode<int>(7); node1->left=node2; node1->right=node3; node2->left=node4; node2->right=node5; node3->right=node7; cout<<IsComplete<int>(node1)<<endl; }
//4.二叉树不为空，也不是满二叉树，遇到叶子节点,则该叶子节点之后的所有结点都为叶子节点 void test4() { // 1 // 2 3 // 4 5 TreeNode<int>* node1=new TreeNode<int>(1); TreeNode<int>* node2=new TreeNode<int>(2); TreeNode<int>* node3=new TreeNode<int>(3); TreeNode<int>* node4=new TreeNode<int>(4); TreeNode<int>* node5=new TreeNode<int>(5); node1->left=node2; node1->right=node3; node2->left=node4; node2->right=node5; cout<<IsComplete<int>(node1)<<endl; } //4.二叉树不为空，也不是满二叉树，遇到左孩子不为空，右孩子为空的结点，则该节点之后的所有结点都为叶子节点 void test5() { // 1 // 2 3 // 4 5 6 TreeNode<int>* node1=new TreeNode<int>(1); TreeNode<int>* node2=new TreeNode<int>(2); TreeNode<int>* node3=new TreeNode<int>(3); TreeNode<int>* node4=new TreeNode<int>(4); TreeNode<int>* node5=new TreeNode<int>(5); TreeNode<int>* node6=new TreeNode<int>(6); node1->left=node2; node1->right=node3; node2->left=node4; node2->right=node5; node3->left=node6; cout<<IsComplete<int>(node1)<<endl; } int main() { test1(); /*test2();*/ /*test3();*/ /*test4();*/ /*test5();*/ return 0; } --------------------- 作者：gogogo_sky 来源： 原文：https://blog.csdn.net/gogogo_sky/article/details/76223384 版权声明：本文为博主原创文章，转载请附上博文链接！
