매일 한 문제 Day 81

이 진 트 리 의 WPL 계산
묘사 하 다.
이 진 트 리 의 대역 권 경로 길이 (WPL) 는 이 진 트 리 의 모든 잎 노드 의 대역 권 경로 길이 의 합 이다.이 진 트 리 T 를 지정 하고 이 진 트 리 로 저장 합 니 다. 결점 구 조 는 left weight right 이 고 그 중에서 잎 결점 의 weight 도 메 인 은 이 결점 의 비 마이너스 가중치 를 저장 합 니 다.루트 를 T 의 루트 노드 를 가리 키 는 지침 으로 설정 하고 T 를 구 하 는 WPL 알고리즘 을 설계 하 십시오.
입력
여러 조 의 데 이 터 는 각 조 의 데이터 한 줄 로 이 진 트 리 의 우선 순위 서열 (서열 에서 요소 가 0 일 때 이 노드 가 비어 있 음 을 나타 내 고 두 요소 사 이 를 빈 칸 으로 구분 합 니 다).입력 이 0 이 하나 밖 에 없 을 때 입력 이 끝 납 니 다.
출력
각 그룹의 데 이 터 는 이 두 갈래 트 리 의 WPL 로 한 줄 씩 출력 합 니 다.
샘플 입력 1 

1 1 0 0 1 0 0
1 2 1 0 0 0 0
0

샘플 출력 1

2
2

해답: 입력 데이터 에 따라 밴드 권 이 진 트 리 를 만 들 고 깊이 는 모든 잎 결점 의 밴드 권 경로 길이 의 합 을 우선 검색 합 니 다.

#include
#include

typedef struct node
{
	int data;
	struct node *left,*right;
} TNode;

int x,count,flag,sum;

void Create(TNode *&T)
{
	scanf("%d",&x);
	count++;
	if(x==0 && count==1)
	{
		flag=1;
		return ;
	}
	else
	{
		if(x==0)
			T=NULL;
		else
		{
			T=(TNode *)malloc(sizeof(TNode));
			T->data=x;
			Create(T->left);
			Create(T->right);
		}
	}
}

void DFS(TNode *T,int k)
{
	if(T->left==NULL && T->right==NULL)
		sum+=(T->data*k);
	if(T->left)
		DFS(T->left,k+1);
	if(T->right)
		DFS(T->right,k+1);
}

int main()
{
	TNode *T;
	while(1)
	{
		flag=0;
		count=0;
		Create(T);
		if(flag)
			break;
		sum=0;
		DFS(T,0);
		printf("%d
",sum);
	}
	return 0;
}