如何尋找二叉樹的下一個(gè)節(jié)點(diǎn)

如何尋找二叉樹的下一個(gè)節(jié)點(diǎn)，很多新手對此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

前言

已知一個(gè)包含父節(jié)點(diǎn)引用的二叉樹和其中的一個(gè)節(jié)點(diǎn)，如何找出這個(gè)節(jié)點(diǎn)中序遍歷序列的下一個(gè)節(jié)點(diǎn)?

問題分析

正如前言所述，我們的已知條件如下：

• 包含父節(jié)點(diǎn)引用的二叉樹

• 要查找的節(jié)點(diǎn)

我們要解決的問題：

• 找出要查找節(jié)點(diǎn)中序遍歷序列的下一個(gè)節(jié)點(diǎn)

接下來，我們通過舉例來推導(dǎo)下一個(gè)節(jié)點(diǎn)的規(guī)律，我們先來畫一顆二叉搜索樹，如下所示：

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

例如，我們尋找6的下一個(gè)節(jié)點(diǎn)，根據(jù)中序遍歷的規(guī)則我們可知它的下一個(gè)節(jié)點(diǎn)是7

• 8的下一個(gè)節(jié)點(diǎn)是9

• 3的下一個(gè)節(jié)點(diǎn)是6

• 7的下一個(gè)節(jié)點(diǎn)是8

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

• 要查找的節(jié)點(diǎn)存在右子樹，那么它的下一個(gè)節(jié)點(diǎn)就是其右子樹中的最左子節(jié)點(diǎn)

• 要查找的節(jié)點(diǎn)不存右子樹：

• 當(dāng)前節(jié)點(diǎn)屬于父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是其父節(jié)點(diǎn)本身

• 當(dāng)前節(jié)點(diǎn)屬于父節(jié)點(diǎn)的右子節(jié)點(diǎn)，那么就需要沿著父節(jié)點(diǎn)的指針一直向上遍歷，直至找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)

上述規(guī)律可能有點(diǎn)繞，大家可以將規(guī)律代入問題中多驗(yàn)證幾次，就能理解了。

實(shí)現(xiàn)思路

• 二叉樹中插入節(jié)點(diǎn)時(shí)保存其父節(jié)點(diǎn)的引用

• 調(diào)用二叉樹的搜索節(jié)點(diǎn)方法，找到要查找的節(jié)點(diǎn)信息

• 判斷找到的節(jié)點(diǎn)是否存在右子樹

• 如果存在，則遍歷它的左子樹至葉節(jié)點(diǎn)，將其返回。

• 如果不存在，則遍歷它的父節(jié)點(diǎn)至根節(jié)點(diǎn)，直至找到一個(gè)節(jié)點(diǎn)與它父節(jié)點(diǎn)的左子節(jié)點(diǎn)相等的節(jié)點(diǎn)，將其返回。

實(shí)現(xiàn)代碼

接下來，我們將上述思路轉(zhuǎn)換為代碼，本文代碼中用到的二叉樹相關(guān)實(shí)現(xiàn)請移步我的另一篇文章：TypeScript實(shí)現(xiàn)二叉搜索樹

搜索要查找的節(jié)點(diǎn)

我們需要找到要查找節(jié)點(diǎn)在二叉樹中的節(jié)點(diǎn)信息，才能繼續(xù)實(shí)現(xiàn)后續(xù)步驟，搜索節(jié)點(diǎn)的代碼如下：

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);     }      // 搜索節(jié)點(diǎn)     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在節(jié)點(diǎn)的左側(cè)             return this.searchNode(<Node<T>>node.left, key);         } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {             // 要查找的key在節(jié)點(diǎn)的右側(cè)             return this.searchNode(<Node<T>>node.right, key);         } else {             // 節(jié)點(diǎn)已找到             return node;         }     } }

保存父節(jié)點(diǎn)引用

此處的二叉樹與我們實(shí)現(xiàn)的二叉樹稍有不同，插入節(jié)點(diǎn)時(shí)需要保存父節(jié)點(diǎn)的引用，實(shí)現(xiàn)代碼如下：

export default class BinarySearchTree<T> {     // 插入方法     insert(key: T): void {         if (this.root == null) {             // 如果根節(jié)點(diǎn)不存在則直接新建一個(gè)節(jié)點(diǎn)             this.root = new Node(key);         } else {             // 在根節(jié)點(diǎn)中找合適的位置插入子節(jié)點(diǎn)             this.insertNode(this.root, key);         }     }        // 節(jié)點(diǎn)插入     protected insertNode(node: Node<T>, key: T): void {         // 新節(jié)點(diǎn)的鍵小于當(dāng)前節(jié)點(diǎn)的鍵，則將新節(jié)點(diǎn)插入當(dāng)前節(jié)點(diǎn)的左邊         // 新節(jié)點(diǎn)的鍵大于當(dāng)前節(jié)點(diǎn)的鍵，則將新節(jié)點(diǎn)插入當(dāng)前節(jié)點(diǎn)的右邊         if (this.compareFn(key, node.key) === Compare.LESS_THAN) {             if (node.left == null) {                 // 當(dāng)前節(jié)點(diǎn)的左子樹為null直接插入                 node.left = new Node(key, node);             } else {                 // 從當(dāng)前節(jié)點(diǎn)(左子樹)向下遞歸,找到null位置將其插入                 this.insertNode(node.left, key);             }         } else {             if (node.right == null) {                 // 當(dāng)前節(jié)點(diǎn)的右子樹為null直接插入                 node.right = new Node(key, node);             } else {                 // 從當(dāng)前節(jié)點(diǎn)(右子樹)向下遞歸，找到null位置將其插入                 this.insertNode(node.right, key);             }         }     } }  /**  * 二叉樹的輔助類: 用于存儲(chǔ)二叉樹的每個(gè)節(jié)點(diǎn)  */ 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, "的父節(jié)點(diǎn)", parent?.key);         this.parent = parent;     }      toString(): string {         return `${this.key}`;     } }

我們來測試下上述代碼，驗(yàn)證下父節(jié)點(diǎn)引用是否成功：

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);

在保存父節(jié)點(diǎn)引用時(shí)折騰了好久也沒實(shí)現(xiàn)，最后求助了我的朋友_Dreams?。

尋找下一個(gè)節(jié)點(diǎn)

接下來，我們就可以根據(jù)節(jié)點(diǎn)的規(guī)律來實(shí)現(xiàn)這個(gè)算法了，實(shí)現(xiàn)代碼如下：

export class TreeOperate<T> {     /**      * 尋找二叉樹的下一個(gè)節(jié)點(diǎn)      * 規(guī)則:      *  1. 輸入一個(gè)包含父節(jié)點(diǎn)引用的二叉樹和其中的一個(gè)節(jié)點(diǎn)      *  2. 找出這個(gè)節(jié)點(diǎn)中序遍歷序列的下一個(gè)節(jié)點(diǎn)      *      * 例如：      *       8      *      / \      *     6   13      *    / \  / \      *   3  7 9  15      *      * 6的下一個(gè)節(jié)點(diǎn)是7，8的下一個(gè)節(jié)點(diǎn)是9      *      * 通過分析，我們可以得到下述信息：      *  1. 如果一個(gè)節(jié)點(diǎn)有右子樹，那么它的下一個(gè)節(jié)點(diǎn)就是其右子樹中的最左子節(jié)點(diǎn)      *  2. 如果一個(gè)節(jié)點(diǎn)沒有右子樹：      *  (1). 當(dāng)前節(jié)點(diǎn)屬于父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是其父節(jié)點(diǎn)本身      *  (2). 當(dāng)前節(jié)點(diǎn)屬于父節(jié)點(diǎn)的右子節(jié)點(diǎn)，沿著父節(jié)點(diǎn)的指針一直向上遍歷，直至找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)      *      */     findBinaryTreeNextNode(tree: BinarySearchTree<number>, node: number): null | Node<number> {         // 搜索節(jié)點(diǎn)         const result: Node<number> | boolean = tree.search(node);         if (result == null) throw "節(jié)點(diǎn)不存在";         let currentNode = result as Node<number>;         // 右子樹存在         if (currentNode.right) {             currentNode = currentNode.right;             // 取右子樹的最左子節(jié)點(diǎn)             while (currentNode.left) {                 currentNode = currentNode.left;             }             return currentNode;         }          // 右子樹不存在         while (currentNode.parent) {             // 當(dāng)前節(jié)點(diǎn)等于它父節(jié)點(diǎn)的左子節(jié)點(diǎn)則條件成立             if (currentNode === currentNode.parent.left) {                 return currentNode.parent;             }             // 條件不成立，繼續(xù)獲取它的父節(jié)點(diǎn)             currentNode = currentNode.parent;         }         return null;     } }

我們通過一個(gè)例子來測試下上述代碼：

// 構(gòu)建二叉搜索樹 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); // 尋找下一個(gè)節(jié)點(diǎn) const nextNode = treeOperate.findBinaryTreeNextNode(tree, 7); console.log("7的下一個(gè)節(jié)點(diǎn)", nextNode.toString());

代碼地址

文中完整代碼如下：

• TreeOperate.ts

• BinarySearchTree.ts

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。