标签: binary-tree

我如何编写一个Java迭代器(即需要next和hasNext方法),它采用二叉树的根,并按顺序迭代二叉树的节点？

我正在阅读Steve Yegge关于单身人士的文章.在其中他提到他的老师告诉他AVL树是邪恶的.只是红色和黑色的树木是更好的解决方案吗？

根据维基百科,

树的高度是树中从根到最深节点的路径长度.只有一个节点(根)的(根)树的高度为零(或一).

我不明白 - 它是零还是一个(或两者)？

在我看来,Pre-order遍历和DFS与我们以深度方式遍历叶节点的两种情况相同.如果我错了,有人可以纠正我吗？

提前致谢!

问题

假设我有两个间隔集合,名为A和B.如何以最节省时间和内存效率的方式找到差异(相对补充)？

图片说明:

间隔时间点是整数(≤2 ¹²⁸ -1),他们总是两个2 ^ñ长排列的M×2 ^ñ晶格(这样就可以使一个二叉树了出来).

间隔可以在输入中重叠,但这不会影响输出(如果平坦的结果相同,则结果).

问题是因为两个集合中都有多个间隔(最多100,000,000),所以天真的实现可能会很慢.

从两个文件中读取输入,并按照这样的方式对输入进行排序:较小的子间隔(如果重叠)紧接在父项之​​后按大小顺序排列.例如:

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

我试过了什么？

到目前为止,我一直致力于生成二进制搜索树的实现,同时聚合[0,3],[4,7] => [0,7]两个集合中的相邻interval(),然后遍历第二个树并"碰撞"两个中存在的间隔(细分更大的必要时在第一个树中的间隔).

虽然这似乎适用于小型集合,但它需要越来越多的RAM来保存树本身,更不用说完成从树中插入和删除所需的时间.

我认为,由于间隔是预先排序的,我可以使用一些动态算法并在一次通过中完成.但是,我不确定这是否可行.

那么,我将如何以有效的方式解决这个问题呢？

免责声明:这不是作业,而是对我所面临的实际现实问题的修改/概括.我用C++编程,但我可以接受任何[命令式]语言的算法.

我对算法类的以下作业问题感到难过:

假设我们给出了一个n值x ₁,x ₂ ... x _n的序列,并寻求快速回答形式的重复查询:给定i和j,找到x _i ... x _j中的最小值

设计一个使用O(n)空间的数据结构,并在O(log n)时间内回答查询.

首先,我不确定一个序列是指一个有序集合,还是一个未排序的集合 - 但由于它没有说明,否则我会假设序列意味着未排序.

所以,我意识到这显然必须涉及二叉树,如果我们谈论的是O(log N)查找时间.所以基本上,我想,你有一个集合S,并将每个元素插入S到二叉树中.问题是,这个问题基本上要求我想出一种方法来回答查询,其中我将一系列索引分配到未排序的集合中 - 然后在O(log N)时间内确定该范围中的最低值.怎么可能？即使将每个数量的集合插入树中,我能做的最好的事情是在O(log N)时间内查找任何特定的数字.这不允许我在未排序的数字范围内找到最低值S.

有什么建议？

我之前的一篇学术课程中有以下关于二阶树(不是BST)的有序遍历(它们也称之为pancaking)的文本:

有序树遍历

在树的外面画一条线.从根的左侧开始,绕过树的外部,最后到根的右侧.尽可能靠近树,但不要越过树.(想想树 - 它的分支和节点 - 作为一个坚实的障碍.)节点的顺序是这条线在它们下面经过的顺序.如果您不确定何时"在节点下面",请记住"左侧"节点始终位于第一位.

这是使用的示例(从下面略微不同的树)

但是,当我在谷歌搜索时,我得到一个相互矛盾的定义.例如维基百科的例子:

顺序遍历序列:A,B,C,D,E,F,G,H,I(左子节点,根节点,右节点)

但根据(我的理解)定义#1,这应该是

A,B,D,C,E,F,G,I,H

任何人都可以澄清哪个定义是正确的？它们可能都描述了不同的遍历方法,但碰巧使用相同的名称.我很难相信同行评审的学术文本是错误的,但不能确定.

这困扰了我一段时间.我知道,如果N键以二叉搜索树的形式排列,可以创建的树的可能数量对应于加泰罗尼亚序列中的第N个数字.

我一直试图确定这是为什么; 无法找到任何甚至可能试图直观地解释它的东西我诉诸于SO的集体知识.我找到了计算可能树木数量的其他方法,但它们似乎不太直观,除了如何使用它之外没有提供任何解释.加上维基页面(上面的链接)甚至可以显示带有3个键的可能树形图的图像,这将使我认为有一个很好的和整洁的解释可以被听到(不用说,不包括在文章中) ).

提前致谢!

C#(或.net)中是否有代表二叉树(或好奇心)和n-ary树的对象？

我不是在谈论表示树控件,而是作为模型对象.

如果没有,是否有任何良好的外部实现？

我最喜欢的面试问题之一是

在O(n)时间和O(1)空间中,确定链表是否包含循环.

这可以使用Floyd的循环寻找算法来完成.

我的问题是,在尝试检测二叉树是否包含循环时,是否可以获得如此好的时间和空间保证.也就是说,如果有人给你一个struct定义

struct node {
    node* left;
    node* right;
};

您如何有效地验证给定结构确实是二叉树,而不是DAG或包含循环的图形？

是否存在一种算法,给定二叉树的根,可以确定该树是否包含O(n)时间并且优于O(n)空间的循环？显然,这可以使用标准DFS或BFS来完成,但这需要O(n)空间.可以在O(√n)空间内完成吗？O(log n)空间？或者(O圣)在O(1)空间？我很好奇,因为在链表的情况下,这可以在O(1)空间中完成,但我从未见过相应有效的算法.