完全二叉树的判定（中南大学机试习题）

完全二叉树的判定查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb利用先序递归遍历算法创建二叉树并判断该二叉树是否为完全二叉树。完全二叉树只能是同深度的满二叉树缺少最后一层倒数连续个叶子结点。先序递归遍历建立二叉树的方法为按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符#时表示该结点不需要创建否则创建该结点。最后判断创建完成的二叉树度是否为完全二叉树。需要注意输入数据序列中的#字符和非#字符的序列及个数关系这会最终决定创建的二叉树的形态。输入输出格式输入描述:输入为接受键盘输入的由大写英文字符和#字符构成的一个字符串用于创建对应的二叉树。输出描述:对应的二叉树是否为完全二叉树的判断结果。若是输出Y否则输出N。输入输出样例输入样例#:复制A## ABC#### AB##C## ABCD###EF##G### A##B## ABC##D##EG###输出样例#:复制Y N Y N Y Y题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode *left; struct TreeNode *right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; int pos; TreeNode* bulidTree(string str){ if(pos str.size()){//没字符了 return NULL; } if(str[pos] #){//是空节点 pos ; return NULL; } TreeNode* root new TreeNode(str[pos]); pos ; root-left bulidTree(str); root-right bulidTree(str); return root; } void LevelOrder(TreeNode* root){ if(root NULL){ coutYendl; return; } queueTreeNode*s; bool total true; s.push(root); while(!s.empty()){ TreeNode* p s.front(); s.pop(); if(p NULL){//是空的就标记 total false; } else{ if(total false){ coutNendl; return; } s.push(p-left); s.push(p-right); } } coutYendl; return; } int main() { int n; string pre, in; string str; while(cinstr){ pos 0; TreeNode* root bulidTree(str); LevelOrder(root); } }