企业官网建设流程全解析

前言

「二叉树的下一个结点」通常指中序遍历（in-order traversal）中某个结点的后继：按照「左、根、右」的顺序访问完整棵树时，紧跟在给定结点后面的那个结点。这个问题在面试里经常出现，因为它同时考察对遍历顺序的理解和对树结构的利用，而不是背一个公式。

最常见的错误是把「下一个结点」直接当成「右孩子」。右孩子只是右子树的根，中序后继应当是右子树中最左边的结点；如果结点没有右子树，后继要沿父指针向上找，直到某个祖先是其父的左孩子。另一个常见错误是忽略「没有后继」的情况：整棵树最后一个结点没有下一个结点，函数必须能返回空指针。还有人把「二叉树」与「二叉搜索树」混为一谈，前者没有大小关系，不能靠比较值来定位后继。

本文按三种前提分别讨论：结点带父指针、只有根指针、以及树是二叉搜索树的情形。示例以 C++17 为基准，只使用标准库。

一、中序后继的两种情况

中序遍历的顺序是：先访问左子树，再访问根，最后访问右子树。对某个结点 x 来说，它的后继只可能来自两个方向。

情况一：x 有右子树。访问完 x 之后，下一个进入的是它的右子树；而右子树中最先被访问的是最左边的结点。因此后继是「x 的右子树中的最左结点」。注意不是右孩子本身：如果右孩子有左子树，后继在更深处。

情况二：x 没有右子树。说明以 x 为根的这棵子树已经访问完毕，接下来要回到祖先。沿着父指针向上走，只要当前结点是父结点的右孩子，就说明父结点也已经访问过（因为右子树在根之后），继续向上；直到遇到一个结点是其父的左孩子，那个父结点就是后继。如果一路走到根都没有遇到这种情况，说明 x 是整棵树最后一个被访问的结点，后继为空。

这两种情况合起来，构成了带父指针时的完整解法。它的时间复杂度是 O(h)，h 为树高：情况一沿着左链向下，情况二沿着父链向上，都不会重复走同一层超过常数次。最坏情况下树退化成链，h 等于结点数。

二、带父指针的 O(h) 解法

先定义结点。父指针用裸指针表示「借用」，树的拥有关系由外部容器或根的所有者负责；示例中不涉及删除，因此不需要unique_ptr。

// 适用于 C++17
#include <iostream>

struct Node {
int value;
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;

explicit Node(int v) : value(v) {}
};

Node* leftmost(Node* n) {
while (n != nullptr && n->left != nullptr) {
n = n->left;
}
return n;
}

Node* inorder_successor(Node* node) {
if (node == nullptr) return nullptr;

// 情况一：有右子树，后继是右子树的最左结点
if (node->right != nullptr) {
return leftmost(node->right);
}

// 情况二：无右子树，向上找第一个「当前结点是其左孩子」的祖先
Node* cur = node;
Node* p = cur->parent;
while (p != nullptr && cur == p->right) {
cur = p;
p = p->parent;
}
return p;
}

推演几个边界：

• 
  
• 结点是叶子且是父的左孩子：p != nullptr，cur == p->right为假，循环不进入，直接返回父结点。正确，因为父结点在左子树访问完后被访问。
• 
  
• 结点是叶子且是父的右孩子：先向上到父，若父仍是祖父的右孩子就继续，直到某个祖先是左孩子或到达根。返回那个祖先的父结点，或者空。
• 
  
• 结点是整棵树的最右叶：一路向上全是右孩子，最终p变成空，返回空指针。正确。
• 
  
• 结点是根且没有右子树：p为空，返回空。正确。
• 
  
• 结点为空：直接返回空，调用方不需要额外判空。
• 
  

leftmost里的n != nullptr判断在传入非空右子树时其实不会用到，但保留它可以让函数独立成立，避免调用方传空时解引用。

三、没有父指针时怎么办

如果结点结构里没有parent，就不能在 O(h) 内直接向上回溯。此时要分两种前提。

一般二叉树：只能遍历

对任意二叉树，没有父指针就无法从结点本身判断它在整棵树中的位置，必须从根开始做一次中序遍历，记录前一个访问的结点，当前结点等于目标时返回下一个。用显式栈可以避免递归深度问题：

// 适用于 C++17
#include <vector>

Node* successor_by_traversal(Node* root, Node* target) {
std::vector<Node*> st;
Node* cur = root;
Node* prev = nullptr;

while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push_back(cur);
cur = cur->left;
}
cur = st.back();
st.pop_back();

if (prev == target) {
return cur;
}
prev = cur;
cur = cur->right;
}
return nullptr;
}

这里用结点地址比较prev == target，而不是比较value。二叉树允许重复值，按值比较可能返回错误的结点。函数的时间复杂度 O(n)，空间复杂度 O(h)。如果目标不在树中，prev永远不会等于它，最终返回空指针；调用方若需要区分「没有后继」与「目标不存在」，可以额外返回一个状态。

二叉搜索树：利用大小关系

如果树同时是二叉搜索树（BST），即使没有父指针，也可以从根开始按值比较，在 O(h) 内找到后继：沿路径向下，记录最后一个「值大于目标」的结点作为候选；走到目标后，如果它有右子树，后继是右子树最左结点，否则候选就是后继。

// 适用于 C++17，要求树是二叉搜索树且值互不相同
// leftmost 沿用上一节的实现
Node* successor_in_bst(Node* root, Node* target) {
Node* cur = root;
Node* candidate = nullptr;

while (cur != nullptr) {
if (target->value < cur->value) {
candidate = cur;
cur = cur->left;
} else if (cur->value < target->value) {
cur = cur->right;
} else {
if (cur->right != nullptr) {
return leftmost(cur->right);
}
return candidate;
}
}
return nullptr;
}

这个版本依赖「左子树所有值小于根、右子树所有值大于根」的 BST 性质，普通二叉树不满足，套用会得到错误结果。值重复时，比较无法区分是哪一个结点，后继的定义也变得不唯一；工程中如果允许重复，通常要在结点里加唯一标识，或者退回遍历法。

前驱的求法与后继完全对称：有左子树时取左子树的最右结点；没有左子树时向上找「当前结点是父的右孩子」的祖先。写代码时把left与right、<与>对调即可，但要注意别只改一半。

常见坑点

坑点一：把后继当成右孩子。

❌return node->right;右孩子有左子树时，中序先访问的是左子树，后继不是右孩子。

✅ 有右子树时返回leftmost(node->right)。

坑点二：向上回溯的条件写反。

❌while (p != nullptr && cur == p->left)这样会在错误的层级停下。

✅ 只有当前结点是父的右孩子时才继续向上，遇到左孩子关系就停。

坑点三：忘记处理「没有后继」。

❌ 一路向上后直接return p->parent;，根结点时解引用空指针。

✅ 循环以p != nullptr为条件，结束时返回p，自然得到空指针。

坑点四：在普通二叉树上按值比较找后继。

❌ 套用 BST 的target->value < cur->value逻辑，普通二叉树没有大小关系，结果错误。

✅ 普通二叉树用中序遍历；只有确认是 BST 才用值比较。

坑点五：用值相等判断是不是目标结点。

❌if (prev->value == target->value)树中有重复值时可能提前返回。

✅ 比较结点地址prev == target，确保是同一个对象。

坑点六：递归实现中序遍历导致深树栈溢出。

❌ 用递归写dfs，斜树深度等于结点数。

✅ 用std::vector模拟栈，或改用带父指针的 O(h) 解法。

坑点七：leftmost不判空。

❌while (n->left != nullptr) n = n->left;传入空指针时直接崩溃。

✅ 循环条件写成n != nullptr && n->left != nullptr。

坑点八：认为带父指针的解法一定是 O(log n)。

❌ 在退化成链的树上仍宣称对数复杂度。

✅ 复杂度是 O(h)，平衡树才是 O(log n)，最坏 O(n)。

总结

「下一个结点」的答案藏在遍历顺序里，而不是结点的局部结构里。有父指针时，向上回溯把「局部」补成了「全局」；没有父指针时，只能靠一次遍历或 BST 的大小关系重新获得全局信息。写之前先确认三件事：树是不是 BST、结点有没有父指针、值是否允许重复。这三点决定了应该用哪一种解法，也决定了边界该怎么写。