二叉树按二叉链表形式存储,试编写一个判别二叉树是否是完全二叉树的算法
#include <iostream>
#include <queue>
typedef struct treenode{
char data;
struct treenode *left;
struct treenode *right;
}treenode,*ptreenode;
ptreenode buytreenode(char x)
{
ptreenode n=(ptreenode) malloc(sizeof (treenode));
n->data=x;
n->left= nullptr,n->right= nullptr;
return n;
}
ptreenode build_tree()//是完全二叉树
{
ptreenode root= buytreenode('A');
root->left= buytreenode('B');
root->right= buytreenode('C');
root->left->left= buytreenode('D');
root->left->right= buytreenode('E');
return root;
}
ptreenode build_tree2()//不是完全二叉树
{
ptreenode root= buytreenode('A');
root->left= buytreenode('B');
root->right= buytreenode('C');
root->left->left= buytreenode('D');
root->left->right= buytreenode('E');
root->left->left->right= buytreenode('F');
return root;
}
bool iscomplete(ptreenode root)
{
std::queue<ptreenode> tmp;
tmp.push(root);
while(!tmp.empty())
{
ptreenode f=tmp.front();
tmp.pop();
if(f) tmp.push(f->left),tmp.push(f->right);
else{
while(!tmp.empty())
{
if(tmp.front()== nullptr) tmp.pop();
else return false;
}
}
}
return true;
}
int main() {
ptreenode root=build_tree();
ptreenode root2=build_tree2();
if(iscomplete(root)) printf("It is a completed binary tree\n");
else printf("NO\n");
if(iscomplete(root2)) printf("It is a completed binary tree\n");
else printf("NO\n");
return 0;
}