二叉树层次遍历的应用--判断一颗二叉树是否为规则二叉树

一 问题

二 解题方法

采用二叉树的层次遍历，需要队列作为辅助，

如图所示，队列保存着层次遍历时二叉树结点的地址，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 100typedef 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!\n");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!\n");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!\n");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\n", t->data);PreTranverse(t->left);PreTranverse(t->right);}}int JudgeRuleBinTree(BinNode *t) {if(!t) return 1;int level = 1;   // the level of bintreeint thislevel;   // the number of nodes in this levelint nextlevel;   // the number of nodes in next levelint 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 queuenextlevel = 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 queueif(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:\n");        for(i = 0;i < k;i++) printf("%d\t", 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("\nrule binary tree!\n");else printf("\nNOT rule binary tree!\n");return 0;}

本题实际上是利用二叉树的层次遍历，关键是找到每个叶子节点的深度。为此，本人使用了thislevel和nextlevel这两个变量来记录层次变化情况。