判断是否是完全二叉树和是否为满二叉树

struct Node { char data; Node *lchild,*rchild; Node(char _data) { data = _data; } };

是否为完全二叉树：

bool isCompleteBinaryTree(Node *root) { if(root == NULL) { return true; } queue<Node*>q; q.push(root); Node *p; //先用层次遍历二叉树,子树为NULL也进队列 while((p = q.front()) != NULL)//如果是完全二叉树，退出此循环后，后面的结点应该都是NULL {//因为本循环会在层次遍历到第一个NULL结点退出 q.push(p->lchild); q.push(p->rchild); q.pop(); } //如果不是完全二叉树，则队列里还有非NULL结点 while(q.empty() == false) //检查是否有非空结点 { p = q.front(); if(p != NULL) //有 { return false; } q.pop(); } return true; }

是否为满二叉树：

bool isFullBinaryTree(Node *root) { if(root->lchild != NULL && root->rchild != NULL) { return isFullBinaryTree(root->lchild) && isFullBinaryTree(root->rchild); } if(root->lchild == NULL && root->rchild != NULL) { return false; } else if(root->rchild && root->lchild != NULL) { return false; } else { return true; } }