寻找二叉树的下一个节点

简介: 寻找二叉树的下一个节点

前言


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


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


问题分析


正如前言所述,我们的已知条件如下:


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


我们要解决的问题:


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


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


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


640.png


在保存父节点引用时折腾了好久也没实现,最后求助了我的朋友_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());


640.png


代码地址


文中完整代码如下:

  • TreeOperate.ts
  • BinarySearchTree.ts


写在最后


  • 公众号无法外链,如果文中有链接,可点击下方阅读原文查看😊
相关文章
【Leetcode -872.叶子相似的树 -993.二叉树的堂兄弟节点】
【Leetcode -872.叶子相似的树 -993.二叉树的堂兄弟节点】
38 0
|
6月前
|
存储
二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)
二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)
|
5月前
【树 - 平衡二叉树(AVL)】F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量
【树 - 平衡二叉树(AVL)】F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量
|
12月前
二叉树子树结点个数
二叉树子树结点个数
53 0
二叉树的中后序遍历构建及求叶子
二叉树的中后序遍历构建及求叶子
134 0
|
数据安全/隐私保护
列出叶节点 (二叉树的建立和BFS)
列出叶节点 (二叉树的建立和BFS)
91 0
二叉树的后继节点
二叉树的后继节点
68 0
剑指offer_二叉树---二叉树的下一节点
剑指offer_二叉树---二叉树的下一节点
66 0
剑指offer 07. 二叉树的下一个节点
剑指offer 07. 二叉树的下一个节点
60 0
二叉树的前中后序遍历以及求深度、叶子节点和二叉树的重建
二叉树的前中后序遍历以及求深度、叶子节点和二叉树的重建
70 0