二叉树

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

二叉树是一种常见的树状数据结构，它由节点（Node）和边（Edge）组成。每个节点最多有两个子节点，分别称为左子节点（Left Child）和右子节点（Right Child）。

基本概念

1. 根节点（Root Node）：二叉树的顶部节点，没有父节点的节点。
2. 叶子节点（Leaf Node）：没有子节点的节点，也称为终端节点。
3. 内部节点（Internal Node）：除了叶子节点之外的其他节点。
4. 子树（Subtree）：以某个节点为根的子树，由该节点及其所有后代节点组成。
5. 深度（Depth）：从根节点到某个节点的唯一路径上的边数，根节点的深度为0。
6. 高度（Height）：从某个节点到其最远叶子节点的路径上的边数，叶子节点的高度为0。

二叉树类型

• 二叉搜索树（Binary Search Tree）：左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 插入操作
TreeNode* insertNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }

    return root;
}

// 查找操作
TreeNode* searchNode(TreeNode* root, int val) {
    if (root == nullptr || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return searchNode(root->left, val);
    } else {
        return searchNode(root->right, val);
    }
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

• 完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点数达到最大，并且最后一层的节点依次从左到右排列。

• 满二叉树（Full Binary Tree）：除了叶子节点外，每个节点都有两个子节点。

• 平衡二叉树（Balanced Binary Tree）：任意节点的左子树和右子树的高度差不超过1。

二叉树操作

• 插入节点：向二叉树中添加新的节点。
• 删除节点：从二叉树中移除指定节点。
• 查找节点：在二叉树中搜索具有特定值的节点。

遍历

按照特定顺序访问二叉树中的所有节点，包括前序遍历、中序遍历、后序遍历和层序遍历等。

三种遍历方式，关键是看每一个子树根节点的顺序：

遍历方式	顺序
先序遍历	根-左-右
中序遍历	左-根-右
后序遍历	左-右-根

递归写法：

// 先序遍历
void preorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    std::cout << root->val << " ";  // 输出当前节点的值
    preorderTraversalRecursive(root->left);  // 递归遍历左子树
    preorderTraversalRecursive(root->right);  // 递归遍历右子树
}

迭代写法：

// 先序遍历
void preorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();

        std::cout << node->val << " ";  // 输出当前节点的值

        if (node->right != nullptr) {
            nodeStack.push(node->right);
        }
        if (node->left != nullptr) {
            nodeStack.push(node->left);
        }
    }
}