二叉树（binary tree）是一种非线性数据结构，代表祖先与后代的派生关系，体现了分治思想。

二叉树的基本单元是节点，包括值和左右节点指针。

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

在二叉树中，除了叶节点，其他节点都包含子节点和非空子树。

• 根节点（root node）：位于顶点的节点。
• 叶节点（leaf node）：没有子节点的节点。
• 边（edge）：连接两个节点的线段。
• 子树（subtree）：以左子节点为根节点的子树成为左子树(left subtree)，右子树亦然。
• 度（degree）：节点的子节点的数量，二叉树中取值为0，1，2。
• 高度（height）：根节点到叶节点的边的数量。
• 深度（depth）：从根节点到该节点经过的边的数量。
• 节点的高度：从距离该节点最远的叶节点到该节点的边的数量。

二叉树基本操作

初始化

TreeNode* n0 = new TreeNode(0);
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
n0->left = n1;
n0->right = n2;
n1->left = n3;

插入与删除节点

TreeNode* P = new TreeNode(0);
n1->left = P;
P->left = n2;

//删除
n1->left = n2;
delete P;

常见二叉树类型

完美二叉树

若树的高度为h，则节点总数为 $2^{h + 1} - 1$。完美二叉树可用数组表示。

完全二叉树

仅最底层的节点未填满。完全二叉树也可用数组表示。

平衡二叉树

二叉树遍历

层序遍历（广度优先搜索）

vector<int> levelOrder(TreeNode* root) {
  queue<TreeNode*> queue;
  queue.push(root);
  vector<int> vec;
  while(!.queue.empty()) {
    TreeNode* node = queue.front();
    queue.pop();
    vec.push_back(node->val);
    if (node->left != nullptr) queue.push(queue.pop());
    if (node->right != nullptr) queue.push(queue.pop());
  }
  
  return 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);
}

前序遍历的递归过程

二叉树的数组表示

二叉组的数组表示有以下优点：

• 数组存储的二叉树对缓存友好，访问与遍历速度快。
• 不需要存储指针，节省空间。
• 允许随机访问节点。

缺点：

• 数组存储需要连续空间，不适合存储数据量大的树。
• 增删节点需要通过数组的插入与删除实现，效率低。
• 二叉树存在大量None时，数组存储空间利用率低。

对于完美二叉树和完全二叉树，可用 $2i + 1$ 和 $2i + 2$ 表示二叉树。

对于任意二叉树，可用none占位实现这个效果。

class ArrayBinaryTree {
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) return (i - 1)/2;
  
  vector<int> levelOrder() {
    vector<int> res;
    for (int i = 0; i < size(); ++i) {
      if (val(i) != INT_MAX) res.push_back(val(i));
    }
    
    return res;
  }
  
  vector<int> preOrder() {
    vector<int> res;
    dfs(0, "pre", res);
  }
  
  vector<int> inOrder() {
    vector<int> res;
    dfs(0, "in", res);
  }
  
  vector<int> postOrder() {
    vector<int> res;
    dfs(0, "post", res);
  }
    
private:
  vector<int> tree;
  void dfs(int i, string order, vector<int>& res) {
    if (val[i] == INT_MAX) return;
    
    if (order == "pre")
      res.push_back(val(i));
    
    dfs(left(i), order, res);
    if (order == "in") 
      res.push_back(val(i));
    dfs(left(i), order, res);
    if (order == "post")
      res.push_back(val(i));
  }
}

二叉树的应用

二叉搜索树

二叉搜索树(binary search tree)

• 左子树所有节点的值 < 根节点的值 < 右子树所有节点的值
• 任意节点的左右子树也满足条件1。
• 二叉搜索树不允许存在重复节点。

二叉搜索树的常见操作

查找

TreeNode* search(int num) {
  TreeNode* cur = root;
  while (cur != nullptr) {
    if (cur->val < num) cur = cur->right;
    else if (cur->val > num) cur = cur->left;
    else break;
  }
  
  return cur;
}

插入

插入过程中，需要保存上一轮访问的节点，以便在遍历到None时，能获取到父节点。

void insert(int num) {
  if (root == nullptr) {
    root = new TreeNode(num);
    return;
  }
  
  TreeNode* cur = root;
  TreeNode* pre = nullptr;
  
  while (cur != nullptr) {
    if (cur->val == num) {
      return;
    }
    
    pre = cur;
    if (cur->val < num) {
      cur = cur->right;
    } else {
      cur = cur->left;
    }
  }
    
  TreeNode* node = new TreeNode(num);
  if (pre->val < num) pre->right = node;
  else pre->left = node;
}

删除

删除分三种情况：

1. 删除度为0的点

1. 删除度为1的点

1. 删除度为2的点

删除操作的核心思想就是：找到待删除节点中序遍历的下一个节点，用该节点的值覆盖删除节点，然后递归删除下一个节点。

void remove(int num) {
  if (root == nullptr) {
    return;
  }
  
  TreeNode* cur = root;
  TreeNode* pre = nullptr;
  // 寻找删除节点
  while (cur != nullptr) {
    if (cur->val == num) break;
    pre = cur;
    if (cur->val < num) cur = cur->right;
    else cur = cur->left;
  }
  if (cur == nullptr) {
    return;
  }
  
  if (cur->left == nullptr || cur->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;
  } else {
    TreeNode* tmp = cur->right;
    while (tmp->left != nullptr) {
      tmp = tmp->left;
    }
    
    int tmpVal = tmp->val;
    remove(tmp->val);
    cur->val = tmpVal;
  }
}

AVL 树

待补充