在我们需要快速查询后代或者祖先的需求中，预排序遍历树算法就显示了出来
预排序遍历树算法顾名思义其实在数据落地之前就计算好了顺序，是一种有序的树状结构
这种树，依赖左值与右值来快速排序
如图：
WechatIMG399.jpeg
祖先的左值如果从N开始排序，子孙的左值则N+1,，右值则为(N+1)+1，如果父级有两个子孙节点，那么从该子孙节点的右节点的左值就左节点的右值N+1,右值则为(N+1)+1
从上图中,假定我们需要搜索某个祖先下的后代
如：第二代的2 -7
那么left>2 并且同时满足条件 right<7 即为它的后代
在上图中,假定我们需要查询某个子孙的祖先
如：第三代的 3 - 4
那么left<3 并且同时满足条件 right > 4 即为它的祖先
网友评论