二叉树

BST.cpp

// 1. 二叉树第i层最多2^{i-1}个节点
// 2. 深度为k的二叉树最多右2^k-1个节点
// 3. 对于二叉树，设节点数为n, 有n0 + n1 + n2 = n; (*1)
// n = B + 1; // B 为分支数目
// n = n1 + 2*n2 + 1; (*2)
// 结合(*1)、(*2) 有 n0 = n2 + 1; (*3) 
// 如用二叉链表表示，空指针数为n+1, 由(*3)、(*1)易得2*n0 + n1 = n + 1;
// 4. 具有n个节点的完全二叉树的深度为floor(log_2n)+1

#include <bits/stdc++.h>
using namespace std;
const int maxn = int(1e6+7);
struct TreeNode {
    int idx;
    TreeNode *left;
    TreeNode *right;
    int color, key, p;
};
int cnt;
TreeNode* build() { //根据二叉树的严格先序遍历建树
    int v;scanf("%d", &v);
    TreeNode *T;
    if (!v)T = NULL;
    else {
        T = new TreeNode();
        T->key = v;
        T->idx = cnt++;
        T->left  = build();
        T->right = build();
    }
    return T;
}


void dfs(TreeNode *u) { //递归中序遍历

    if (u) {
        dfs(u->left);
        printf("%d ",u->key);
        dfs(u->right);
    }
}

void bfs(TreeNode *u) { //非递归中序遍历：左孩子一直入栈，输出无左孩子的节点，进入右孩子继续左孩子入栈
    stack<TreeNode *> stk;
    while (!stk.empty() || u) {
        while (u) {
            stk.push(u);
            u = u->left;
        }
        if (!stk.empty()) {
            u = stk.top();stk.pop();
            printf("%d ", u->key);
            u = u->right;
        }
    }
}
int main() {
    TreeNode *root = build();
    dfs(root); puts("");
    bfs(root);puts("");
    return 0;
}

// 6 5 2 0 0 5 0 0 7 0 8 0 0
// inorder: 2 5 5 6 7 8