- 节点1有子节点2和3。 - 节点2有子节点4和5。 - 节点3有子节点6和7。 - 等等。
在深度D处将有2^D个节点,编号为2^D...2^(D+1)-1。
对于任何深度的完全树,其深度优先搜索遍历是确定的。
例如,深度为4的树将始终被遍历为:1、2、4、8、9、5、10、11、3、6、12、13、7、14、15。
我正在寻找一种方法来通过它们在任何树的DFS遍历中出现的位置来排序数字列表。
特别地,我想要一个比较函数,可以取两个数字并确定哪个在DFS遍历中先出现。
有什么想法吗?
预先计算某些最大树大小的DFS遍历是一种方法,但我更喜欢不需要计算和存储该信息的数学解决方案。