后继节点

作者: 一凡呀 | 来源:发表于2017-11-27 11:56 被阅读0次

问题:

求一个二叉树中一个节点的后继节点(后继节点是中序遍历后的集合每个元素的下一个元素)

思路:

后继节点一共有两种情况,一种情况是当前节点有右子树,那么当前节点的后继节点一定在它的右子树上,即为右子树的最左边(这里的最左边是指当前结点的右孩子以及之下它的右孩子之下的树结构的最左边),比如下图


image.png

第二种情况是,当前结点没有右子树,那么就依次网上找,找到一种情况是当前节点是它的父亲节点的左孩子的时候,那么这个父亲节点就是我原始节点的后继节点

代码:

public static Node getNextNode(Node node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

相关文章

  • 后继节点

    问题: 求一个二叉树中一个节点的后继节点(后继节点是中序遍历后的集合每个元素的下一个元素) 思路: 后继节点一共有...

  • Python数据结构与算法2——双向链表

    双向链表 后继节点:指向下一个节点 前驱节点:指向前一个节点 头节点没有前驱节点,尾节点没有后继节点 实现功能 该...

  • 2018-09-07

    树的基本定义: 树是一种非线性结构,有一个直接前驱,可能有很多个后继 根节点:没有前驱结点 叶子节点:没有后继节点...

  • 19-前驱节点和后继节点

    一、前驱节点 二、后继节点 代码以二叉搜索树为例: 三、完善二叉搜索树代码,remove只针对二叉搜索树 删除代码...

  • 十三、前驱节点(predecessor)&后继节点(succes

    前驱节点(predecessor) 前驱节点:中序遍历时的前一个节点如果是二叉搜索树,前驱节点就是前一个比它小的节...

  • 中序建立线索二叉树

    为什么使用中序遍历来建立线索二叉树? 因为中序遍历方便寻找前驱节点和后继节点,而先序遍历不方便找后继节点,后序遍历...

  • 剑指 Offer II 053. 二叉搜索树中的中序后继

    给定一棵二叉搜索树和其中的一个节点 p ,找到该节点在树中的中序后继。如果节点没有中序后继,请返回 null 。 ...

  • 面试题 04.06. 后继者

    面试题 04.06. 后继者设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。 如果指定节点...

  • Redis源码分析(二)——Redis数据结构-链表

    数据结构——节点 prev:链表节点的前驱 next:链表节点的后继 value:节点中的值 数据结构——链表 h...

  • 二叉搜索树的前驱和后继节点

    前驱节点val值小于该节点val值并且值最大的节点后继节点val值大于该节点val值并且值最小的节点 BST.pn...

网友评论

    本文标题:后继节点

    本文链接:https://www.haomeiwen.com/subject/rxwrbxtx.html