一、题目
给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针。
以下面的二叉树为例，它的中序遍历序列是：[2, 4, 1, 5, 3, 6]，节点 4 的下一个节点是 1，节点 3 的下一个节点是 5 。
二、分析
画出上面这棵二叉树的中序遍历过程为：
根据中序遍历的特性，可以整理出来的下一个节点的规律：
- 如果节点有右子节点，那么下一个节点一定在右子树中，这种又分成了 2 种情况。
- 右儿子没有子节点，那么下一个节点就是子节点 （节点 2）
- 如果右子节点有子节点，下一个节点就是右子节点种最左的节点 （节点 1） 。
- 如果节点没有右子节点，并且是父节点的左子节点，那么下一个节点就是父亲节点 （节点 5） 。
- 如果节点没有右子节点，并且是父节点的右子节点，那就递归查找父节点，直到一个父节点是祖父节点的左子树 （节点 4） 。如果找到根节点都没有找到，就说明该节点已经是最后一个了 （节点 6） 。
三、代码
类节点定义：
|
1 2 3 4 5 6 7 8 |
template<typename T> class tree_node { private: T data; tree_node *lchild; tree_node *rchild; tree_node *parent; }; |
查找中序遍历序列中下一个节点的成员函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// 获取中序遍历的下一个节点 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 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/* * 测试案例：查找二叉树中序遍历的下一个节点 * 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); } |
测试结果：
