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

简介: 这篇文章介绍了如何计算二叉树的平衡因子,并提供了C++代码实现,用于根据二叉树的数组存储形式,计算并输出每个节点的平衡因子。

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

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

题目描述

二叉树用数组存储,将二叉树的结点数据依次自上而下,自左至右存储到数组中,一般二叉树与完全二叉树对比,比完全二叉树缺少的结点在数组中用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;
}
相关文章
|
6月前
|
机器学习/深度学习
【每日一题Day364】LC2003每棵子树内缺失的最小基因值 | dfs
【每日一题Day364】LC2003每棵子树内缺失的最小基因值 | dfs
54 0
|
存储 C语言 C++
问题 D: DS查找—二叉树平衡因子(不一样的新做法哦)
问题 D: DS查找—二叉树平衡因子(不一样的新做法哦)
|
6月前
|
Java
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
62 0
|
6月前
|
C++ 容器
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
|
6月前
|
算法 测试技术 C++
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
|
5月前
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
68 1
|
6月前
|
存储 Java
高效删除链表倒数节点最优实现
要删除链表的倒数第 n 个节点,并返回链表的头节点,我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针:快指针和慢指针。
|
算法 C语言
【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法【上】
文章目录 一、二叉数的结构体 二、构建二叉树,供后续测试使用 三、二叉树销毁 四、构建节点 五、二叉树的高度: 1.代码: 2.测试结果: 二叉树节点个数 1.代码: 2.测试结果:
|
算法 DataX C语言
【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法【下】
六、二叉树叶子节点个数 1.代码: 2.测试结果: 七、二叉树第k层节点个数 1.代码: 2.测试结果: 八、二叉树查找值为x的节点 1.代码: 2.测试结果: 九、判断二叉树是否是完全二叉树 1.代码: 2.测试结果: 十、补充:队列代码 Queue.h Queue.c
|
6月前
|
机器学习/深度学习 人工智能 算法
【树】【异或】【深度优先】【DFS时间戳】2322. 从树中删除边的最小分数
【树】【异或】【深度优先】【DFS时间戳】2322. 从树中删除边的最小分数