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

超、凢脫俗 2023-10-04 14:38 12阅读 0赞

#### 文章目录 ####

*  题目
 *  实现思路
 *  代码
 *  附网上常见的该题做法，比对学习

--------------------

## 题目 ##

问题 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  
提示

--------------------

## 实现思路 ##

> 百度出来的代码，千遍一律，都是先建树再求高度，诸如此类的。

但是，我转念一想，为什么做二叉树的就一定要建树，其实有时候题目给的往往就是一颗隐形的二叉树,比如说上面今天这一道题，要是你仔细看的话，一定会发现这个规律

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4_size_16_color_FFFFFF_t_70]  
 可以发现要求的第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;
    }

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

[源码链接：][Link 1]

#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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210527235104954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/weixin_40673608/article/details/84792456