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

DDD888

vivicats 发表于 4-6-2015 14:29
毫无疑问2最优

I agree

May I ask how big is the tree? If space is not an issue and if just want fastest way, maybe just use a hash table to store each node link with all parents as a comma delimited string, just one hash lookup and a text search on the csv will get the answer

cais

浮云云艾米莉 发表于 4-6-2015 14:48
肯定是2啊。。。b如果有x个children, A在第y层，1要走x^y, 2只要走y

这律师也来抢我们的饭碗了啊。。。

cais

周星星1832 发表于 4-6-2015 14:56
也不一定。。
如果Ａ是Ｂ的子孙。。且是很近的子孙。。而且树枝少的话。。。很快就找到了
但是方法二要 ...

A是B的子孙的话，方法二不是也能很快的找出来吗？

cais

这个题有没有其它的信息，比如知道每个节点在树里面的深度。知道的话，方法二就可以提前结束了。
或者是树的节点有某种排序。
如果没有其它信息，你这两个方法，怎么样都是二比较有效啊。

superopengl

这还取决于树的数据结构。如果每个node都保存the path from root to self的话，判断A是否是B的子孙，只要判断A.PathToRoot.Contains(B.PathToRoot)即可。是个O(1)的算法。

这种树不适合频繁移动和插入node操作。因为所有被移动subtree上的所有node都需要修改PathToRoot.

周星星1832

ArBen 发表于 4-6-2015 20:26
读书少 你不要骗俺

这是标准答案。。记住了。。。下回别人问你
你也这么说

周星星1832

DDD888 发表于 4-6-2015 20:44
I agree

May I ask how big is the tree? If space is not an issue and if just want fastest way, m ...

可能很大。。。。。
取决于用户建多大
节点是存储在数据库的
但是树是一次性load的
所以判断的时候是js判断的。没在后台判断

周星星1832

cais 发表于 5-6-2015 00:07
A是B的子孙的话，方法二不是也能很快的找出来吗？

没有啊。。是子孙的话
也就是说不是parent。所以药一直到遍历到root才知道
假设是直接子孙就一层
这个情况2就不是很有效率了

周星星1832

cais 发表于 5-6-2015 00:10
这个题有没有其它的信息，比如知道每个节点在树里面的深度。知道的话，方法二就可以提前结束了。
或者是树 ...

树的深度。节点多少都是随机的。。因为都是用户决定的

周星星1832

superopengl 发表于 5-6-2015 01:06
这还取决于树的数据结构。如果每个node都保存the path from root to self的话，判断A是否是B的子孙，只要判 ...

这个不太可能。。。没保存过这个路径
确实不适合频繁改动。但是也确实改动的很频繁

ArBen

周星星1832 发表于 5-6-2015 05:58
这是标准答案。。记住了。。。下回别人问你
你也这么说

ArBen

周星星1832 发表于 5-6-2015 05:58
这是标准答案。。记住了。。。下回别人问你
你也这么说

周星星1832

ArBen 发表于 5-6-2015 08:12

非诚勿扰上这么说的

ArBen

周星星1832 发表于 5-6-2015 08:14
非诚勿扰上这么说的

岛国爱情片？

周星星1832

ArBen 发表于 5-6-2015 08:21
岛国爱情片？

浮云云艾米莉

cais 发表于 5-6-2015 00:04
这律师也来抢我们的饭碗了啊。。。

算法，大学不是都学过的嘛！

不许鄙视数学出身的人。。。

vivicats

周星星1832 发表于 5-6-2015 06:02
没有啊。。是子孙的话
也就是说不是parent。所以药一直到遍历到root才知道
假设是直接子孙就一层

不需要遍历到root，如果是子孙的话，一直找parent node，一定可以找到B，然后就结束了。

遍历到root只有最坏情况，也就是A不是B的子孙。我觉得唯一1比2优的情况就是A不是B的子孙，而且B的所有子孙节点个数小于B的深度。

周星星1832

vivicats 发表于 5-6-2015 09:24
不需要遍历到root，如果是子孙的话，一直找parent node，一定可以找到B，然后就结束了。

遍历到root只 ...

恩。。最坏的情况就是用户犯错。。。Ａ是Ｂ的子孙。。。二就要遍历到root..
不过这种情况应该很少见。。。所以還是2是最优的

只是这总少见情况下。。1才有可能比2路径短

khing

周星星要找工作？

周星星1832

khing 发表于 9-6-2015 16:14
周星星要找工作？

暂时还不找

wiserfirst

看了讨论，似乎已经有结论了，即方法2在大部分情况下会更高效。
但是我有个问题，为什么方法2要用递归呢，一个循环从A开始一路找自己的Parent，要么找到B，要么找到Root，不就行了吗？不知道 @周星星1832 用什么语言，但是循环的效率至少不会比递归差吧

周星星1832

wiserfirst 发表于 9-6-2015 22:31
看了讨论，似乎已经有结论了，即方法2在大部分情况下会更高效。
但是我有个问题，为什么方法2要用递归呢， ...

没法循环。。因为不知道多少个parent。也没法一下子获取所有parent节点
只能一层层的递归上去
这个应用是javascript

DDD888

周星星1832 发表于 10-6-2015 06:46
没法循环。。因为不知道多少个parent。也没法一下子获取所有parent节点
只能一层层的递归上去
这个应用 ...

while loop 行吗？

周星星1832

DDD888 发表于 10-6-2015 09:24
while loop 行吗？

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

复制代码

貌似可以

周星星1832

其实感觉還是递归比while 更简洁

vivicats

一个while loop就解决了，递归有点多此一举了，要考虑到递归不管从效率还是内存空间使用上，都差于loop，递归要保存当前的所有状态，在这个例子是完全是没用的

周星星1832

vivicats 发表于 10-6-2015 11:35
一个while loop就解决了，递归有点多此一举了，要考虑到递归不管从效率还是内存空间使用上，都差于loop，递 ...

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

复制代码

vivicats

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

这样写短一点

        function is_child(setNewParentId, thisId) {
                    var parentConns, parentId;
                while (thisId != setNewParentId && thisId != 0) {
                        parentConns = instance.getConnections({ target:[thisId],  scope:["cause", "combo"] },true);
                        parentId = parentConns[0].sourceId;
                }
                return (thisId == setNewParentId);
            }

ps: 不太会写javascript，见笑了，另外不知道怎么编辑格式，凑合着看吧

周星星1832

vivicats 发表于 10-6-2015 12:05
这样写短一点

        function is_child(setNewParentId, thisId) {

nice

khing

周星星1832 发表于 9-6-2015 16:15
暂时还不找

那是工作中遇到的问题啊？好高大上

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

1. bool isParent(node *a, node *b) {
   
2.   if (!a) return false;
   
3.   if (a->l == b || a->r == b)
   
4.      return true;
   
5.   return isParent(a->l, b) || isParent(a->r, b);
   
6. }

复制代码

不好意思，俺只会C++