二叉树

思路

模板

C++模板

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
/*
数组模拟二叉树
如果以存储起点为1那么：
如果2^i<n那么说明有左节点,如果2^i+1<n那么说明有右节点,i代表的是度，n代表总体的长度,该度的最后一位计算就是2^(i+1)-1;
比如说你现在的度是1那么度为2的最后一位就是在数组2^(1+1)-1=3当中
如果以存储起点为0那么：
如果2^i-1<n那么说明有左节点,如果2^i<n那么说明有右节点,i代表的是度,n代表总体的长度，该度的最后一位计算就是2*(i+1)-2;
比如说你现在的度是1，那么度为2的最后一位就是在数组2^(1+1)-2=2当中

<和<=的问题要看你是怎么存储的如果是从1开始存储那么就要取<=n如果是从0开始存储那么就要取<
度必须从1开始因为如果没有二叉树必须要有一个为起点
*/

#include <iostream>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int a[N];

/// @brief 寻找完全二叉树的总共的度
/// @param n 总体的长度
/// @param dept 度
/// @return 是完全二叉树的总共的度
int find(int n, int dept)
{
    for (int i = 2; i <= n; i++)
    {
        // 找到了最后一位那么递增一位度
        if (pow(2, dept + 1) - 1 == i)
            dept++;
    }

    return dept;
}

/// @brief 输出树里面的数
/// @param n 总体的长度
/// @param dept 度
void findTree(int n, int dept)
{
    if (a[dept])
        cout << a[dept] << " ";
    if (a[dept * 2] && 2 * dept <= n)
        findTree(n, 2 * dept);
    if (a[dept * 2 + 1] && 2 * dept + 1 <= n)
        findTree(n, 2 * dept + 1);
}

int main()
{
    //以下是测试集
    int n;
    cin >> n;

    a[1] = 1;
    for (int i = 2; i <= n; i++)
        a[i] = i;

    findTree(n, 1);
    find(n, 1);
}