本文轉載自微信公眾號「神奇的程序員k」，作者神奇的程序員K。轉載本文請聯(lián)系神奇的程序員k公眾號。  

前言

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

本文就跟大家分享下這個問題的解決方案與實現(xiàn)代碼，歡迎各位感興趣的開發(fā)者閱讀本文。

問題分析

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

• 包含父節(jié)點引用的二叉樹
• 要查找的節(jié)點

我們要解決的問題：

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

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

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

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

• 8的下一個節(jié)點是9
• 3的下一個節(jié)點是6
• 7的下一個節(jié)點是8

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

• 要查找的節(jié)點存在右子樹，那么它的下一個節(jié)點就是其右子樹中的最左子節(jié)點
• 要查找的節(jié)點不存右子樹：
  • 當前節(jié)點屬于父節(jié)點的左子節(jié)點，那么它的下一個節(jié)點就是其父節(jié)點本身
  • 當前節(jié)點屬于父節(jié)點的右子節(jié)點，那么就需要沿著父節(jié)點的指針一直向上遍歷，直至找到一個是它父節(jié)點的左子節(jié)點的節(jié)點

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

實現(xiàn)思路

• 二叉樹中插入節(jié)點時保存其父節(jié)點的引用
• 調用二叉樹的搜索節(jié)點方法，找到要查找的節(jié)點信息
• 判斷找到的節(jié)點是否存在右子樹
• 如果存在，則遍歷它的左子樹至葉節(jié)點，將其返回。
• 如果不存在，則遍歷它的父節(jié)點至根節(jié)點，直至找到一個節(jié)點與它父節(jié)點的左子節(jié)點相等的節(jié)點，將其返回。

實現(xiàn)代碼

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

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

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

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

保存父節(jié)點引用

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

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

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

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é)點引用時折騰了好久也沒實現(xiàn)，最后求助了我的朋友_Dreams😁。

尋找下一個節(jié)點

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

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

代碼地址

文中完整代碼如下：

• TreeOperate.ts
• BinarySearchTree.ts