一、题目

给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针。

以下面的二叉树为例，它的中序遍历序列是：[2, 4, 1, 5, 3, 6]，节点4的下一个节点是1，节点3的下一个节点是5。

二、分析

画出上面这棵二叉树的中序遍历过程为：

根据中序遍历的特性，可以整理出来的下一个节点的规律：

1. 如果节点有右子节点，那么下一个节点一定在右子树中，这种又分成了2种情况。

   • 右儿子没有子节点，那么下一个节点就是子节点（节点2）
   • 如果右子节点有子节点，下一个节点就是右子节点种最左的节点（节点1）。
2. 如果节点没有右子节点，并且是父节点的左子节点，那么下一个节点就是父亲节点（节点5）。
3. 如果节点没有右子节点，并且是父节点的右子节点，那就递归查找父节点，直到一个父节点是祖父节点的左子树（节点4）。如果找到根节点都没有找到，就说明该节点已经是最后一个了（节点6）。

三、代码

类节点定义：

template<typename T>
class tree_node {
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
    tree_node *parent;
};

查找中序遍历序列中下一个节点的成员函数：

// 获取中序遍历的下一个节点
const tree_node<T> *get_next_node_in_order() const {
    const tree_node<T> *p, *father;
    if (rchild) { // 有右节点，在右子树中查找
        p = rchild;
      
        // 循环遍历左子树
        while (p->lchild)
            p = p->lchild;
      
        return p;
    } else if (parent) {
        p = this;
        father = parent;
      
        // 只要不是父节点的左子节点，一直往上找
        while (father && p != father->lchild) {
            p = father;
            father = father->parent;
        }

        // 返回父亲节点
        return father;
    }
    return nullptr;
}

四、单元测试

单元测试主要覆盖几个点：

• 节点有右子节点。
• 节点没有右子节点，存在一个父节点是祖先节点的左子节点。
• 节点没有右子节点，不存在一个父节点是祖先节点的左子节点。

/*
 * 测试案例：查找二叉树中序遍历的下一个节点
 *         1
 *      /     \
 *     2       3
 *      \     / \
 *       4   5   6
 */
TEST(bin_tree, get_next_node_in_order) {
    bin_tree<int> tree;
    const tree_node<int> *node;
    int in[] = {2, 4, 1, 5, 3, 6}; // 先序遍历序列
    int pre[] = {1, 2, 4, 3, 5, 6}; // 中序遍历序列
    
    // 根据先序遍历序列和中序遍历序列生成二叉树
    tree.construct(pre, in, 6);
    EXPECT_TRUE(tree.get_root());

    // 定位到中序遍历的开始节点2，然后依次获取下一个节点，和in数组对比
    node = tree.get_root()->get_lchild();
    for (int i = 0; i < 6; i++) {
        EXPECT_TRUE(node) << i;
        EXPECT_EQ(node->get_data(), in[i]);
        node = tree.get_next(node);
    }
    EXPECT_EQ(node, nullptr);
}

测试结果：