二叉树的下一个结点

思路:

(1)若该节点存在右子树:则下一个节点为右子树最左子节点(如图节点B)

(2)若该节点不存在右子树:这时分两种情况:

2.1 该节点为父节点的左子节点,则下一个节点为其父节点(如图节点D)

2.2 该节点为父节点的右子节点,则沿着父节点向上遍历,直到找到这样一个节点:它是它父节点的左子节点,则该节点的父节点就是我们要找的(如图节点I,沿着父节点一直向上查找找到B(B为其父节点的左子节点),则B的父节点A为下一个节点)。

其实(2)也可以总结为一点:若该节点不存在右子树,则沿着父节点向上遍历,直到找到这样一个节点:它是它父节点的左子节点,则该节点的父节点就是我们要找的

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,...
    lqsss阅读 535评论 0 0
  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,526评论 1 31
  • 按照中序排序,求二叉树的下一个结点。 分析下一个结点: (1)如果当前结点存在右结点, 那么它的下一个结点就是它的...
    BeijingIamback阅读 327评论 0 1
  • 题目描述给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点...
    GoDeep阅读 224评论 0 0
  • 题目描述给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点...
    NoFacePeace阅读 152评论 0 0