数据结构作业-判断是否完全二叉树

原答案是错误的，无法判断少了一个左节点的情况，所以我又想到了一种方法，对节点编号，采用线段树的存储思想，根节点编号为1，如果是左子树，编号为根节点*2，右子树编号为根节点*2+1，然后层序遍历，如果遍历到的数字不是上一个数字+1，那么就不是完全二叉树，否则是完全二叉树。

Code

#include <bits/stdc++.h>
#define Pair pair<node*,int>
#define ll long long
using namespace std;
struct node
{
	node* left;
	node* right;
}*tree[1005], * root;
int deep[1005], cnt;
//初始化建树
void Init()
{
	for (int i = 0; i < 1005; i++)
	{
		tree[i] = (node*)malloc(sizeof(node));
		tree[i]->left = NULL;
		tree[i]->right = NULL;
	}
	root = (node*)malloc(sizeof(node));
	root = tree[1];
	root->left = tree[2];
	root->right = tree[3];
	tree[2]->left = tree[4];
	tree[2]->right = tree[5];
	tree[3]->left = tree[6];
	tree[3]->right = tree[7];
	tree[4]->left = tree[8];
	tree[4]->right = tree[9];
	tree[5]->left = tree[10];
}
//广度优先搜索
bool Bfs(node* root)
{
	queue<Pair>q;
	q.push(Pair{ root,1 });
	int flag = 0;
	while (!q.empty())
	{
		Pair temp = q.front();
		q.pop();
		if (temp.second == flag + 1)
			flag++;
		else
			return false;
		if (temp.first->left == NULL && temp.first->right == NULL)
			deep[cnt++] = temp.second;
		if (temp.first->left != NULL)
			q.push(Pair{ temp.first->left ,temp.second * 2 });
		if (temp.first->right != NULL)
			q.push(Pair{ temp.first->right ,temp.second * 2 + 1 });
	}
	return true;
}
int main()
{
	Init();
	puts(Bfs(root) ? "Yes" : "No");
}

-------------------

什么是完全二叉树

完全二叉树

方法1

深度优先搜索，先搜左子树，再搜右子树，当遍历的节点是叶子节点时，依此将叶子节点的深度存入数组，最后判断数字是不是形如  或者形如 ，如果是，那么这棵树就是完全二叉树，否则，不是完全二叉树。以下面的树为例，代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
	node* left;
	node* right;
}*tree[1005], *root;
int deep[1005], cnt;
//初始化建树
void Init()
{
	for (int i = 0; i < 1005; i++)
	{
		tree[i] = (node*)malloc(sizeof(node));
		tree[i]->left = NULL;
		tree[i]->right = NULL;
	}
	root = (node*)malloc(sizeof(node));
	root = tree[1];
	root->left = tree[2];
	root->right = tree[3];
	tree[2]->left = tree[4];
	tree[2]->right = tree[5];
	tree[3]->left = tree[6];
	tree[3]->right = tree[7];
	tree[4]->left = tree[8];
	tree[4]->right = tree[9];
	tree[5]->left = tree[10];
}
//深度优先搜索找叶子
void Dfs(node* root, int dep)
{
	if (root->left == NULL && root->right == NULL)
	{
		deep[cnt++] = dep;
		return;
	}
	if (root->left != NULL)
		Dfs(root->left, dep + 1);
	if (root->right != NULL)
		Dfs(root->right, dep + 1);
}
//输出deep数组
void Print()
{
	for (int i = 0; i < cnt; i++)
		printf("%d%c", deep[i], i == cnt - 1 ? '\n' : ' ');
}
//判断是否完全二叉树
bool Check()
{
	int f = 0;
	for (int i = 1; i < cnt; i++)
	{
		if (deep[i - 1] != deep[i])
		{
			if (deep[i - 1] == deep[i] + 1)
				f++;
			else
				return false;
		}
	}
	if (f <= 1)
		return true;
	return false;
}
int main()
{
	Init();
	Dfs(root, 1);
	Print();
	puts(Check() ? "Yes" : "No");
}

方法2：

广度优先搜索，一层一层搜，当遍历的节点是叶子节点时，依此将叶子节点的深度存入数组，最后判断数字是不是形如  或者形如 ，如果是，那么这棵树就是完全二叉树，否则，不是完全二叉树。

以上面的树为例代码如下：

#include <bits/stdc++.h>
#define Pair pair<node*,int>
#define ll long long
using namespace std;
struct node
{
	node* left;
	node* right;
}*tree[1005], *root;
int deep[1005], cnt;
//初始化建树
void Init()
{
	for (int i = 0; i < 1005; i++)
	{
		tree[i] = (node*)malloc(sizeof(node));
		tree[i]->left = NULL;
		tree[i]->right = NULL;
	}
	root = (node*)malloc(sizeof(node));
	root = tree[1];
	root->left = tree[2];
	root->right = tree[3];
	tree[2]->left = tree[4];
	tree[2]->right = tree[5];
	tree[3]->left = tree[6];
	tree[3]->right = tree[7];
	tree[4]->left = tree[8];
	tree[4]->right = tree[9];
	tree[5]->left = tree[10];
}
//深度优先搜索找叶子
void Bfs(node* root)
{
	queue<Pair>q;
	q.push(Pair{ root,1 });
	while (!q.empty())
	{
		Pair temp = q.front();
		q.pop();
		if (temp.first->left == NULL && temp.first->right == NULL)
			deep[cnt++] = temp.second;
		if (temp.first->left != NULL)
			q.push(Pair{ temp.first->left ,temp.second + 1 });
		if (temp.first->right != NULL)
			q.push(Pair{ temp.first->right ,temp.second + 1 });
	}
}
//输出deep数组
void Print()
{
	for (int i = 0; i < cnt; i++)
		printf("%d%c", deep[i], i == cnt - 1 ? '\n' : ' ');
}
//判断是否完全二叉树
bool Check()
{
	int f = 0;
	for (int i = 1; i < cnt; i++)
	{
		if (deep[i - 1] != deep[i])
		{
			if (deep[i - 1] + 1 == deep[i])
				f++;
			else
				return false;
		}
	}
	if (f <= 1)
		return true;
	return false;
}
int main()
{
	Init();
	Bfs(root);
	Print();
	puts(Check() ? "Yes" : "No");
}