本文转载自微信公众号「神奇的寻找程序员k」，作者神奇的叉树程序员K。转载本文请联系神奇的下点程序员k公众号。
前言
已知一个包含父节点引用的个节二叉树和其中的一个节点，如何找出这个节点中序遍历序列的寻找下一个节点?
本文就跟大家分享下这个问题的解决方案与实现代码，欢迎各位感兴趣的叉树开发者阅读本文。
问题分析
正如前言所述，下点我们的个节已知条件如下：
包含父节点引用的二叉树 要查找的节点 我们要解决的问题：
找出要查找节点中序遍历序列的下一个节点 接下来，我们通过举例来推导下一个节点的寻找规律，我们先来画一颗二叉搜索树，叉树如下所示：
8 / \ 6 13 / \ / \ 3 7 9 15 例如，下点我们寻找6的个节下一个节点，根据中序遍历的寻找规则我们可知它的下一个节点是7
8的下一个节点是9 3的下一个节点是云南idc服务商6 7的下一个节点是8 通过上述例子，我们可以分析出下述信息：
要查找的叉树节点存在右子树，那么它的下点下一个节点就是其右子树中的最左子节点 要查找的节点不存右子树： 当前节点属于父节点的左子节点，那么它的下一个节点就是其父节点本身 当前节点属于父节点的右子节点，那么就需要沿着父节点的指针一直向上遍历，直至找到一个是它父节点的左子节点的节点 上述规律可能有点绕，大家可以将规律代入问题中多验证几次，就能理解了。
实现思路
二叉树中插入节点时保存其父节点的引用 调用二叉树的搜索节点方法，找到要查找的节点信息 判断找到的节点是否存在右子树 如果存在，则遍历它的左子树至叶节点，将其返回。亿华云 如果不存在，则遍历它的父节点至根节点，直至找到一个节点与它父节点的左子节点相等的节点，将其返回。 实现代码
接下来，我们将上述思路转换为代码，本文代码中用到的二叉树相关实现请移步我的另一篇文章：TypeScript实现二叉搜索树
搜索要查找的节点
我们需要找到要查找节点在二叉树中的节点信息，才能继续实现后续步骤，搜索节点的代码如下：
import { Node } from "./Node.ts"; export default class BinarySearchTree<T> { protected root: Node<T> | undefined; constructor(protected compareFn: ICompareFunction<T> = defaultCompare) { this.root = undefined; } // 搜索特定值 search(key: T): boolean | Node<T> { return this.searchNode(<Node<T>>this.root, key); } // 搜索节点 private searchNode(node: Node<T>, key: T): boolean | Node<T> { if (node == null) { return false; } if (this.compareFn(key, node.key) === Compare.LESS_THAN) { // 要查找的key在节点的左侧 return this.searchNode(<Node<T>>node.left, key); } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { // 要查找的key在节点的右侧 return this.searchNode(<Node<T>>node.right, key); } else { // 节点已找到 return node; } } } 保存父节点引用
此处的二叉树与我们实现的二叉树稍有不同，插入节点时需要保存父节点的引用，实现代码如下：
export default class BinarySearchTree<T> { // 插入方法 insert(key: T): void { if (this.root == null) { // 如果根节点不存在则直接新建一个节点 this.root = new Node(key); } else { // 在根节点中找合适的位置插入子节点 this.insertNode(this.root, key); } } // 节点插入 protected insertNode(node: Node<T>, key: T): void { // 新节点的键小于当前节点的键，则将新节点插入当前节点的左边 // 新节点的键大于当前节点的键，服务器租用则将新节点插入当前节点的右边 if (this.compareFn(key, node.key) === Compare.LESS_THAN) { if (node.left == null) { // 当前节点的左子树为null直接插入 node.left = new Node(key, node); } else { // 从当前节点(左子树)向下递归,找到null位置将其插入 this.insertNode(node.left, key); } } else { if (node.right == null) { // 当前节点的右子树为null直接插入 node.right = new Node(key, node); } else { // 从当前节点(右子树)向下递归，找到null位置将其插入 this.insertNode(node.right, key); } } } } /** * 二叉树的辅助类: 用于存储二叉树的每个节点 */ export class Node<K> { public left: Node<K> | undefined; public right: Node<K> | undefined; public parent: Node<K> | undefined; constructor(public key: K, parent?: Node<K>) { this.left = undefined; this.right = undefined; console.log(key, "的父节点", parent?.key); this.parent = parent; } toString(): string { return `${ this.key}`; } } 我们来测试下上述代码，验证下父节点引用是否成功：
const tree = new BinarySearchTree(); tree.insert(8); tree.insert(6); tree.insert(3); tree.insert(7); tree.insert(13); tree.insert(9); tree.insert(15); 
在保存父节点引用时折腾了好久也没实现，最后求助了我的朋友_Dreams😁。
寻找下一个节点
接下来，我们就可以根据节点的规律来实现这个算法了，实现代码如下：
export class TreeOperate<T> { /** * 寻找二叉树的下一个节点 * 规则: * 1. 输入一个包含父节点引用的二叉树和其中的一个节点 * 2. 找出这个节点中序遍历序列的下一个节点 * * 例如： * 8 * / \ * 6 13 * / \ / \ * 3 7 9 15 * * 6的下一个节点是7，8的下一个节点是9 * * 通过分析，我们可以得到下述信息： * 1. 如果一个节点有右子树，那么它的下一个节点就是其右子树中的最左子节点 * 2. 如果一个节点没有右子树： * (1). 当前节点属于父节点的左子节点，那么它的下一个节点就是其父节点本身 * (2). 当前节点属于父节点的右子节点，沿着父节点的指针一直向上遍历，直至找到一个是它父节点的左子节点的节点 * */ findBinaryTreeNextNode(tree: BinarySearchTree<number>, node: number): null | Node<number> { // 搜索节点 const result: Node<number> | boolean = tree.search(node); if (result == null) throw "节点不存在"; let currentNode = result as Node<number>; // 右子树存在 if (currentNode.right) { currentNode = currentNode.right; // 取右子树的最左子节点 while (currentNode.left) { currentNode = currentNode.left; } return currentNode; } // 右子树不存在 while (currentNode.parent) { // 当前节点等于它父节点的左子节点则条件成立 if (currentNode === currentNode.parent.left) { return currentNode.parent; } // 条件不成立，继续获取它的父节点 currentNode = currentNode.parent; } return null; } } 我们通过一个例子来测试下上述代码：
// 构建二叉搜索树 const tree = new BinarySearchTree(); tree.insert(8); tree.insert(6); tree.insert(3); tree.insert(7); tree.insert(13); tree.insert(9); tree.insert(15); // 寻找下一个节点 const nextNode = treeOperate.findBinaryTreeNextNode(tree, 7); console.log("7的下一个节点", nextNode.toString()); 
代码地址
文中完整代码如下：
TreeOperate.ts BinarySearchTree.ts