​ 树是个让我比较头疼的知识点，变化比较多样，各种性质也让我感到烦琐。二叉树就是一种树形数据结构，其中每个节点最多只能有两个子节点，分别称为左子节点和右子节点。

​ 有很多前置的数的性质与知识，比如节点的高度、度数之类的都很好理解，包括一些稍微需要计算的东西我这里懒得写了，主要想记录存储和遍历这种更实际一点的东西。

二叉树的存储

顺序存储

​ 首先当然是顺序存储，但是二叉树这种东西怎么能顺序存储呢，很奇怪吧，因为你需要体现它的父节点和子节点，所以我们一般只用顺序存储去存完全二叉树（完全二叉树是一种二叉树，除了最后一层外，其他每一层都被完全填满，而最后一层的节点全部集中在左侧），按照满二叉树（满二叉树是一种二叉树，其中每个节点要么没有子节点（是叶子），要么正好有两个子节点（左子和右子）。）的顺序去放置节点在顺序的槽位i中，如果该位置没有节点就标记为空，很浪费对吧hh。

链式存储

​ 链式存储就很好理解了，链表太好用了

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;

// 定义二叉树结点结构
typedef char ElemType; // 假设元素类型为字符

struct BiTNode {
    ElemType data;       // 数据域
    BiTNode* lchild;     // 左子节点指针
    BiTNode* rchild;     // 右子节点指针
};

无需多言

二叉树的遍历

前序遍历（Preorder Traversal）

顺序：根 → 左 → 右

1
2
3
4
5
6
7
void PreOrder(BiTNode* T) {
    if (T) {
        cout << T->data << ' ';       // 访问根
        PreOrder(T->lchild);          // 遍历左子树
        PreOrder(T->rchild);          // 遍历右子树
    }
}

先访问根结点，再递归访问左子树和右子树，适合先构建结构的场景（如创建树）。

中序遍历（Inorder Traversal）

顺序：左 → 根 → 右

1
2
3
4
5
6
7
void InOrder(BiTNode* T) {
    if (T) {
        InOrder(T->lchild);           // 遍历左子树
        cout << T->data << ' ';       // 访问根
        InOrder(T->rchild);           // 遍历右子树
    }
}

先访问左子树，然后访问根结点，再访问右子树，中序遍历在二叉搜索树中输出的是有序序列。

后序遍历（Postorder Traversal）

顺序：左 → 右 → 根

1
2
3
4
5
6
7
void PostOrder(BiTNode* T) {
    if (T) {
        PostOrder(T->lchild);         // 遍历左子树
        PostOrder(T->rchild);         // 遍历右子树
        cout << T->data << ' ';       // 访问根
    }
}

最后访问根结点，适合删除树、释放内存场景，因为它保证后访问根。

层次遍历（Level-Order Traversal）

顺序：一层层从左到右访问

1
2
3
4
5
6
7
8
9
10
11
12
#include <queue>
void LevelOrder(BiTNode* T) {
    if (!T) return;
    queue<BiTNode*> q;
    q.push(T);
    while (!q.empty()) {
        BiTNode* node = q.front(); q.pop();
        cout << node->data << ' ';
        if (node->lchild) q.push(node->lchild);
        if (node->rchild) q.push(node->rchild);
    }
}

利用队列结构，先进先出地处理每个结点，然后依次将它的左右子节点加入队列。适合按层操作的场景，如求最大宽度、最短路径等。

二叉树的构造

中序 + 先序

⇒ 唯一确定

原理：

  • 先序第一个是根；
  • 在中序中定位根位置，划分左/右子树；
  • 递归处理左右子树的子问题。
中序 + 后序

⇒ 唯一确定

原理：

  • 后序最后一个是根；
  • 在中序中定位根位置，划分左/右子树；
  • 递归处理左右子树。

线索二叉树

二叉树的线索化
在线索二叉树中找前驱后继
先序
中序
后序