标题:这么多天了,搜索二叉树才搞定了最基础的部分(蹉跎了好些岁月,终于搞定了 ...
只看楼主
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 30楼 renkejun1942
除了按层遍历~其余三种迭代遍历都是输出位置不同~有的网上代码认为后序遍历难度最高~不过自我感觉就是输出位置不同嘛~在数据结构写了一个三种遍历合并在一个函数里面(通过调用参数决定遍历类型)自我感觉不错不过就是没有什么浏览量~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-12 20:16
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-05-12 20:18
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 32楼 renkejun1942
不是说用栈来代替递归么~难道不调用递归函数也是叫做递归~~

https://bbs.bccn.net/thread-475553-1-1.html

可以看看这个~虽然感觉自己写得很长不过却很好理解~很容易看懂自己在干什么~

[此贴子已经被作者于2017-5-12 20:53编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-12 20:50
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
得分:0 
回复 33楼 九转星河
都已经搞定了。以后找时间看吧。
现在准备睡觉,明天很早要上班。

我的版本,在一定程度上模拟了递归。
我是怎么写出来的呢?嗯,我先手动将递归版本全部展开,然后……开写。

[此贴子已经被作者于2017-5-12 21:00编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-12 20:55
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 34楼 renkejun1942
好的~准备好就可以去看看线索二叉树~我手头有些资料还差消化其中内容~我打算弄好这个再看AVL树~毕竟感觉一起讨论总比摸着石头过河好~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-12 21:00
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
得分:0 
回复 35楼 九转星河
我收回我前几天说的,希望下周进入AVL树环节。
我低估了二叉树,嗯……准确说我对二叉树理解不够深,会比较好。
所以……我觉得在二叉树上在停停会比较好。

搜索了一下线索二叉树,不太明白。我的书上貌似没有这中结构。

[此贴子已经被作者于2017-5-12 21:07编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-12 21:03
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
得分:0 
回复 10楼 书生牛犊
我现在可以回答你的这个问题了。
用void*作为二叉树的值域为什么不行,当然如果只是自己用的话,这样做当然可以,但是如果拿出去给别人用,就不行了。
原因在于,二叉树的特性,左小右大,如果由使用者提供比较函数,那么树的特性分分钟被破坏,这不是假设,而是会很快发生的现实。

如果树的特性被破坏,那么一切树的操作(除了遍历)都成了空谈。犹如对未排序的数组使用折半查找。

我想了很久,想不到解决办法,唯一的办法是,只有自己用。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-18 10:31
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 37楼 renkejun1942
不是使用者知道这一规则就可以避免这种问题么~快排也是一样啊~确认了比较规则就可以知道该值在二叉树的走向了~要么不用比较函数~要么所有相关判断都用用户自己写的比较函数~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-18 17:16
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
得分:0 
回复 38楼 九转星河
这很明显不会因知道规则就可以避免,我举个例子,所有人都知道吸毒有害,但还是有人吸毒。

快速排序函数,规则是前者大于后者返回正数,否则返回负数。
对吧?
但是你知道如果反过来,让前者大于后者返回负数,否则返回正数可以做到降序排序么?

这样是对规则的破坏吗?我不太清楚,但是排序函数而言,无所谓的,但是换在二叉树上,二叉树的特性就遭到了破坏。


如果代码的编写者,自己来编写比较函数,这对于基本类型是很简单的,但是派生类型呢?结构呢?联合呢?你得写多少的比较函数?

[此贴子已经被作者于2017-5-18 17:41编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-18 17:39
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 39楼 renkejun1942
其实比较无异于两种~一种是数值大小~一种是字符串大小~~~派生类型的比较可以转化为那四种基本类型的比较~~

还有~如果按你的说法~那岂不是通用二叉树会出现影响二叉树特性的情况?~或者说还是不弄通用二叉树好~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-18 19:13



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-476865-1-1.html




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

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