D : DS查找—二叉树平衡因子_no6.(20220101): 1.下面程序段的功能是建立二叉树的算法,请在下划线处填上

D : DS查找—二叉树平衡因子

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 16     Solved: 16    
1

题目描述

二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。

–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求 输入 测试次数t

每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。

输出

对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）

样例输入

2
6 ABC00D
24 ABCD0EF0000H00000000000I

样例输出
B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2

#include<iostream>
using namespace std;

int get_height(char arr[],int n){
	if(arr[n] == '0') return 0;
	return get_height(arr,n*2+1)>get_height(arr,n*2+2) ? get_height(arr,n*2+1) + 1: get_height(arr,n*2+2) + 1;
}

void print(char *arr,int n){
	if(arr[n] == '0') return ;
	print(arr,n*2+1);
	print(arr,n*2+2);
	cout<<arr[n]<<" "<<get_height(arr,n*2+1) - get_height(arr,n*2+2)<<endl;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		char *arr;
		int n;
		cin>>n;
		int a = 2;
		while(a/2 < n)a*=2;
		arr = new char[a];
		for(int i = 0; i < n; i++)cin>>arr[i];
		for(int i = n; i < a; i++)arr[i] = '0';
		print(arr,0);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31