二叉树的下一个节点

我们寻找6的下一个节点，根据中序遍历的规则我们可知它的下一个节点是7

• 8的下一个节点是9
• 3的下一个节点是6
• 7的下一个节点是8

通过上述例子，我们可以分析出下述信息：

• 要查找的节点存在右子树，那么它的下一个节点就是其右子树中的最左子节点
• 要查找的节点不存右子树：
  • 当前节点属于父节点的左子节点，那么它的下一个节点就是其父节点本身
  • 当前节点属于父节点的右子节点，那么就需要沿着父节点的指针一直向上遍历，直至找到一个是它父节点的左子节点的节点

上述规律可能有点绕，大家可以将规律代入问题中多验证几次，就能理解了。

实现思路

• 二叉树中插入节点时保存其父节点的引用
• 调用二叉树的搜索节点方法，找到要查找的节点信息
• 判断找到的节点是否存在右子树
• 如果存在，则遍历它的左子树至叶节点，将其返回。
• 如果不存在，则遍历它的父节点至根节点，直至找到一个节点与它父节点的左子节点相等的节点，将其返回。

实现代码

接下来，我们将上述思路转换为代码，本文代码中用到的二叉树相关实现请移步我的另一篇文章：TypeScript实现二叉搜索树

搜索要查找的节点

我们需要找到要查找节点在二叉树中的节点信息，才能继续实现后续步骤，搜索节点的代码如下：

（编辑：甘孜站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!