树

二叉树遍历

层序遍历：利用队列

/**
 * 利用队列实现层序遍历
 */
vector<int> levelOrder(TreeNode *root) {
    queue<TreeNode *> queue;
    // 存储节点的值
    vector<int> valSet;
    // 头节点入队
    queue.push(root);
    // 队列非空
    while (!queue.empty()) {
        // 只获取队头节点，并不出队
        TreeNode *node = queue.front();
        // 出队
        queue.pop();
        // 元素值记录
        valSet.push_back(node->val);
        // 左孩子非空入队
        if (node->left != nullptr) queue.push(node->left);
        // 右孩子非空入队
        if (node->right != nullptr) queue.push(node->right);
    }
    return valSet;
}

深度优先遍历（利用递归）:

//
// Created by zhou on 2023/10/10.
//
#include "../utils/common.h"

vector<int> vec;

/**
 * 前序：根-左-右
 */
void preOrder(TreeNode *root) {
    if (root == nullptr) return;
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

/**
 * 中序：左-根-右
 */
void inOrder(TreeNode *root) {
    if (root == nullptr) return;
    inOrder(root->left);
    vec.push_back(root->val);
    inOrder(root->right);
}

/**
 * 后序：左-右-根
 */
void postOrder(TreeNode *root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}

数组表示二叉树：

//
// Created by zhou on 2023/10/10.
//
#include "../utils/common.h"



/**
 * 数组表示二叉树
 */
class ArrayBinaryTree {
private:
    vector<int> tree;

    void dfs(int index, string order, vector<int> &res) {
        if(val(index) == INT_MAX) return;
        // 前序遍历
        if(order == "pre") {
            res.push_back(val(index));
        }
        dfs(left(index), order, res);
        // 中序遍历
        if(order == "in") {
            res.push_back(val(index));
        }
        dfs(right(index), order, res);
        // 后序遍历
        if (order == "post") {
            res.push_back(val(index));
        }
    }
public:

    ArrayBinaryTree(vector<int> arr) {
        tree = arr;
    }

    /**
     * 数组长度
     */
    int size() {
        return tree.size();
    }

    /**
     * 索引对应的值
     */
    int val(int i) {
        // 越界处理
        if(i < 0 || i >= size()) {
            return INT_MAX;
        }
        return tree[i];
    }

    /**
     * 左孩子的索引
     */
    int left(int i) {
        return 2 * i + 1;
    }

    /**
     * 右孩子的索引
     */
    int right(int i) {
        return 2 * i + 2;
    }

    /**
     * 找当前索引的父索引
     */
    int parent(int i) {
        if (i == 0) return 0;
        return (i - 1) / 2;
    }

    /**
     * 直接遍历数组就是层序遍历的结果
     */
    vector<int> levelOrder() {
        vector<int> res;
        for(int i = 0; i < size(); i++) {
            // 不是空位就记录下来
            if(tree[i] != INT_MAX) {
                res.push_back(val(i));
            }
        }
        return res;
    }

    vector<int> preOrder() {
        vector<int> res;
        dfs(0, "pre", res);
        return res;
    }

    vector<int> inOrder() {
        vector<int> res;
        dfs(0, "in", res);
        return res;
    }

    vector<int> postOrder() {
        vector<int> res;
        dfs(0, "post", res);
        return res;
    }
};

二叉搜索树

查找节点：

//
// Created by zhou on 2023/10/10.
//
#include "../utils/common.h"

TreeNode * binarySearch(TreeNode *root, int val) {
    TreeNode *cur = root;
    while (cur != nullptr) {
        // 小的往左找
        if (cur->val > val) cur = cur->left;
        // 大的往右找
        else if (cur->val < val) cur = cur->right;
        // 找到跳出去
        else break;
    }
    // 最终返回结果节点
    return cur;
}

添加节点：

void addTreeNode(TreeNode *root, int val) {
    // 根节点为空，直接初始化为根节点
    if (root == nullptr) {
        root = new TreeNode(val);
        return;
    }

    TreeNode *cur = root;
    // 记录上一次的节点
    TreeNode *pre;
    // 不断循环直至到叶子节点为止
    while (cur != nullptr) {
        pre = cur;
        // 已存在的不准插入
        if (cur->val == val) return;
        else if (cur->val > val) cur = cur->left;
        else if (cur->val < val) cur = cur->right;
    }
    // 小的往左走，大的往右走
    if (pre->val < val) pre->right = new TreeNode(val);
    else if (pre->val > val) pre->left = new TreeNode(val);
}

删除节点：

void removeTreeNode(TreeNode *root, int val) {
    // 空树，直接结束
    if (root == nullptr) return;

    TreeNode *cur = root;
    TreeNode *pre;
    // 寻找需要删除的节点
    while (cur != nullptr) {
        pre = cur;
        // 找到跳出循环
        if (cur->val == val) break;
        else if (cur->val > val) cur = cur->left;
        else cur = cur->right;
    }
    // 没找到不用删
    if (cur == nullptr) return;

    // 度为0或1的操作，可能只有左孩子或右孩子，也可能两者皆有
    if (cur->left == nullptr || cur->right == nullptr) {
        // child可能是left, right, nullptr中的任一个
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 当前删除的不是根节点
        if (cur != root) {
            // 看删除的节点在左还是右，重新指向
            if (pre->left == cur) pre->left = child;
            else pre->right = child;
        } else {
            // 删除节点是根节点，则重新定义根节点
            root = child;
        }
        // 执行删除
        delete cur;
    }
    // 度为2的操作：需找左子树的最大节点或右子树的最小节点
    // 此处以找右子树的最小节点为例
    else {
        // 先从右子树着手
        TreeNode *tmp = cur->right;
        // 寻找最小节点（肯定是不断往左找，最左下角的就是）
        // 注意不要写成tmp != nullptr，这样写找到的是目标单位的左孩子，会导致空指针
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        // 记录下来当前值
        int tmpVal = tmp->val;
        // 最左下角的节点可能还有右子树，要把目标节点往前移相当于继续执行删除操作，因此递归
        removeTreeNode(root, tmpVal);
        // 最后把右子树的最小节点赋值给原来要删除的节点即可（通过换值完成删除）
        cur->val = tmpVal;
    }
}