二叉树

概念

定义

每个节点最多有两个子节点的树

分类

• 完全二叉树：除最后一层，每层节点都满，最后一层节点从左到右连续
• 满二叉树：非叶子节点必有2个子节点
• 平衡二叉树：任一节点的左右子树高度差不超过1
• 二叉搜索树：左子树节点值小于父节点，右子树节点值大于父节点
• 二叉线索树：利用空指针存储前驱后继信息的二叉树

性质

变量定义

• $m$叉树
• 高度$h$
• 节点总数$n$，各节点度数$n_i$
• 编号为$i$的节点$a_i$

公式

• $n_i \leq 2^i$
• $n \leq 2^h - 1$
• 叶子节点数 = 非叶子节点数 + 1
• $a_i \rightarrow left = a_{2i}$
• $a_i \rightarrow right = a_{2i+1}$
• $a_i \rightarrow parent = a_{\frac{i}{2}}$

二叉树存储

二叉树的存储方式有两种

• 顺序存储

适用于完全二叉树

• 链式存储（或数组模拟）

适用于一般二叉树

顺序存储

数组存储二叉树节点

• 根节点存在$a[1]$
• 左子节点在$a[2i]$
• 右子节点在$a[2i+1]$
• 父节点在$a[i/2]$

空节点可以用特殊值（如-1）表示

int tree[100]; // 假设二叉树最多有99个节点
// 初始化数组，-1表示空节点
for(int i = 0; i < 100; i++) tree[i] = -1;
// 插入节点（以第8号位置为例）
tree[8] = 10; // 根节点
tree[8/2] = 10; // 父节点
tree[8*2] = 5;  // 左子节点
tree[8*2+1] = 15; // 右子节点

链式存储

链表存储，每个节点包含数据和左右指针 也可以再加入父指针以方便访问父节点

struct Node {
    int data;
    Node* left;
    Node* right;
    Node* parent; // 可选
    Node(int val, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr)
        : data(val), left(l), right(r), parent(p) {}
};
void linkedBT(){
    Node* root = new Node(10); // 根节点
    root->parent = root; // 根节点的父节点指向自己或nullptr表示无父节点
    root->left = new Node(5, root);// 左子节点
    root->right = new Node(15, root);// 右子节点
}

数组模拟的链式存储

用数组模拟链式存储，每个节点包含数据和左右子节点的索引

适合节点数较少且不连续的二叉树

静态数组实现

struct Node {
    int data;
    int left; 
    int right;
    int parent; // 可选
    Node(int val = -1, int p = -1, int l = -1, int r = -1)
        : data(val), left(l), right(r), parent(p) {}
};
int idx = 0; // 全局索引，模拟节点分配
// 插入节点函数，返回新节点的索引
int add(Node a[], int val, int parent = -1){
    idx++;
    a[idx] = Node(val, parent);
    return idx;
}
Node a[100]; // 假设二叉树最多有99个节点
// 初始化数组，默认-1表示空节点
for(int i = 0; i < 100; i++) a[i] = Node();
// 插入节点（以第8号位置为例）
int rootI = add(a, 10); // 根节点
a[rootI].parent = rootI; // 根节点的父节点指向自己或-1表示无父节点
a[rootI].left = add(a, 5, rootI); // 左子节点
a[rootI].right = add(a, 15, rootI); // 右子节点

vector实现

struct Node {
    int data;
    int left; 
    int right;
    int parent; // 可选
    Node(int val = -1, int p = -1, int l = -1, int r = -1)
        : data(val), left(l), right(r), parent(p) {}
};
int add(vector<Node>& tree, int val, int parent = -1){
    tree.emplace_back(val, parent);
    // 新节点索引位置在vector末尾
    return tree.size() - 1; 
}
vector<Node> tree; // 用vector存储节点
tree.reserve(100); // 预留空间，假设二叉树最多有99个节点
// 插入节点（以第8号位置为例）
int rootI = add(tree, 10); // 根节点
tree[rootI].parent = rootI; // 根节点的父节点指向自己或-1表示无父节点
tree[rootI].left = add(tree, 5, rootI); // 左子节点
tree[rootI].right = add(tree, 15, rootI); // 右子节点

二叉树遍历

常见遍历方式有4种

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前三者都是dfs递归（或栈）实现 最后一种是bfs队列实现

前序遍历

$根节点 \rightarrow 左子树 \rightarrow 右子树$

void preOrder(TreeNode* root){
    // 递归出口
    if(root == nullptr) return;
    // 访问根节点
    cout << root->val << ' ';
    // 访问左子树
    preOrder(root->left);
    // 访问右子树
    preOrder(root->right);
}

中序遍历

$左子树 \rightarrow 根节点 \rightarrow 右子树$

void inOrder(TreeNode* root){
    // 递归出口
    if(root == nullptr) return;
    // 访问左子树
    inOrder(root->left);
    // 访问根节点
    cout << root->val << ' ';
    // 访问右子树
    inOrder(root->right);
}

后序遍历

$左子树 \rightarrow 右子树 \rightarrow 根节点$

void postOrder(TreeNode* root){
    // 递归出口
    if(root == nullptr) return;
    // 访问左子树
    postOrder(root->left);
    // 访问右子树
    postOrder(root->right);
    // 访问根节点
    cout << root->val << ' ';
}

层序遍历

按层次从上到下、从左到右访问树的节点

void levelOrder(TreeNode* root){
    // 空树直接返回
    if(root == nullptr) return;
    // 队列管理候选节点
    queue<TreeNode*> q;
    // 根节点入队
    q.push(root);
    // 当队列不空时，持续访问节点
    while(!q.empty()){
        // 访问队首节点
        TreeNode* node = q.front();
        cout << node->val << ' ';
        // 出队
        q.pop();
        // 左右子节点入队
        if(node->left) q.push(node->left);
        if(node->right) q.push(node->right);
    }
}

二叉树建立

根据不同序列确定方式不同

• 层序：只能确定根节点（第一个节点）
• 先序：只能确定根节点（第一个节点）
• 后序：只能确定根节点（最后一个节点）
• 中序：无法确定，但知道根可划分左右子树

因此通常用 $中序+其他$ 来确定二叉树结构

先序+中序

1. 先序第一个节点为根节点
2. 在中序中找到根节点位置，划分左右子树
3. 递归构建左右子树

Node* preBuild(
    int pre[], int in[],
    int pl, int pr, 
    int il, int ir
    ) {
    // 递归出口
    if(pl > pr || il > ir) return nullptr;
    // 创建新根节点
    Node* root = new Node(pre[pl]);
    // 在中序中找到根节点位置
    int rootI = il;
    while(in[rootI] != root->val) rootI++;
    // 计算左子树大小
    int lSize = rootI - il;
    // 递归构建左右子树
    root->left = preBuild(
        pre, in,
        // 左子树在前半部分
        pl + 1, pl + lSize,
        il, rootI - 1
    );
    root->right = preBuild(
        pre, in,
        // 右子树在后半部分
        pl + lSize + 1, pr,
        rootI + 1, ir
    );
    return root;
}

后序+中序

1. 后序最后一个节点为根节点
2. 在中序中找到根节点位置，划分左右子树
3. 递归构建左右子树

Node* postBuild(
    int post[], int in[],
    int pl, int pr, 
    int il, int ir
    ) {
    // 递归出口
    if(pl > pr || il > ir) return nullptr;
    // 创建新根节点
    Node* root = new Node(post[pr]);
    // 在中序中找到根节点位置
    int rootI = il;
    while(in[rootI] != root->val) rootI++;
    // 计算左子树大小
    int lSize = rootI - il;
    // 递归构建左右子树
    root->left = postBuild(
        post, in,
        // 左子树在前半部分
        pl, pl + lSize - 1,
        il, rootI - 1
    );
    root->right = postBuild(
        post, in,
        // 右子树在后半部分
        pl + lSize, pr - 1,
        rootI + 1, ir
    );
    return root;
}

层序+中序

1. 中序中取在层序中最靠前的节点为根节点
2. 在中序中找到根节点位置，划分左右子树
3. 递归构建左右子树

Node* levelBuild(
    int lev[], int in[]， int levn,
    int il, int ir
    ) {
    // 递归出口
    if(il > ir) return nullptr;
    // 在中序中找到层序中最靠前的节点位置
    int rootLevI = levn, rootInI = il;
    // 遍历层序
    for(int i = 0;i < levn;i++){
        // 遍历中序
        for(int j = il;j <= ir;j++){
            // 寻找匹配且位置最靠前的节点
            if(lev[i] == in[j]){
                if(i < rootLevI){
                    // 更新在层序和中序中的位置
                    rootLevI = i;
                    rootInI = j;
                }
                break;
            }
        }
    }
    // 创建新根节点
    Node* root = new Node(in[rootI]);
    // 递归构建左右子树
    root->left = levelBuild(
        lev, in, levn,
        // 左子树在前半部分
        il, rootInI - 1
    );
    root->right = levelBuild(
        lev, in, levn,
        // 右子树在后半部分
        rootInI + 1, ir
    );
    return root;
}