这棵树是不是完全二叉树呢？它的每一层都满了，最后一层也只缺少最右边的节点？

本文共计595个文字，预计阅读时间需要3分钟。

什么是完全二叉树？对于深度为k的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称为完全二叉树。特点：所有的叶节点都出现在最后一层，且最后一层的节点都尽可能地靠左排列。

什么是完全二叉树？

对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

特点：所有的叶结点都出现在第k层或k-1层（层次最大的两层）。

对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1。

void LevelOrder(BiTree T) { BiTree Q[MAXSIZE]; BiTree p; int front,rear; front=rear=0; if(T==NULL) return 0; printf("%c",T->data); rear++; Q[rear]=T; while(rear!=front) { front=(front+1)%MAXSIZE; p=Q[front]; if(p->lchild!=NULL) { printf("%c",p->lchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->lchild; } if(p->rchild!=NULL) { printf("%c",p->rchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->rchild; } } }

如何判断层次遍历进行到了第几层？引入层次指针。

void fun2(BiTree T){ BiTree Q[MAXSIZE],p; int front,rear,layer,count,n; //layer层指针，count每层个数计数，n层次计数 front=rear=layer=count=0; if(!T) return; printf("%c",T->data); printf("layer-%d:%d\n",1,1); rear++; Q[rear]=T; layer++; n=1; while(rear!=front){ front=(front+1)%MAXSIZE; p=Q[front]; if(p->lchild!=NULL){ printf("%c",p->lchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->lchild; count++; } if(p->rchild!=NULL){ printf("%c",p->rchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->rchild; count++; } /*若没有front!=rear会多统计一个空层*/ if(front==layer&&front!=rear){ n++; printf("layer-%d:%d\n",n,count); layer=rear; count=0; } } putchar('\n'); }

判断是否为完全二叉树

对于完全二叉树，在层次遍历过程中，若某结点缺失了左孩子或右孩子，则其后继一定无孩子。

int fun(BiTree T) { BiTree Q[MAXSIZE]; BiTree p; int front,rear; front=rear=0; int flag=1;//标志到目前为止未发现缺失孩子的结点 if(T==NULL) return 0; printf("%c",T->data); rear++; Q[rear]=T; while(rear!=front) { front=(front+1)%MAXSIZE; p=Q[front]; if(p->lchild!=NULL) { printf("%c",p->lchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->lchild; } else flag=0; if(p->rchild!=NULL) { printf("%c",p->rchild->data); rear=(rear+1)%MAXSIZE; Q[rear]=p->rchild; } else flag=0; } return 1; }