文章目录
题目
问题 D: DS查找—二叉树平衡因子
题目描述
二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用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
提示
实现思路
百度出来的代码，千遍一律，都是先建树再求高度，诸如此类的。
但是，我转念一想，为什么做二叉树的就一定要建树，其实有时候题目给的往往就是一颗隐形的二叉树,比如说上面今天这一道题，要是你仔细看的话，一定会发现这个规律
可以发现要求的第i个节点的平衡因子，他的左子树的数组下标为2*i+1， 右子树为2*i+2 ，因此，我们完全可以不重新建树，就可以解出道题。
- 求深度的思路
利用dfs探到树的叶子节点，再回溯求深度。
代码
#include<iostream> using namespace std; int length; char *p; int dfs(int i){ if(i>=length || p[i]=='0') return 0; int l = dfs(2*i+1); int r = dfs(2*i+2); cout<<p[i]<<' '<<l-r<<endl; return max(l,r)+1; } int main() { int T; cin>>T; while(T--) { int n; cin>>n; length = n; p=new char[n]; for(int i=0;i<n;i++) cin>>p[i]; dfs(0); delete []p; } return 0; }
附网上常见的该题做法，比对学习
#include <iostream> using namespace std; class Bt{ private: char *t; //存输入的信息 int n; //长度 int *le; //存左子树深度 int *ri; //存右子树深度 public: Bt(){}; ~Bt(){}; void set_Bt(); void get_balance_factor(int k); void out_put(); void PostOrder(int k); }; void Bt::out_put() { for(int i=0;i<n;i++) { cout<<le[i]<<' '<<ri[i]<<endl; } } void Bt::set_Bt() { cin>>n; t=new char[n]; for(int i=0;i<n;i++) { cin>>t[i]; } le=new int[n]; ri=new int[n]; for(int i=0;i<n;i++) { le[i]=-1; ri[i]=-1; } } void Bt::get_balance_factor(int k) //求结点k的左右孩子的深度 { int left=k*2+1,right=k*2+2; if(left>=n) //若左右孩子都不存在，则深度都为0 { le[k]=0; ri[k]=0; } else { if(t[left]=='0') //若左孩子不存在，则深度为0 le[k]=0; else { get_balance_factor(left); //若左孩子存在，则递归求左孩子的左右子树的深度，然后取大的一个+1作为左子树的深度 le[k]=le[left]>ri[left] ? le[left]+1:ri[left]+1; } if(right>=n) ri[k]=0; else { if(t[right]=='0') //若右孩子不存在，则深度为0 ri[k]=0; else { get_balance_factor(right); //若右孩子存在，则递归求右孩子的左右子树的深度，然后取大的一个+1作为右子树的深度 ri[k]=le[right]>ri[right] ? le[right]+1:ri[right]+1; } } } } void Bt::PostOrder(int k) //后序输出平衡因子，平衡因子即为左子树深度减右子树深度 { if(k>=n || t[k]=='0') return ; int left=k*2+1,right=k*2+2; //取左右孩子的下标 PostOrder(left); //先输出左孩子的平衡因子 PostOrder(right); //后输出右孩子的平衡因子 cout<<t[k]<<' '<<le[k]-ri[k]<<endl; //最后输出自己的平衡因子 } int main() { int t; cin>>t; while(t--) { Bt temp; temp.set_Bt(); temp.get_balance_factor(0); // temp.out_put(); temp.PostOrder(0); } }
TO BE continue
