二叉树的定义、性质与存储
从“每家最多两子”的家族分支，理解二叉树为什么是程序里最常用的树

#include <iostream>
using namespace std;

int main() {
    // 第 i 层最多 2^(i-1) 个结点；深度为 d 的二叉树最多 2^d - 1 个结点
    int level = 5;
    cout << "完全二叉树第 " << level << " 层最多 "
         << (1 << (level - 1)) << " 个结点" << endl;      // 16

    int depth = 4;
    cout << "深度为 " << depth << " 的二叉树最多 "
         << ((1 << depth) - 1) << " 个结点" << endl;      // 15
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n = 15;
    int k = 0;
    while ((1 << k) - 1 < n) k++;
    cout << "n=" << n << " 深度=" << k
         << " 是否满二叉树：" << (n == (1 << k) - 1 ? "是" : "否") << endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
struct TreeNode { int val; TreeNode *l, *r;
    TreeNode(int v) : val(v), l(nullptr), r(nullptr) {} };
int pos = 0;
TreeNode* build(const string a[], int n) {
    if (pos >= n) return nullptr;
    string s = a[pos++];
    if (s == "#") return nullptr;
    TreeNode* t = new TreeNode(stoi(s));
    t->l = build(a, n); t->r = build(a, n);
    return t;
}
void count(TreeNode* r, int& n0, int& n1, int& n2) {
    if (!r) return;
    int d = (r->l ? 1 : 0) + (r->r ? 1 : 0);  // 度：0 / 1 / 2
    if (d == 0) n0++; else if (d == 1) n1++; else n2++;
    count(r->l, n0, n1, n2);
    count(r->r, n0, n1, n2);
}
int main() {
    string a[] = {"1","2","4","#","#","5","#","#","3","#","6","#","#"};
    int n = sizeof(a) / sizeof(a[0]);
    TreeNode* root = build(a, n);
    int n0 = 0, n1 = 0, n2 = 0;
    count(root, n0, n1, n2);
    cout << "n0(叶子) = " << n0 << endl;
    cout << "n1(度为1) = " << n1 << endl;
    cout << "n2(度为2) = " << n2 << endl;
    cout << "性质3 验证：n0 = n2 + 1 -> " << n0 << " = " << n2
         << " + 1 " << (n0 == n2 + 1 ? "成立" : "不成立") << endl;
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    // 从 1 开始编号的顺序存储：双亲 = i/2，左孩子 = 2i，右孩子 = 2i+1
    int n = 20;              // 假设这棵完全二叉树一共有 20 个结点
    int i = 10;

    cout << "结点 " << i << " 的双亲下标 = " << i / 2 << endl;    // 5
    cout << "结点 " << i << " 的左孩子下标 = " << 2 * i;
    if (2 * i > n)
        cout << "（已经超过总结点数 " << n << "，其实不存在）";
    cout << endl;                                                 // 20
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n = 10;
    int k = (int)log2(n) + 1;
    cout << "深度 = " << k << " 是否满二叉树："
         << (n == (1 << k) - 1 ? "是" : "否") << endl;
    return 0;
}