如何寻找二叉树的下一个节点

2024-04-02 19:04:59 936人浏览安东尼

摘要

如何寻找二叉树的下一个节点，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。前言已知一个包含父节点引

如何寻找二叉树的下一个节点，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

前言

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

问题分析

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

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

我们要解决的问题：

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

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

 8    / \   6   13  / \  / \ 3  7 9  15

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

8的下一个节点是9
3的下一个节点是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> {          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());