如何找到非二叉树中的第n个节点？

我知道如何遍历一棵二叉树using the answer here，但是如果我想停在预先遍历的第10个节点上，我该怎么做？如何找到非二叉树中的第n个节点？

2014-12-08 Doug Smith

难道你不会只重复遍历遍历n次的树吗？您在预订遍历中看到的每个节点都会增加计数器，并且当计数器== n停止获取当前节点时。

当然是根的前序遍历的第一个，最左边的孩子递归调用，接下来最左边的孩子递归调用，...，最右边的孩子递归调用

2014-12-08 04:12:36 Freestyle076

你如何保持n个轨道有关系吗？给定的遍历实现使用递归，这使得它在这方面变得复杂。 – 2014-12-08 04:36:02

@DougSmith：一种可能性：递归函数需要一个额外的参数，它是要遍历的元素的最大数量，并返回实际遍历的元素数量（可能会少一些）。另一种可能性是：访问者对象维护包含剩余计数的状态，并返回一个布尔值来指示导线是否应该继续。（在这种情况下，递归遍历也必须返回相同的布尔指标。） – rici 2014-12-08 04:48:12

那么，在语言不可知的算法中，我们只需在递归算法之外追踪它，从算法中递增算法。语言不可知的算法不会被迫考虑内存管理。如果我们想获得具体的实现，大多数语言将支持基于参数的计数器和n变量的传递，或者可以使用全局变量来跟踪这两个变量 – Freestyle076 2014-12-08 04:53:14

如何找到非二叉树中的第n个节点？

回答

相关问题