【王道数据结构】【chapter5树与二叉树】【P158t6】

本文主要是介绍【王道数据结构】【chapter5树与二叉树】【P158t6】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树按二叉链表形式存储，试编写一个判别二叉树是否是完全二叉树的算法

#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;
}