Question

已知一颗二叉链表表示二叉树T ，编写函数，判断T是否为完全二叉树。先

已知一颗二叉链表表示二叉树T ，编写函数，判断T是否为完全二叉树。先给出算法思想，再写出程序代码。
不要程序代码。要书面伪代码

Answer 1

问题：判断二叉树是否为完全二叉树。完全二叉树的定义是，前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。以3层二叉树为例，以下情况为完全二叉树：[方法一]这个问题的描述已经提示了解法，采用广度优先遍历，从根节点开始，入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。这个方法需要遍历整棵树，复杂度为O(N)，N为节点的总数。//二叉树结点定义typedefstructNode{intdata;structNode*left;structNode*right;}Node;//实现广度遍历需要队列Queuequeue;//第n层最右节点标志boolleftMost=false;boolProcessChild(Node*child){if(child){if(!leftMost){queue.push(child);}else{returnfalse;}}else{leftMost=true;}returntrue;}boolIsCompleteBinaryTree(Node*root){//空树也是完全二叉树if(!root)returntrue;//首先根节点入队列queue.push(root);while(!queue.empty()){Node*node=queue.pop();//处理左节点if(!ProcessChild(node->left))returnfalse;//处理右节点if(!ProcessChild(node->right))returnfalse;}//广度优先遍历完毕，此乃完全二叉树returntrue;}[方法二]根据完全二叉树的定义，左边的深度>=右边的深度。从根节点开始，分别沿着最左最右分支下去，找到最左和最右的深度。如果左边比右边深1，再分别检查以左儿子和右儿子为根的两根树。有点递归的感觉了。[Tobecontinued]