树的遍历， 判断子孙問題，求最有效率算法

周星星1832

khing 发表于 10-6-2015 22:44
那是工作中遇到的问题啊？好高大上

如果有指向parent的指针，直接循环往回找就是了；

目前的项目确实比较难搞
涉及很多基础的涉及
其实发现知识真的是用的时候才是觉得有用的。。

wiserfirst

周星星1832 发表于 10-6-2015 11:55

我建议把查找parentId的逻辑提取出来，会更清晰一点

1. function get_parent_id(thisId) {
   
2.     var parentId = undefined;
   
3.     if (parentConns = instance.getConnections({ target:[thisId], scope:["cause", "combo"] }, true)) {
   
4.         parentId = parentConns[0].sourceId;
   
5.     }
   
6.     return parentId;
   
7. }
   
8. 
   
9. function is_child(setNewParentId, thisId) {
   
10.     var parentId;
    
11.     while (parentId = get_parent_id(thisId)) {
    
12.         if (parentId === setNewParentId) {
    
13.             return true;
    
14.         } else {
    
15.             thisId = parentId;
    
16.         }
    
17.     }
    
18.     return false;
    
19. }
    

复制代码

周星星1832

wiserfirst 发表于 11-6-2015 17:41
我建议把查找parentId的逻辑提取出来，会更清晰一点

好主意。。。。等我休假回来改代码
昨天早上系统已经go live了。。。

clarkli

2的前提是child node要有指向parent的指针

1的话，如果是二叉搜索树可以做到O(log(N))，否则只能linear了

周星星1832

clarkli 发表于 14-6-2015 14:02
2的前提是child node要有指向parent的指针

1的话，如果是二叉搜索树可以做到O(log(N))，否则只能linear ...

指针算是有
不是二叉树