当前位置:C++技术网 > 资讯 > 数据结构笔记分享:38 二叉搜索树转变成排序的双向链表

数据结构笔记分享:38 二叉搜索树转变成排序的双向链表

更新时间:2016-02-02 21:34:25浏览次数:1+次

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


////                 13

////          10          15

//// 5              11          17

////                        16          22

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



static void ConvertNodeToLink(BinNode root,ref DoubleLink link)
{
  if (root == null)
      return;
  BinNode temp = root;
  if (temp.Left != null)
      ConvertNodeToLink(temp.Left, ref link);
  //visit current node
  link.Next = new DoubleLink(link, null, root);
  link = link.Next;
  if (temp.Right != null)
      ConvertNodeToLink(temp.Right, ref link);
}


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


static DoubleLink ReverseDoubleLink(BinNoderoot, ref DoubleLink link)
{
   ConvertNodeToLink(root,ref link);
  DoubleLink temp = link;
  while (temp.Prev != null)
   {
      temp = temp.Prev;
   }
  return temp;
}


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

于是有算法2:来源于网络

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

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

代码如下所示:

link.Next= new DoubleLink(link, null, root);

link = link.Next;

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

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

link.Prev= new DoubleLink(null, link, root);

link = link.Prev;

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

算法代码如下所示:


static void ConvertNodeToLink2(BinNoderoot, ref DoubleLink link)
{
  if (root == null)
      return;
  BinNode temp = root;
  if (temp.Right != null)
      ConvertNodeToLink2(temp.Right, ref link);
  //visit current node
  link.Prev = new DoubleLink(null, link, root);
  link = link.Prev;
  if (temp.Left != null)
      ConvertNodeToLink2(temp.Left, ref link);
}