二叉树的下一个结点&二叉树的上一个结点

二叉树的下一个结点

题目:给定一棵二叉树和其中一个结点,如何找出中序遍历的下一个结点,树中的结点除了有两个分别指向左右子结点的指针外,还有一个指向父节点的指针

 最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案  还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有,直接打印右子树中最左的结点即为答案;如果没有,就往上回溯,假设当前结点是x,父节点是p,如果x是p的左孩子,p就是答案,如果不是,就一直向上回溯x = p;p = p.parent;

二叉树的上一个结点

题目:给定一棵二叉树和其中一个结点,如何找出中序遍历的上一个结点,树中的结点除了有两个分别指向左右子结点的指针外,还有一个指向父结点的指针

 这个的做法正好与上面相反,先判断当前结点x是否有左子树,如果有,打印左子树最右的结点;如果没有,还是网上回溯,如果x是p的右孩子,p就是答案

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

二叉查找树

二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

622
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

992
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

2028
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

2965
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列04:重建二叉树 原

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

782
来自专栏编程坑太多

HashMap 源码解析

1242
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

732
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1535
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

2815
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

873

扫码关注云+社区