算法与数据结构——二叉树种类介绍及其基本操作

算法与数据结构——二叉树种类介绍及其基本操作

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

struct TreeNode{
    int val;					// 节点值
    TreeNode *left;		// 左子结点指针
    TreeNode *right;	// 右子节点指针
    TreeNode(int x) :val(x), left(nullptr), right(nullptr){}
};

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。在二叉树中，除叶子节点外，其他所有节点都包含子节点和非空子树。如图所示，如果将“节点2”视为父节点，则其左子节点和右子节点分别是“节点4”和“节点5”，左子树是“节点4及其以下节点形成的树”，右子树是“节点5及其以下节点形成的树”。

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向nullptr。
• 边（edge）：连接两个节点的线段，即节点引用（指针）。
• 节点所在的层（level）：从顶至底递增，根节点所在层为1。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是0、1、2。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。
• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

初始化二叉树

与链表类似，首先初始化节点，然后构建引用（指针）。

/*初始化二叉树*/
// 初始化节点
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。下图给出了一个示例：

/*插入与删除节点*/
TreeNode *P = new TreeNode(0);
// 在 n1 -> n2 之间插入节点 P
n1->left = P;
P->left = n2;
// 删除 P 节点
n1->left = n2;

注意：插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。因此，在二叉树中，插入与删除通常是由一套操作配合完成的，以实现有实际意义的操作。

常见的二叉树类型

完美二叉树

如图所示，完美二叉树（perfect binary tree）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0，其余所有节点的度都为2；若树高度为h，则节点总数为2h+1- 1，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。

完全二叉树

如图所示，完全二叉树（complete binary tree）只有最底层的节点未被填满，且最底层节点尽量靠左填充。

完满二叉树

如图所示，完满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点。

平衡二叉树

如图所示，平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过1。

二叉树的退化

如图展示了二叉树的理想结构与退化结构。当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

• 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
• 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至O(n)。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左往右的顺序访问节点。

层序遍历本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（breadth-first search, BFS），它体现一种“一圈一圈向外扩展”的逐层遍历方式。

代码实现

广度优先遍历通常借助“队列来实现”。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

vector<int> levelOrder(TreeNode *root){
    // 初始化队列，加入根节点
    queue<TreeNode *> que;
    que.push(root);
    // 返回一个vector用于打印
    vector<int> vec;
    while (!que.empty()){
        TreeNode *node = que.front();
        que.pop(); // 节点出队
        vec.push_back(node->val); // 保存节点值
        if (node->left != nullptr){
            que.push(node->left);		//左子结点入队
        }
        if (node->right != nullptr){
            que.push(node->right);		// 右子节点入队 
        }
    }
    return vec;
}

复杂度分析

• 时间复杂度O(n)：所有节点被访问一次，使用O(n)时间，其中n为节点数量
• 空间复杂度为O(n)：在最差情况喜爱，即满二叉树时，遍历到最底层之前，队列中最多同时存在（n + 1）/ 2 个节点，占用O(n)空间。

前序、中序、后序遍历

相应地，前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search,DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式。

下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像时绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序、中序和后序遍历。

代码实现

深度优先搜索通常基于递归实现：

/*前序遍历*/
void preOrder(TreeNode *root, vector<int> &res){
    if (root == nullptr){
        return;
    }
    // 访问优先级：根节点 -> 左子树 -> 右子树
    res.push_back(root->val);
    preOrder(root->left, res);
    preOrder(root->right, res);
}
/*中序遍历*/
void inOrder(TreeNode *root, vector<int> &res){
    if (root == nullptr){
        return;
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root->left, res);
    res.push_back(root->val);
    inOrder(root->right, res);
}
/*后序遍历*/
void postOrder(TreeNode *root, vector<int> &res){
    if (root == nullptr){
        return;
    }
    // 访问优先级： 左子树 -> 右子树 -> 根节点
    postOrder(root->left, res);
    postOrder(root->right, res);
    res.push_back(root->val);
}

复杂度分析

• 时间复杂度为O(n)：所有节点被访问一次，使用O(n)时间。
• 空间复杂度为O(n)：在最差情况下，即树退化为链表时，递归深度达到n，系统占用O(n)栈帧空间。