一 问题
二 解题方法
采用二叉树的层次遍历，需要队列作为辅助，
如图所示，队列保存着层次遍历时二叉树结点的地址，Thislevel记录了当前层的结点数，Nextlevel记录了下一层结点数。当队列中每出一个结点，Thislevel必须减1，当前结点的左或右孩子入队，Nextlevel必须加1。当Thislevel为0时，说明二叉树的一层遍历结束，开始新的一层。
三 测试
四 代码
/*
* to judge whether a binary tree is a binary tree
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ElemType int
#define END -1
#define MAX 100
typedef struct BinNode {
ElemType data;
struct BinNode *left;
struct BinNode *right;
}BinNode;
int leaves[MAX];
typedef struct QueueNode {
struct BinNode *data;
struct QueueNode *next;
}QueueNode;
QueueNode *front, *rear;
void InQueue(struct BinNode *e) {
QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
if(!p) {
perror("memory error!
");
exit(EXIT_FAILURE);
}
p->data = e;
p->next = 0;
if(rear) rear->next = p;
rear = p;
if(!front) front = rear;
}
struct BinNode *DeQueue() {
if(!front) {
perror("the queue is empty!
");
exit(EXIT_FAILURE);
}
struct BinNOde *p = front->data;
QueueNode *r = front;
front = front->next;
free(r);
if(!front) rear = NULL;
return p;
}
int QueueEmpty() {
return front == NULL?1:0;
}
void CreateBinTree(BinNode **t) {
ElemType e;
if(scanf("%d", &e) != 1) {
perror("input error!
");
exit(EXIT_FAILURE);
}
if(e == END) return;
if(*t == NULL) {
*t = (BinNode *)malloc(sizeof(BinNode *));
(*t)->left = NULL;
(*t)->right = NULL;
(*t)->data = e;
}
CreateBinTree(&((*t)->left));
CreateBinTree(&((*t)->right));
}
void PreTranverse(BinNode *t) {
if(t) {
printf("%d
", t->data);
PreTranverse(t->left);
PreTranverse(t->right);
}
}
int JudgeRuleBinTree(BinNode *t) {
if(!t) return 1;
int level = 1; // the level of bintree
int thislevel; // the number of nodes in this level
int nextlevel; // the number of nodes in next level
int k = 0; // the number of leaves in bintree
int i, j;
BinNode *p;
InQueue(t);
thislevel = 1; // when the root node is added into the queue
nextlevel = 0;
while(!QueueEmpty()) {
p = DeQueue();
/*
* if a leaf occurs
*/
if(!p->left && !p->right) leaves[k++] = level;
thislevel--; // when a node is out from the queue
if(p->left) {
InQueue(p->left);
nextlevel++; // the children of current node
}
if(p->right) {
InQueue(p->right);
nextlevel++;
}
if(!thislevel) {
thislevel = nextlevel;
nextlevel = 0;
level++;
}
}
printf("the level of all the leaves in binary tree is:
");
for(i = 0;i < k;i++) printf("%d ", leaves[i]);
for(i = 0;i < k - 1;i++) {
for(j = i + 1;j < k;j++) {
if(fabs(leaves[i] - leaves[j]) != 0 && fabs(leaves[i] - leaves[j]) != 1) {
return 0;
}
}
}
return 1;
}
int main() {
BinNode *root = NULL;
CreateBinTree(&root);
PreTranverse(root);
if(JudgeRuleBinTree(root)) printf("
rule binary tree!
");
else printf("
NOT rule binary tree!
");
return 0;
}
五 编程体会
本题实际上是利用二叉树的层次遍历，关键是找到每个叶子节点的深度。为此，本人使用了thislevel和nextlevel这两个变量来记录层次变化情况。