当前位置:   article > 正文

问题 D: DS查找—二叉树平衡因子(不一样的新做法哦)_d. ds查找—二叉树平衡因子

d. ds查找—二叉树平衡因子


题目

问题 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;
}
  • 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

附网上常见的该题做法,比对学习

源码链接:


#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);
    }
}
  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

TO BE continue
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/766254
推荐阅读
相关标签
  

闽ICP备14008679号