首页 > 其他 > 详细

学习数据结构的第七天(二)

时间:2020-04-02 18:46:27      阅读:77      评论:0      收藏:0      [点我收藏+]

  然而,刚刚那个替换法是我想的,目前觉得这样替换也是挺符合的吧。

对于我的那种替换法,怎么去调用递归来做,也要去看,锻炼递归的思想,虽然它不是一种很好的方法。

  真正常用的替换方法:技术分享图片

 

右边的最小节点放在被替换位置,或者左边的最大节点放在被替换位置,都是常用的方法,而我挑一个的话,就是拿右边的最小节点放在被替换位置。

 

我用的替换方法,涉及到一些递归的知识在里面,也是需要再写一下我的那个方法的remove。

key1:  注意,对这个函数的定义:返回删除之后的根的节点。  (原因:因为对于树结构的操作,它的目的如下图)

技术分享图片假设需要做的是:用n.left来替换n  那么用node  n1=n;n=n.left这样可以吗?

 

 技术分享图片

 

 实际上发生的过程是:    node这个指针,从指向当前位置到指向了node.left位置

 

因此,最终的启发:  如果说要改变树的结构,用A结点来替换B结点,那么需要做的是:返回替换后的根给它,而不是指针性的改变。

与之同理的是:  add函数,添加某个节点进树里面,也是返回替换后的根给它,而不是说指针性改变。

技术分享图片

 

 技术分享图片

 

 因此,你就能够理解,为什么是上面的做法对,而不是下面的做法了。

因为你是要返回替换后的根给它,所以上面的做法,左边的根  就是remove后的左边的根  右边的根,就是remove后的右边的根。

抓准函数的内涵。

 

第二点:  最大的节点,它可以有左子树(左边的一连串都行,不仅仅可以有左子节点,因为的话左边子树都比它小)

                最小的节点,可以有右子树(左边的一连串都行,不仅仅可以有左子节点,因为的话左边子树都比它小)

技术分享图片 这里的话,如果说删除的是M节点的话,  那么删除的意思:   I.right=N,而不是说指针性替换。    如果说不使用递归的方法返回根的话,那么需要保存到I这个结点,应该也是使用prev记录前一个节点 I,Node n1记录M节点,使用prev.right=N来替换吧。

 

 

技术分享图片

 

 

这里说的是:如果不使用递归的方法,如何用一些prev的思想来删除最大节点,最小节点。

 

其中,删除最大节点,或者删除最小节点的话。技术分享图片

 

 这里想说的是:  最小节点,可以有右子树。直接拿右子树的根来替换当前结点就ok。

而如果删除普通的是:拿右子树的最小节点来替换它自己,记住,替换的是自己,不是右子树的根。

自己学会了:如何去删除最大节点、如何删除最小节点的思想。以及如何删除普通的某个节点的思想。

怎么看替换后的大小关系原来的大小关系是符合的呢?

 需删除位置上面肯定是满足的, 需删除位置的下面也是肯定满足的,那么只需要看  需删除的接口位置满足大小关系即可。

 

 技术分享图片

 

 删除最小元素的话,那么其实就是删除E节点,看大小关系是否符合的话,就是看H和D之间的关系是不是符合的。

那么H大于E 并且H肯定是小于D的,    那么是满足的

 

也就是自己也知道,如何去看移动后是不是满足原来的大小关系,看接口位置是不是满足大小关系即可。

并且也知道了如何删除最大元素、如何删除最小元素,如何删除某个元素的正确方法,以及我的想法的实现。

下一章将把这些实现都写了。

学习数据结构的第七天(二)

原文:https://www.cnblogs.com/startFrom0/p/12621304.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!