已知一棵非空二叉树结点的数据域为不等于0的整数,请编写程序找出该二叉树中叶结点数据值之和最大的层。
输入格式:
输入为一组用空格间隔的整数,个数不超过100个,表示带空指针信息的二叉树先根序列。
输出格式:
输出为一个整数,表示叶结点数据值之和最大的层,如果存在多个满足条件的层,则输出最下面一层。
输入样例1:
1 2 0 0 3 0 0
输出样例1
1
输入样例2:
1 -2 0 0 3 -1 0 0 -1 0 0
输出样例2:
2
思路:根据前序序列创建树;
递归求每一层叶子节点的和,用一个数组存每一层的和,数字下标对应第几层;
遍历数组,找出最大值对应的那个下标。
#include<iostream>
#include<stdlib.h>
using namespace std;
int b[100]={0};//用来存每一层叶子结点的和
//定义结点
typedef struct BiTreeNode
{
int data;
struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*LinkBiTreeNode;
//创建一棵树:只根据前序序列创建
LinkBiTreeNode CreateBiTree1(){
int Data;
LinkBiTreeNode node;
scanf("%d",&Data);
if (Data == 0) {
node = NULL;
}
else{
node = (LinkBiTreeNode)malloc(sizeof(BiTreeNode));
node->data = Data;
node->lchild = CreateBiTree1();
node->rchild =CreateBiTree1();
}
return node;
}
int sum=0;
int ii=1;
//开始最重要的工作,求叶子结点的和的最大值那层
void P( LinkBiTreeNode BT ){
if(BT){
if(BT->lchild==NULL&&BT->rchild==NULL)
b[ii]+=BT->data;
P(BT->lchild);
P(BT->rchild);
if(BT->lchild!=NULL&&BT->rchild!=NULL)ii++;
/*这句代码的位置放得很关键!反正递归也就是那几句话,关于叶子结点就是离不开这句if(BT->lchild!=NULL&&BT->rchild!=NULL),改改就成。所以关键就是这句代码放的位置*/
}
return ;
}
//排序搜索出最大值,对应的下标就是第几层
int compare(int *a,int k){
int i, j, temp=a[0],l=0;
for (j = 1; j < k ; j++)
{
if(temp<=a[j]){
temp = a[j];
l=j;}
}
return l;
}
int main(){
LinkBiTreeNode T = NULL;
T = CreateBiTree1();
if(T->lchild==NULL&&T->rchild==NULL){cout<<"0";return 0;}
P(T);
int l= compare(b,ii);
cout<<l<<endl;
return 0;
}
结果如下:
如有不足,欢迎指正!
祝大家都能拿满分!