企业官网建设流程全解析

• 教程
• 示例工程

树（Tree）是计算机科学中最基础也最重要的非线性数据结构之一，而二叉树（Binary Tree）作为其最经典的变体，是二分查找、二叉堆、表达式解析与各类自平衡树（AVL、红黑树）的基石。本指南以 Cosmos 仓库code/data_structures/src/tree/binary_tree/binary_tree/目录下的多语言实现为核心，系统讲解二叉树的节点模型、基本性质、遍历算法，以及高度/直径、镜像/平衡、重建/序列化等经典操作，帮助你既能在概念层面吃透二叉树，也能在 C/C++、Java、Python 等语言中直接套用仓库源码快速落地。

从树到二叉树：核心概念与术语

关联文档 README.md 给出了树的精确定义：树由若干「节点」组成，每个节点至少有一个父节点，并可以有多个子节点；唯一没有父节点的节点称为「根」（root，也称 base node）；没有任何子节点的节点称为「叶子」（leaf）。

在此基础上，二叉树说明 进一步定义了二叉树：它是树的一种变体，每个节点最多拥有两个孩子（通常称为左孩子 left 与右孩子 right）。这个"最多两个"的限制看似简单，却带来了巨大的结构收益：

• 结构规整，便于递归定义与递归算法设计（子树仍是二叉树）；
• 支持高效的二分思想，可用于执行二分查找；
• 可以构建二叉堆（本仓库见 maxHeap、minHeap 等实现）与各类排序算法配合使用；
• 是 AVL 树、红黑树、伸展树等自平衡搜索树的基础。

从"度"（degree，即节点拥有的子节点个数）的角度看，二叉树的节点度最大为 2。若一棵二叉树除最后一层外每一层都被填满，且最后一层节点都靠左排列，则称为完全二叉树；若所有叶子都在同一层且每个非叶节点都有两个孩子，则称为满二叉树——这些变体在堆与线段树的实现中尤为重要。

二叉树的节点模型：多语言实现对照

一切二叉树操作都从节点定义开始。Cosmos 仓库提供了两种典型实现范式：

C++ 模板节点（shared_ptr 智能指针）

节点实现 node.cpp 使用模板与std::shared_ptr管理节点生命周期，避免手动释放内存：

template<typename _Type> class TreeNode { protected: using SPNodeType = std::shared_ptr<TreeNode>; using ValueType = _Type; public: TreeNode(ValueType v, SPNodeType l = nullptr, SPNodeType r = nullptr) : value_(v), left_(l), right_(r) {} ValueType value() { return value_; } void value(ValueType v) { value_ = v; } SPNodeType left() { return left_; } void left(SPNodeType l) { left_ = l; } SPNodeType right() { return right_; } void right(SPNodeType r) { right_ = r; } private: ValueType value_; SPNodeType left_; SPNodeType right_; };

同一文件中还提供了__BaseTreeNode与DerivativeTreeNode的继承体系，专门为 AVL 树、伸展树等派生二叉搜索树复用节点基础设施而设计——这是仓库在工程化上的一大亮点：通过 CRTP（奇异递归模板模式）将基础节点能力抽离为可继承基类。

Python 节点与完整 BST 封装

Python 实现 tree.py 用类封装了节点与二叉搜索树（BST），节点模型简洁直观：

class Node(object): def __init__(self, data=None): self.left = None self.right = None self.data = data

该文件还完整实现了 BST 的十余种核心操作：插入（迭代insert与递归insert_recursive）、删除（delete/Delete，含单子节点直接提升、双子节点用后继替换的策略）、搜索search、求最小/最大值find_min/find_max、树高height、层序遍历traverse、节点路径get_node_path与最近公共祖先LCA、后继节点successor等，是学习二叉搜索树完整 API 的绝佳参考。

更多语言版本

目录 tree/ 下还提供tree.c、tree.java、tree.js、tree.rb、tree.swift、tree.go等实现（如tree2.java、tree2.swift为补充版本），适合在不同技术栈中对照学习。

二叉树的遍历：从层序到 Zigzag

遍历是二叉树一切算法的基础。仓库中既有标准遍历，也有不少变体实现。

层序遍历（BFS）

tree.py 的traverse方法用队列（列表模拟）实现层序遍历：从根入队开始，每次弹出队首节点并输出，再依次将左、右孩子入队，天然保证按"层"从上到下、从左到右输出。

Zigzag（锯齿形）遍历

zigzag.cpp 使用双栈交替实现锯齿形层序遍历：当前层从左到右输出时，将孩子按"先右后左"压入另一栈；下一层从右到左输出时，将孩子按"先左后右"压回——两个栈交替工作即可完成"之"字形遍历，无需借助方向标志位。

线索二叉树中序遍历

右线索二叉树实现 right_threaded.cpp 展示了利用空指针建立"线索"来消除递归栈/显式栈的中序变体，适合要求 O(1) 辅助空间的场景。

左视图与右视图

preorder 目录 下提供了 左视图 left_view.java 与 右视图 right_view.cpp、right_view.py、right_view2.cpp。它们解决"从左侧/右侧观察二叉树时能看到哪些节点"的问题，本质是每层取最左/最右节点。

高度、深度与直径

最大高度

maximum_height.cpp 通过递归求树高：左右子树高度取较大者加 1（空节点高度为 0）。同目录还提供maximum_height.java、maximum_height.py与两个 C++ 变体。Python 版 tree.py 的height_递归后对外接口height返回depth - 1，并特别注明"第一个节点的高度为 0 而非 1"——这是容易踩坑的约定细节，使用时需与自己的定义保持一致。

最小高度

minimum_height 目录 提供minimum_height.c、minimum_height.cpp、minimum_height.java、minimum_height.py四种实现，对应"根到最近叶子"的最短路径长度，常用于判断树的紧凑程度。

直径（最长路径长度）

直径实现 diameter.cpp 给出了递归与迭代两套解法，并与公共节点实现 node.cpp 协同工作：

• 递归版diameterRecursive：对每个节点计算左子树高度 + 右子树高度 + 1，全局取最大值；返回值是子树高度，maximum引用参数累积直径；
• 迭代版diameterIterative：借助显式栈做 DFS，并在回退时用哨兵nullptr标记右子树已完成访问，避免重复计算；
• 辅助函数getDiameter与getDeep复用节点value()字段暂存子树深度，实现原地记忆化。

同目录的diameter.c、diameter.java、diameter.py、diameter.hs、diameter2.c、diameter2.cpp提供了多语言对照。

镜像、对称与平衡

生成镜像树

make_mirror_tree.cpp 用递归生成一棵新镜像树：m_root->left = mirror(root->right)、m_root->right = mirror(root->left)，左右子树互换并递归创建新节点。它演示了不修改原树、生成新树的纯函数式写法；同目录还有make_mirror_tree.c与make_mirror_tree.py变体。

平衡性判断与失衡调整

• is_balance 目录 提供is_balance.java，用于判断任意二叉树是否为平衡二叉树（任意节点的左右子树高度差不超过 1）；
• balance_binary_tree 目录 的balance_bst_dsw.cpp实现经典的DSW 算法（通过右旋将 BST 压平成有序链表，再经一系列左旋重建为平衡树），而BST.py则是配套的搜索树操作参考——这是理解"树平衡化"底层机制的重要代码。

树的判定、比较与重建

判定二叉搜索树与结构比较

• is_binary_tree.cpp：校验给定二叉树是否满足 BST 的"左小右大"性质；
• is_same.cpp：判断两棵二叉树结构是否完全相同。

由遍历序列重建二叉树

重建问题是面试与竞赛高频题。make_binary_tree 目录 下：

• from_inorder_and_preorder：由前序 + 中序重建二叉树，提供make_tree_from_inorder_and_preorder.c、.cpp、.java及说明文档。核心思想是前序序列的首个元素必为根，据此在中序序列中切分左右子树区间并递归；
• from_inorder_and_postorder：由后序 + 中序重建，make_tree_from_inorder_and_postorder.c与.cpp中后序序列的末元素为根，中序再行切分。

注意重建的前提是序列中节点值唯一，且提供的中序序列必须真实来自同一棵树。

序列化与反序列化

serializer.cpp 实现二叉树的序列化/反序列化，可将树编码为字符串流（通常配合空标记#表示空节点、先序遍历顺序），用于网络传输或持久化存储。

路径、子树与链表转换等进阶问题

binary_tree目录还收录了大量进阶问题，均为可运行、可测试的独立实现：

• 路径和：path_sum.cpp 与其头文件path_sum.hpp判断是否存在"根到叶子路径和等于目标值"；sum_left 子目录 提供sum_left.c与left_sum.py，计算所有左叶子之和；
• 子树求和：Subtree_sum/subtreesum_recursive.cpp 递归计算以每个节点为根的子树和；
• 同值子树计数：count_universal_subtrees.cpp 统计所有节点值相同的子树数量；
• 原地转双向链表：convert_to_doubly_linked_list.cpp 将二叉搜索树按中序线索化为双向链表，不引入额外空间。

这些题目覆盖了"分治递归 + 引用/全局累计 + 原地改造"三类典型技巧，可与 diameter.cpp 的递归写法互相印证。

延伸阅读与仓库探索路径

若想继续深入，建议按以下路径在仓库中展开：

1. 二叉树的近亲：仓库 data_structures/src/tree 下还包含二叉搜索树、AVL 树、红黑树、B 树等大量变体实现（共 189 个文件、覆盖 20 余种语言）；
2. 堆与优先队列：基于完全二叉树思想的 maxHeap 与 binary_heap；
3. 与二叉树的关联算法：本目录顶部文档提到的 二分查找 与 排序；
4. 仓库根 README.md 与 数据结构总览 可帮助你定位更多示例与测试用例。

结语

从三行概念定义出发，Cosmos 仓库在code/data_structures/src/tree/binary_tree/binary_tree/下沉淀了一套横跨 C/C++、Java、Python、Go、Swift、Ruby、JavaScript、Haskell 等多语言的二叉树实践集：既有基础节点模型与遍历，也有高度、直径、镜像、平衡、重建、序列化等经典算法，还有可直接运行的进阶题目。对照 node/node.cpp 与 tree/tree.py 两个核心文件逐行研读，再以其余实现做多语言对照，即可快速建立对二叉树的系统性掌握。

• 教程
• 示例工程