例如我们把这样的二叉搜索树
//// 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);
}