mappingTree构造

添加结点MappingNode

增加子结点策略:每个结点下面有多个子节点,每个节点主要记录最左子结点和右兄弟结点,多个孩子时,子结点按照从大到小顺序从左到右进行排序。最右面的结点的有兄弟结点=null
root:root节点
leftMostChild :root结点的最左子结点
child:当前要插入的结点
position:遍历的计数器,记录遍历的当前结点
prev:遍历的计数器,记录遍历的当前节点的前一个结点

public void linkAsChild(final MappingNode child) {
1.leftMostChild 不存在,root添加child作为leftMostChild
if (this.leftMostChild == null) { this.leftMostChild = child;
2.leftMostChild存在,依次遍历子结点,从leftMostChild 开始:
} else { MappingNode prev = null; MappingNode position = this.leftMostChild; while (true) {
2.1position=null,遍历到最右,将child添加到最后一个子结点prev后
if (position == null) { prev.sibling = child; break; }
2.2child>position,
int c = child.getMapping().compareTo(position.getMapping()); if (c < 0) {
2.2.1prev==null,root添加child作为leftMostChild
child.sibling = position; if (prev == null) { this.leftMostChild = child;
2.2.2prev!=null,child插入prev和position中间
} else { prev.sibling = child; } break;
2.3child<=position,比较下一个结点,从1)开始
} else { prev = position; position = position.sibling; } } } }

图:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容