编程语言寻找二叉树的下一个节点

本文转载自微信公众号「神奇的程序员k」，作者神奇的程序员K。转载本文请联系神奇的程序员k公众号。 

前言

已知一个包含父节点引用的二叉树和其中的一个节点，如何找出这个节点中序遍历序列的下一个节点?

本文就跟大家分享下这个问题的解决方案与实现代码，欢迎各位感兴趣的开发者阅读本文。

问题分析

正如前言所述，我们的已知条件如下：

• 包含父节点引用的二叉树
• 要查找的节点

我们要解决的问题：

• 找出要查找节点中序遍历序列的下一个节点

接下来，我们通过举例来推导下一个节点的规律，我们先来画一颗二叉搜索树，如下所示：

1.  
2. 8 
3.    / \\ 
4.   6   13 
5.  / \\  / \\ 
6. 3  7 9  15 

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

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

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

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

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

实现思路

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

实现代码

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

搜索要查找的节点

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

1. import { Node } from "./Node.ts"; 
2.  
3. export default class BinarySearchTree<T> { 
4.     protected root: Node<T> | undefined; 
5.  
6.     constructor(protected compareFn: ICompareFunction<T> = defaultCompare) { 
7.         this.root = undefined; 
8.     } 
9.    
10.     // 搜索特定值 
11.     search(key: T): boolean | Node<T> { 
12.         return this.searchNode(<Node<T>>this.root, key); 
13.     } 
14.  
15.     // 搜索节点 
16.     private searchNode(node: Node<T>, key: T): boolean | Node<T> { 
17.         if (node == null) { 
18.             return false; 
19.         } 
20.  
21.         if (this.compareFn(key, node.key) === Compare.LESS_THAN) { 
22.             // 要查找的key在节点的左侧 
23.             return this.searchNode(<Node<T>>node.left, key); 
24.         } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { 
25.             // 要查找的key在节点的右侧 
26.             return this.searchNode(<Node<T>>node.right, key); 
27.         } else { 
28.             // 节点已找到 
29.             return node; 
30.         } 
31.     } 
32. } 

保存父节点引用

此处的二叉树与我们实现的二叉树稍有不同，插入节点时需要保存父节点的引用，实现代码如下：

1. export default class BinarySearchTree<T> { 
2.     // 插入方法 
3.     insert(key: T): void { 
4.         if (this.root == null) { 
5.             // 如果根节点不存在则直接新建一个节点 
6.             this.root = new Node(key); 
7.         } else { 
8.             // 在根节点中找合适的位置插入子节点 
9.             this.insertNode(this.root, key); 
10.         } 
11.     } 
12.    
13.     // 节点插入 
14.     protected insertNode(node: Node<T>, key: T): void { 
15.         // 新节点的键小于当前节点的键，则将新节点插入当前节点的左边 
16.         // 新节点的键大于当前节点的键，则将新节点插入当前节点的右边 
17.         if (this.compareFn(key, node.key) === Compare.LESS_THAN) { 
18.             if (node.left == null) { 
19.                 // 当前节点的左子树为null直接插入 
20.                 node.left = new Node(key, node); 
21.             } else { 
22.                 // 从当前节点(左子树)向下递归,找到null位置将其插入 
23.                 this.insertNode(node.left, key); 
24.             } 
25.         } else { 
26.             if (node.right == null) { 
27.                 // 当前节点的右子树为null直接插入 
28.                 node.right = new Node(key, node); 
29.             } else { 
30.                 // 从当前节点(右子树)向下递归，找到null位置将其插入 
31.                 this.insertNode(node.right, key); 
32.             } 
33.         } 
34.     } 
35. } 
36.  
37. /** 
38.  * 二叉树的辅助类: 用于存储二叉树的每个节点 
39.  */ 
40. export class Node<K> { 
41.     public left: Node<K> | undefined; 
42.     public right: Node<K> | undefined; 
43.     public parent: Node<K> | undefined; 
44.     constructor(public key: K, parent?: Node<K>) { 
45.         this.left = undefined; 
46.         this.right = undefined; 
47.         console.log(key, "的父节点", parent?.key); 
48.         this.parent = parent; 
49.     } 
50.  
51.     toString(): string { 
52.         return `${this.key}`; 
53.     } 
54. } 

我们来测试下上述代码，验证下父节点引用是否成功：

1. const tree = new BinarySearchTree(); 
2. tree.insert(8); 
3. tree.insert(6); 
4. tree.insert(3); 
5. tree.insert(7); 
6. tree.insert(13); 
7. tree.insert(9); 
8. tree.insert(15); 

在保存父节点引用时折腾了好久也没实现，最后求助了我的朋友_Dreams