使用层序遍历+队列实现该功能。每次都将队列的队头元素出队,将其左右孩子入队。同时判断出队元素是否等于要求的整数a,b。如果等于某个值,则将当前层数的值赋值给该元素所在层数。每次将该层的最后一个结点出队处理后将当前层数+1。最后判断a,b的层数是否修改过,然后返回相应结果。
2.定义结构体typedef struct BiNode { int data; struct BiNode* lchild; struct BiNode* rchild; } BiNode,*BiTree;3.函数实现
每次队头元素出队前先判断a,b是否都已经找到了,如果找到了那就返回层数的差值,否则就出队,继续寻找。
如果遍历完了该二叉树,说明要么只找到一个,要么一个都没找到(如果都找到了就会直接返回结果),因此进行判断并返回结果。
int check(BiTree T, int a, int b) { BiNode *Q[MAXSIZE]; BiNode *p; int front = -1, rear = -1; int level = 0,level1 = -1,level2 = -1,last = 0; if(!T) { printf("该二叉树为空!"); return -2; } Q[++rear] = T; while(front < rear) { if(level1 != -1 && level2 != -1) {//都找到时,返回层数差值 printf("数据:%d所在的层数为:%dn数据:%d所在的层数为:%dn",a,level1,b,level2); return level1 > level2 ? level1-level2 : level2-level1; } p = Q[++front];//队头元素出队 //左右孩子入队 if(p->lchild) { Q[++rear] = p->lchild; } if(p->rchild) { Q[++rear] = p->rchild; } //比较当前结点是否为a或b结点 if(p->data == a) { level1 = level+1; } if(p->data == b) { level2 = level+1; } if(last == front) {//遍历到该层最后一个结点 level++; last = rear; } } //只找到一个元素 if(level1 != -1 || level2 != -1) { return -1; } //两个都没找到 return -2; }4.测试结果
#include#include #define MAXSIZE 50 typedef struct BiNode { int data; struct BiNode* lchild; struct BiNode* rchild; } BiNode,*BiTree; int check(BiTree T, int a, int b) { BiNode *Q[MAXSIZE]; BiNode *p; int front = -1, rear = -1; int level = 0,level1 = -1,level2 = -1,last = 0; if(!T) { printf("该二叉树为空!"); return -2; } Q[++rear] = T; while(front < rear) { if(level1 != -1 && level2 != -1) {//都找到时,返回层数差值 printf("数据:%d所在的层数为:%dn数据:%d所在的层数为:%dn",a,level1,b,level2); return level1 > level2 ? level1-level2 : level2-level1; } p = Q[++front];//队头元素出队 //左右孩子入队 if(p->lchild) { Q[++rear] = p->lchild; } if(p->rchild) { Q[++rear] = p->rchild; } //比较当前结点是否为a或b结点 if(p->data == a) { level1 = level+1; } if(p->data == b) { level2 = level+1; } if(last == front) {//遍历到该层最后一个结点 level++; last = rear; } } //只找到一个元素 if(level1 != -1 || level2 != -1) { return -1; } //两个都没找到 return -2; } int main() { BiTree l1 = (BiTree)malloc(sizeof(BiNode)); BiNode *l2 = (BiNode *)malloc(sizeof(BiNode)); BiNode *l3 = (BiNode *)malloc(sizeof(BiNode)); BiNode *l4 = (BiNode *)malloc(sizeof(BiNode)); BiNode *l5 = (BiNode *)malloc(sizeof(BiNode)); BiNode *l6 = (BiNode *)malloc(sizeof(BiNode)); BiNode *l7 = (BiNode *)malloc(sizeof(BiNode)); l1->data = 1; l2->data = 2; l3->data = 3; l4->data = 4; l5->data = 5; l6->data = 6; l7->data = 7; l1->lchild = l2; l1->rchild = l3; l2->lchild = l4; l2->rchild = l5; l3->lchild = l6; l3->rchild = l7; l4->lchild = NULL; l4->rchild = NULL; l5->lchild = NULL; l5->rchild = NULL; l6->lchild = NULL; l6->rchild = NULL; l7->lchild = NULL; l7->rchild = NULL; int a = 2, b = 3; int result= check(l1, a, b); printf("结果为:%dn",result); return 0; }