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

周星星1832 · 发表于 4-6-2015 15:19:53

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有帐号？FreeOZ用户注册

x

好吧。。。我已经一脑子浆糊。。。。。。。。。。

一颗巨大的树
判断一個Ａ节点是另外一個节点Ｂ的子孙。。。
我想到的两种方法
(1)
递归看Ｂ的childeren有没有Ａ。。有Ａ的返回。。。没有的话要遍历所有子孙
(2)
递归看A的parent有没有B。。有Ｂ的返回没有的话要到ＲＯＯＴ

哪个更有效率哇。。。還是有更有效率的方法
還是根本就没有更有效率的方法。。

我目前用（2）。至少遍历是单线

周星星1832 · 发表于 4-6-2015 15:20:28

@DDD888

周星星1832 · 发表于 4-6-2015 15:25:50

貌似根據ＡＢ节点的位置不同。。最短路径都会不同。。。。

vivicats · 发表于 4-6-2015 15:29:51

毫无疑问2最优

周星星1832 · 发表于 4-6-2015 15:31:00

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

我也是这种感觉

浮云云艾米莉 · 发表于 4-6-2015 15:48:10

肯定是2啊。。。b如果有x个children, A在第y层，1要走x^y, 2只要走y

周星星1832 · 发表于 4-6-2015 15:56:38

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

也不一定。。
如果Ａ是Ｂ的子孙。。且是很近的子孙。。而且树枝少的话。。。很快就找到了
但是方法二要一直遍历到root。。

ArBen · 发表于 4-6-2015 16:09:24

怎么完全蒙圈了

melody_iic · 发表于 4-6-2015 16:13:25

运算复杂度应该选最坏情况计算

如果A是B的子孙，方法1的运算复杂度是AB层数差是指数关系，方法2是AB层数差的线性关系
如果A不是B的子孙，方法1的运算复杂度是B到最远叶子层数的指数关系，方法2是A层数的线性关系

综上，方法2胜出

周星星1832 · 发表于 4-6-2015 16:16:57

ArBen 发表于 4-6-2015 15:09
怎么完全蒙圈了

你是IT吗

周星星1832 · 发表于 4-6-2015 16:23:00

melody_iic 发表于 4-6-2015 15:13
运算复杂度应该选最坏情况计算

如果A是B的子孙，方法1的运算复杂度是AB层数差是指数关系，方法2是AB层数 ...

是不是还应该结合实际应用情况来看。。。

判断子孙是肯定要的。。。

但是是子孙的情况比较少。。因為是子孙属于用户判断错误。。。多数情况用户判断应该是正确的
也就是说多数情况下应该不是子孙。。是parent。。。。

所以還是2胜出。。。

melody_iic · 发表于 4-6-2015 16:27:24

理论结合实际，正解

ArBen · 发表于 4-6-2015 16:28:45

周星星1832 发表于 4-6-2015 15:16
你是IT吗

不是完全早不到节奏

周星星1832 · 发表于 4-6-2015 16:36:38

melody_iic 发表于 4-6-2015 15:27
理论结合实际，正解

清醒了我

周星星1832 · 发表于 4-6-2015 16:36:53

ArBen 发表于 4-6-2015 15:28
不是完全早不到节奏

那你肯定完全不懂

ArBen · 发表于 4-6-2015 17:08:16

周星星1832 发表于 4-6-2015 15:36
那你肯定完全不懂

你能写不是挨踢男禁入不

周星星1832 · 发表于 4-6-2015 17:09:53

ArBen 发表于 4-6-2015 16:08
你能写不是挨踢男禁入不

脑补一下挨踢知识也是好的

ArBen · 发表于 4-6-2015 17:11:27

周星星1832 发表于 4-6-2015 16:09
脑补一下挨踢知识也是好的

会帮助泡妞嘛

周星星1832 · 发表于 4-6-2015 17:12:30

补一下应用情况
用户需要给子树设置新的parent
所以在设置前系统需要判断是不是能设置
也就是不能让子树节点作为parent

MICHELLE07 · 发表于 4-6-2015 17:30:41

周星星1832 发表于 4-6-2015 15:36
那你肯定完全不懂

弄点大家都懂的挨踢题目给我们玩玩

周星星1832 · 发表于 4-6-2015 17:31:41

ArBen 发表于 4-6-2015 16:11
会帮助泡妞嘛

你的人生能不能有点更高的追求

周星星1832 · 发表于 4-6-2015 17:32:08

MICHELLE07 发表于 4-6-2015 16:30
弄点大家都懂的挨踢题目给我们玩玩

今天头都大了。。

ArBen · 发表于 4-6-2015 17:53:18

周星星1832 发表于 4-6-2015 16:31
你的人生能不能有点更高的追求

难就介点出息了

周星星1832 · 发表于 4-6-2015 19:14:30

ArBen 发表于 4-6-2015 16:53
难就介点出息了

你就不能投入的爱一次

ArBen · 发表于 4-6-2015 19:20:26

周星星1832 发表于 4-6-2015 18:14
你就不能投入的爱一次

你就不能投入的爱一次

周星星1832 · 发表于 4-6-2015 19:31:21

ArBen 发表于 4-6-2015 18:20
你就不能投入的爱一次

我每次都很投入

ArBen · 发表于 4-6-2015 19:43:59

周星星1832 发表于 4-6-2015 18:31
我每次都很投入

一共几次

ArBen · 发表于 4-6-2015 19:44:05

周星星1832 发表于 4-6-2015 18:31
我每次都很投入

一共几次

周星星1832 · 发表于 4-6-2015 19:46:42

ArBen 发表于 4-6-2015 18:43
一共几次

2次。。。。我只谈过两次恋爱

ArBen · 发表于 4-6-2015 21:26:39

周星星1832 发表于 4-6-2015 18:46
2次。。。。我只谈过两次恋爱

读书少你不要骗俺

		自动登录	找回密码
密码			FreeOZ用户注册

FreeOZ

[IT技术] 树的遍历，判断子孙問題，求最有效率算法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

评分

评分

评分

FreeOZ

[IT技术] 树的遍历， 判断子孙問題，求最有效率算法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

评分

评分

评分

[IT技术] 树的遍历，判断子孙問題，求最有效率算法