第十章 ALDS1_9_A:Complete Binary Tree 完全二叉树

知识点

• 完全二叉树:二叉树的叶结点深度最大差距为1，最下层叶结点都集中在该层最左边的若干位置。
  
  • 树高是log2n
  • 最下层的叶结点都是从左往右满满得集中在左侧且中间没有空置的。
• 满二叉树:叶结点的深度全部相同，对于每个结点，要么有两个子结点，要么是叶结点。
  
  • 对于n层的满二叉树（从1开始），整个树有2n−1个结点。
  • 要么是叶结点，要么是含有两个子结点的内部结点
  • 满二叉树一种比较特别的完全二叉树

• 二叉堆：一棵完全二叉树的各结点的键值和一个数组的各元素的对应 。二叉堆有最大堆和最小堆，其结点的键值小于等于（大于等于）其父结点的键值。
  
  • 当知道一个结点的下标i，则通过floor(i/2)，2*i, 2*i +1得出其父结点、左子结点、右子结点。
    
-

问题链接

ALDS1_9_A:Complete Binary Tree

问题内容

输出二叉堆各结点的信息，求出各结点的父结点、左子结点、右子结点。

思路

根据二叉堆的性质去求即可

代码

#include <iostream>
#include <cstdio>
using namespace std;

// 分别求出结点i的父结点，左子结点、右子结点
int parent(int i) { return i / 2; }
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
int main()
{
    int H[300];
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &H[i]);

    for (int i = 1; i <= n; i++) {
        printf("node %d: key = %d, ", i, H[i]);
        if (parent(i) >= 1)
            printf("parent key = %d, ", H[parent(i)]);
        if (left(i) <= n) 
            printf("left key = %d, ", H[left(i)]);
        if (right(i) <= n)
            printf("right key = %d, ", H[right(i)]);
        printf("\n");
    }
    return 0;
}