用数组存二叉树

二叉树不一定非用指针，还能塞进一个数组，省事又好算。给节点从 1 开始编号：根是 1，它的左孩子是 2、右孩子是 3，再往下 2 的孩子是 4、5……规律是——编号 $i$ 的左孩子是 $2i$，右孩子是 $2i+1$，父亲是 $i/2$（整除）。位置一算就知道，不用存指针。

#include <iostream>
using namespace std;
int tree[16];
int main() {
    tree[1]=1; tree[2]=2; tree[3]=3;   // 根和它的两个孩子
    tree[4]=4; tree[5]=5;              // 2 号的左右孩子
    int i = 5;
    cout << i << " 号的父亲: " << tree[i/2] << " 号" << endl; // 2 号
    cout << "1 号左孩子: " << tree[1*2] << endl;              // 2
    return 0;
}

小纸条问：编号 5 的节点，父亲是几？用 $5/2=2$（整除去掉小数），所以父亲是 2 号。要注意编号从 1 开始（别从 0，那样乘 2 的公式就不成立了）；还有，如果树又细又长、缺胳膊少腿，中间会空出很多没用的格子，这种"稀疏"的树用数组存反而浪费。