惯用遍历二叉树（可能是任何树）
一个双重链接列表可以实现对链接列表的惯用遍历，我想为什么不使用二叉树呢？传统上，二叉树或树一般是单向的，这意味着，给定一棵有足够数量节点的大树，查找叶节点的运行时间可能是昂贵的。
如果在找到这样一个节点后，为了找到下一个节点，我可以朝着根方向遍历树，那么与通过树的每个节点的另一个深度优先搜索相比，这不是很有利吗？我以前从未考虑过这一点，直到我意识到双链表和二叉树的结合可能会增加好处。
例如，如果我雇佣了一个内部类
class Tree<T> {
private class TwoWayNode {
var data : T
var left : TwoWayNode
var right : TwoWayNode
var previous : TwoWayNode
}
}
使用left和right与从每个节点遍历相应子树一样正常，而previous将保存指向父节点的指针，从而实现惯用遍历。有些东西能很好地工作吗？有哪些潜在的问题或陷阱？
共有2个答案
事实上，二叉树的节点通常是通过指向左、右子级和父级的指针来实现的（参见红黑树的实现）。
但您并不总是需要父指针：
- 对于顺序遍历，您可以使用递归算法，以便调用堆栈为您处理。
- 如果你想访问最小或最大节点，你可以简单地保持一个额外的指针到他们。
- 有时你可以用手指树。
- 或者组织你的指针非常聪明（见自调整二叉搜索树第666页）：
- 一个节点的左指针指向第一个（左）子节点
- 节点的右指针指向兄弟姐妹（如果是左子节点）或返回父节点（如果是右子节点）
额外的酷：线程化的二进制搜索树，无需堆栈就可以进行非常简单的按序（和逆序）遍历-so（1）空间！
如果您存储了一个上一个引用，您可以先从最左边走。到达叶节点后，再次备份一个，向右遍历。
您始终可以将当前节点（您的“walker”）与子节点进行比较，以便检查上次是向左还是向右。这使得遍历无状态，甚至不需要递归；适用于非常大的数据集。
现在，每次你离开右边的叶子时，你都会再次备份一片。
该算法是深度优先搜索*
使其更快：假设您可以为遍历顺序定义一些确定性条件，那么这将变得非常灵活，甚至可以在光线跟踪等应用程序中使用。
*：http://en.wikipedia.org/wiki/Depth-first_search
奖励：这篇关于光线跟踪中Kd树遍历算法的论文：综述：光线跟踪中的Kd树遍历算法(http://dcgi.felk.cvut.cz/home/havran/ARTICLES)/cgf2011。pdf
-
如果水平顺序遍历优于rest遍历，那么在二叉搜索树中学习它们有什么用呢？ 与顺序遍历和前序遍历相比，级别顺序遍历似乎更容易获取信息。
-
主要内容：层次遍历的实现过程,实现代码前边介绍了 二叉树的先序、中序和后序的遍历算法，运用了 栈的 数据结构，主要思想就是按照先左子树后右子树的顺序依次遍历树中各个结点。 本节介绍另外一种遍历方式：按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用 队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层
-
为了上课，我必须创建一个状态对象的二叉树，每个状态对象包括一个居民对象的二叉树，这些居民对象组织住在每个州的人。我试图在一个给定的州中搜索最老的居民；然而，居民是按字母顺序组织在树中的，这对我的搜索毫无帮助。因此，我必须遍历整个居民树，更新保存最老的人的节点，并在树被完全遍历后返回它。我已经有了代码的第一部分，但是还停留在如何写递归的剩余部分。 状态树的方法： 然后是公共“包装器”状态树方法：
-
中序遍历二叉树 按完全二叉树的层次遍历给出一棵二叉树的遍历序列（其中用0表示虚结点），要求输出该二叉树的深度及中序遍历该二叉树得到的序列。 输入格式: 首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据首先输入一个正整数n（n≤1000），代表给出的二叉树的结点总数（当然，其中可能包含虚结点）。结点编号均为正整数,且各不相同。 然后输入n个正整数，表示按完全二叉树（即第1层1
-
本文向大家介绍二叉树 Z 字型遍历相关面试题，主要包含被问及二叉树 Z 字型遍历时的应答技巧和注意事项，需要的朋友参考一下 考察点：遍历
-
我已经实现了一个四叉树来对图形中的点进行排序。每当一个点落在已经包含一个点的象限内时，该象限就会再次细分，以允许每个点落入其自己的象限。每个节点都具有以下属性： 假设我想遍历存储在这棵树中的每个节点，并计算落在给定矩形边界内的点数，我将如何递归检查树中的每个节点（假设我已经有方法检查它们是否落在某个区域）？