| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 8435 人关注过本帖, 1 人收藏
标题:字典树(已完成遍历、插入、删除整颗树)
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 30楼 九转星河
听说过森林么?
突然感觉用三个节点表示不如用森林表示~
森林可以简单理解为很多树的集合~
一颗红黑树或者AVL树只储存一级关键字~和下一级关键字的节点~

这样就有了<<一颗树的值是另一棵树>>了~感觉这个设想挺好的哦~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-04 19:13
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 31楼 九转星河
当然知道啊,但是没有深究(以后再去了解这个,先专注眼前的东西),我看的书里面,森林也仅仅是作为一个定义出现。


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-04 19:18
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 31楼 九转星河
你说的一棵树的值是另一棵树,这很容易实现,但问题在于应用在什么地方呢?

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-04 19:18
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 33楼 renkejun1942
就是用于逐字二分法查找啊~
相对于链表的值是另一个链表~那个是树的结构~能够加快一级搜索速度~用AVL平衡树的话26个字母最多遍历5个节点就可以找到该关键字了~虽然时间方面会比楼主的字典树要低一些~不过用森林能最大限度地节约空间啊~

[此贴子已经被作者于2017-6-4 19:26编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-04 19:22
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 33楼 renkejun1942
顺便补充一下~森林里面的二叉树用AVL树或红黑树为佳~当然你说容易实现感觉你理解成一般的二叉搜索树了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-04 19:24
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 34楼 九转星河
减少1级搜索的时间没有什么意义,毕竟就26个字母,无论什么结构,都能飞一般的完成。
减少二级搜索的时间才是关键。

因此树套树,同样会面临空间浪费,只是很少而已,只比链表多一个指针。

其实,为什么不链表套树,或者更直接的数组套树。

是哦,我那个链表,为社么不用数组呢?我傻。。。。。。。。。。。。。

[此贴子已经被作者于2017-6-4 19:28编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-04 19:26
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 35楼 九转星河
我说的很容易实现,意思是,只要写一个接口和实现,就可以直接调用,用这一套函数完成所有操作。
就像我那个链表一样。
唯一需要处理的只有一些细节而已。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-04 19:27
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 36楼 renkejun1942
如果用数组~那和一楼的代码有啥区别~而且数组还是会占用空间的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-04 20:07
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 38楼 九转星河
我的意思是用数组做索引。
数组的每一个元素都是一个对应首字母的树。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-04 20:10
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 39楼 renkejun1942
感觉理解上来还是有点抽象~不知道我理解有没有出入~感觉就是把单词当作数组处理通过其下标值索引然后就可以一下子找到树里面的那个数组下标了~这样听你说却不难实现~可以添加个简单的单词查找功能~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-04 20:17
快速回复:字典树(已完成遍历、插入、删除整颗树)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028853 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved