# 二叉树二叉树是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右节点引用。 ```cpp struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} } ``` 每个节点都有两个引用指针，分别指向左子节点和右子节点，该节点被称为这两个子节点的父节点。当给定一个二叉树的节点时，我们将该节点的左子节点以及下节点形成的树成为该节点的左子树，同理可得右子树。 ## 二叉树常见术语 - 根节点（root node）：位于二叉树顶层的节点，没有父节点。 - 叶节点（leaf node）：没有子节点的节点，其两个指针指向None。 - 边（edge）：连接两个节点的线段，即节点引用（指针）。 - 边点所在的层（level）：从顶至底递增，根节点所在层为1。 - 节点的度（degree）：节点的子节点数量。在二叉树中，度的取值范围是0、1、2。 - 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。 - 节点的深度（depth）：从根节点到该节点所经过的边的数量。 - 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。 ## 二叉树的基本操作 ### 初始化二叉树 ```cpp 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; ``` ### 插入与删除节点 ```cpp TreeNode* P = new TreeNode(0); // 在n1和n2之间插入节点 n1->left = P; P->left = n2; // 删除P节点 n1->left = n2; delete P; ``` ## 二叉树常见类型 ### 完美二叉树完美二叉树顾名思义就是所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0,其余所有节点的度都为2;若树的高度为h，则节点总数为`2的h+1次方-1`，层现标准的指数级关系，反应自然界中常见的细胞分裂现象。 ### 完全二叉树完全二叉树仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充。请注意，完美二叉树也是一颗完全二叉树。 ### 完满二叉树完满二叉树除了叶节点之外，其余所有节点都有两个子节点。 ### 平衡二叉树平衡二叉树中任意节点的左子树和右子树的高度之差的绝对值不超过1. ## 二叉树的退化二叉树每层节点都被填满时，达到“完美二叉树”，但是当所有节点都偏向一侧时，二叉树又退化成了“链表” - 完美二叉树是理想情况，可以充分发挥二叉树的“分治”的优势。 - 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至O(n)。 ## 二叉树的遍历从物理结构的角度上看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树上一种非线性的数据结构，这使得遍历树比遍历链表更为复杂，需要借助搜索算法来实现。二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。 ### 层序遍历层序遍历从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。层序遍历本质上属于广度优先遍历，也成为广度优先搜索，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。 ```cpp vector levelOrder(TreeNode *root) { queue queue; queue.push(root); vector vec; while(!queue.empty()) { TreeNode *node = queue.front(); queue.pop(); vec.push_back(node->val); if(node->left != nullptr) queue.push(node->left); if(node->right != nullptr) queue.push(node->right); } return vec; } ``` ### 前序、中序、后序遍历相应地，前序、中序和后序遍历都属于深度优先遍历，也称为深度优先搜索，它体现了一种“先走到尽头，再回溯继续”的遍历方式。深度优先搜索通常基于递归实现 ```cpp /* 前序遍历 */ 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); } ``` ## 数组表示二叉树在链表表示下，二叉树的存储单元为节点`TreeNode`，节点之间通过指针相连接。 ### 表示完美二叉树先分析一个简单案例。给定一颗完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。根据层序遍历的特征，我们可以推导出父节点索引与子节点索引之间的“映射公式”：若某节点的索引为i，则该节点的左子节点索引为`2i + 1`，右节点索引为`2i + 2`。图下展示了各个节点索引之间的映射关系。 ![完美二叉树的数组表示](/upload/images/ebe36107882f227ecd3a9e4ca187e0687e4e59aa0f9323e911d1fa1934170a68.png) ### 表示任意二叉树完美二叉树是一个特例，在二叉树中间曾存在许多None。由于层序遍历序列并不包含这些None，因此我们无法仅凭该序列来推测None的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。给定一颗非完美二叉树，完美二叉树的表示方法已经失效。 ![层序遍历序列对应多种二叉树可能性](array_representation_without_empty.png) 为了解决这个问题，我们在层序遍历序列中显式地写出所有None。这样处理后，层序遍历序列就可以唯一表示二叉树了。 ```cpp /* 二叉树的数组表示 */ vector tree = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15}; ``` ![任意类型二叉树的数组表示](/upload/images/dca8f7c96a0a0253c34d7d994c8507ea591f9536b1eaeb497cb429f274737f1e.png) 值得说明的是，完全二叉树非常适合使用数组表示。回顾完全二叉树的定义，`None` 只出现在最底层且靠右的位置，因此所有`None`一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略储存所有`None`，非常方便。 ![完全二叉树的数组表示](/upload/images/e2366ea9d39c767d187b2a70f64c51a7e2d8aa0c762bd0acb730669c36df33d4.png) 以下代码实现了一颗树基于数组表示的二叉树，包括以下几种操作。 - 给定某节点，获取它的值、左（右）子节点、父节点。 - 获取前序遍历、中序遍历、后序遍历、层序遍历序列。 ```cpp class ArrayBinaryTree { public: /* 构造方法 */ ArrayBinaryTree(vector arr) { tree = arr; } /* 列表容量 */ int size(){ return tree.size(); } /* 获取索引为 i 节点的值 */ int val(int i) { if(i < 0 || i >= size()) return INT_MAX; return tree[i]; } /* 获取索引为 i 节点的左子节点的索引 */ int left(int i) { return 2 * i + 1; } /* 获取索引为 i 节点的右子节点的索引 */ int parent(int i) { return (i - 1) / 2; } /* 层序遍历 */ vector levelOrder() { vector res; for(int i = 0; i < size(); i++) { if(val(i) != INT_MAX) res.push_back(val(i)); } return res; } /* 前序遍历 */ vector preOrder() { vector res; dfs(0, "pre", res); return res; } /* 中序遍历 */ vector inOrder() { vector res; dfs(0, "in", res); return res; } /* 后序遍历 */ vector postOrder() { vector res; dfs(0, "post", res); return res; } private: vector tree; /* 深度优先遍历 */ void dfs(int i, string order, vector &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(right(i), order, res); if(order == "post") res.push_back(val(i)); } } ``` ### 优点与局限性二叉树的数组表示主要有以下优点。 - 数组储存在连续的空间中，对缓存友好，访问与遍历速度较快。 - 不需要储存指针，比较节省空间。 - 允许随机访问节点。然而，数组表示也存在一些局限性。 - 数组储存需要连续内存空间，因此不适合储存数据量过大的树。 - 增删节点需要通过数组插入与删除操作实现，效率低。 - 当二叉树中存在大量`None`时，数组中包含的节点数据比重较低，空间利用率低。 ## 二叉搜索树二叉搜索树满足以下条件。 1. 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。 2. 任意节点的左、右子树也是二叉搜索树，即同样满足条件`1`。 ### 二叉搜索树的操作我们将二叉搜索树封装为一个类`BinarySearchTree`，并声明一个成员变量`root`，指向树的根节点。 #### 1. 查找节点给定目标节点值`num`，可以根据二叉搜索树的性质来查找。我们声明一个节点cur，从二叉树的根节点`root`出发，循环比较节点值`cur.val`和`num`之间的大小关系。 - 若`cur.val < num`，说明目标节点在`cur`节点的右子树中，因此执行`cur = cur.right`。 - 若`cur.val > num`，说明目标节点中`cur`的左子树中，因此执行`cur = cur.left`。 - 若`cur.val = num`，说明找到目标节点，跳出循环并返回节点。二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用O(log n)时间。 ```cpp 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; } ``` #### 2. 插入节点给定一个待插入元素`num`，为了保持二叉树搜索“左子树 < 根节点 < 右子树”的性质，插入操作如下： 1. 查找插入位置：与查找操作类似，从根节点出发，根据当前节点值和`num`的大小关系循环向下搜索，直到越过叶节点（遍历至`None`）时跳出循环。 2. 在该位置插入节点：初始化节点`num`，将该节点置于`None`的位置。在代码实现中，需要注意下面两点。 - 二叉搜索树不允许存在重复节点，否则违反其定义。因此，若待插入节点已经在树中存在，则不执行插入操作。 - 为了实现插入节点，我们需要借助节点`pre`保存上一轮循环的节点。这样遍历至`None`时，我们可以获取到其父节点，从而完成节点插入操作。 ```cpp void insert(int num) { if(root == nullptr){ root = new TreeNode(num); return; } TreeNode *cur = root, *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; } ``` 运行效率和查找相同，时间复杂度都为O(log n)。 #### 3. 删除节点先在二叉树中查找到目标节点，再将其删除。与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的“左子树<根节点<右子树”的特性仍然被满足。因此，我们根据目标节点的子节点数量，分为0、1和2这三种情况，执行对应的删除节点操作。 1. 当待删除节点的度为0时，表示该节点上叶节点，可以直接删除。 2. 当待删除节点的度为1时，将待删除节点替换成为子节点即可。 3. 当待删除节点的度为2时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。假设我们选择右子树的最小节点（中序遍历的下一个节点），则删除操作流程如下： 1. 找到待删除节点在“中序遍历序列”中的下一个节点，记为`tmp`。 2. 用`tmp`的值覆盖待删除节点的值，并在树中递归删除节点`tmp`。删除节点操作的时间复杂度同样为O(log n)。 ```cpp void remove(int num) { if(root == nullptr) return; TreeNode *cur = root, *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-l>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; } } ``` #### 4. 中序遍历有序二叉树的中序遍历遵循“左->根->右”的遍历顺序，而二叉搜索树满足“左子节点<根节点<右子节点”的大小关系。这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要的性质：二叉搜索树的中序遍历是升序的。利用中序遍历的性质我们仅需要使用O(n)的时间复杂度，即可获得一个升序的数据。 ### 二叉搜索树的效率 | | 无序数组 | 二叉搜索树 | | -------- | -------- | ---------- | | 查找元素 | O(n) | O(log n) | | 插入元素 | O(1) | O(log n) | | 删除 | O(n) | O(log n) |