C++ 二叉树边界遍历

以特定顺序访问二叉树边界节点的过程称为边界遍历。边界节点包括不包含左叶节点的左边界、叶节点和不包含右叶节点的右边界。这种遍历有助于访问和处理树的外部节点，这对于各种应用都很有用。

1. 左边界：从树的根到其最左侧节点（不包括左叶节点）的节点组形成左边界。可以自上而下实现左边界遍历。每当有左孩子时，从根开始向左遍历。如果没有左孩子，则访问右孩子并继续，直到找到最左侧的节点。
2. 叶节点：没有左右孩子的节点称为叶节点。可以使用中序遍历来遍历这些节点。中序遍历将按顺时针方向访问每个叶节点。
3. 右边界：构成树右边界的节点集（不包括右叶节点）从最右侧节点延伸到根。您可以使用自下而上的方法构建右边界的遍历，就像您对左边界所做的那样。每当有合适的子节点时，从源开始向右遍历。如果没有右子节点，则访问左子节点，然后继续这种方式，直到到达最右侧的节点。

边界遍历可以通过在 C++ 中为左边界遍历、右边界遍历和叶节点遍历创建不同的函数来实现。这三个元素将按指定顺序包含在最终的边界遍历中。

边界遍历的步骤简述如下：

1. 应打印根节点。
2. 使用自上而下策略打印左边界（不包括左叶节点）。
3. 使用中序遍历打印叶节点。
4. 使用自下而上策略打印右边界（不包括右叶节点）。

编码

让我们举一个例子来说明 C++ 中二叉树的边界遍历

输出

1 2 3 5 6 8 10 9 7

说明

1. 在此示例中，代码首先声明了TreeNode结构并包含了所需的头文件。此结构代表二叉树中的一个节点，具有三个属性：left，指向节点的左孩子；right，指向节点的右孩子；以及 val，存储节点的值。

代码中定义了三个递归函数，用于边界遍历的不同方面。

1. printLeaves(TreeNode* root)：函数printLeaves(TreeNode* root)负责打印树的叶节点。它从根开始，从左到右遍历树，如果节点是叶节点（即它没有左孩子和右孩子），则打印其值。
2. printLeftBoundary(TreeNode* root)：除了左叶节点，树的左边界可以使用printLeftBoundary(TreeNode* root)打印。它从根开始，采用自上而下的策略移动到最左侧的节点。如果节点有左孩子，则打印其左孩子；否则，考虑右孩子。此过程一直持续到到达最左侧的非叶节点。
3. printRightBoundary(TreeNode* root)：类似于printLeftBoundary，printRightBoundary自下而上打印树的右边界（不包括右叶节点）。函数名为printRightBoundary(TreeNode* root)。从根开始向最右侧的非叶节点移动，沿途打印节点。

2. 边界遍历的主要引擎是函数boundaryTraversal(TreeNode* root)。首先显示根节点。之后，它调用printLeftBoundary打印左边界（不包括左侧的叶节点），调用printLeaves打印叶节点，并调用printRightBoundary打印右边界（不包括右侧的叶节点）。

为了演示目的，在主函数中构建了一个示例二叉树。树的结构如下：

3. 通过使用树根调用boundaryTraversal函数来执行边界遍历。

代码将按以下顺序打印二叉树的节点：根、左边界（不包括左叶节点）、叶节点和右边界（不包括右叶节点）。