数据结构笔记分享——二叉搜索树转变成排序

数据结构笔记分享——二叉搜索树转变成排序

二叉搜索树的中序遍历就是按照大小排序的，简答说BST的中序遍历就是一个从小到大的访问顺序，利用这一点很方便的简单这个问题。文章来源：C++技术原创文章版权所有，未经授权，禁止转载。

例如我们把这样的二叉搜索树

////13

////

////

////

转变为Link：5=10=11=13=15=16=17=22

staticvoidConvertNodeToLink(BinNoderoot,refDoubleLinklink){if(root==null)return;BinNodetemp=root;if(ft!=null)ConvertNodeToLink(ft,reflink);//xt=newDoubleLink(link,null,root);link=xt;if(ght!=null)ConvertNodeToLink(ght,reflink);}

但是我们发现，这样得到的Link是指向双链表最后一个元素22，而我们想要得到的是表头5，为此，我们不得不额外进行while循环，将指针向前移动到表头：

staticDoubleLinkReverseDoubleLink(BinNoderoot,refDoubleLinklink){ConvertNodeToLink(root,reflink);DoubleLinktemp=link;while(ev!=null){temp=ev;}returntemp;}

这么写有点蠢，为什么不直接在递归中就把顺序反转呢？

于是有算法2：来源于络

算法2：观察算法1的递归方法，访问顺序是Left-Root–Right，所以我们要把访问顺序修改为Right-Root–Left。

此外，算法的节点访问逻辑，是连接当前节点和新节点，同时指针link向前走，即5=10=11=13=15=16=17=22=link

代码如下所示：

xt=newDoubleLink(link,null,root);

link=xt;

那么，即使我们颠倒了访问顺序，新的Link也只是变为：22=17=16=15=13=11=10=5=link。

为此，我们修改上面的节点访问逻辑——将Next和Prev属性交换：

ev=newDoubleLink(null,link,root);

link=ev;

这样，新的Link就变成这样的顺序了：link=5=10=11=13=15=16=17=22

算法代码如下所示：

staticvoidConvertNodeToLink2(BinNoderoot,refDoubleLinklink){if(root==null)return;BinNodetemp=root;if(ght!=null)ConvertNodeToLink2(ght,reflink);//ev=newDoubleLink(null,link,root);link=ev;if(ft!=null)ConvertNodeToLink2(ft,reflink);}

文章来源：C++技术原创文章版权所有，未经授权，禁止转载。

转载请注明：http://www.92nongye.com/tlfc/204612488.html