document.write('由于转换后的双向链表中结点的顺序与二叉树的中序遍历的顺序相同，因此，可以对二叉树的中序遍历算法
进行修改，通过在中序遍历的过程中修改结点的指向来转换成一个排序的双向链表。实现思路如下图所示：
假设当前遍历的结点为root，root的左子树已经被转换为双向链表(如下图(1)所示)，使用两个变量pHead与
pEnd分别指向链表的头结点与尾结点。那么在遍历root结点的时候，只需要将root结点的lchild(左)指向
pEnd，把pEnd的rchild(右)指向root；此时root结点就被加入到双向链表里了，因此，root变成了双向链表
的尾结点。对于所有的结点都可以通过同样的方法来修改结点的指向。因此，可以采用递归的方法来求解，
在求解的时候需要特别注意递归的结束条件以及边界情况(例如双向链表为空的时候)。
实现代码如下：
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
class Test:
def __init__(self):
self.pHead=None #双向链表头结点
self.pEnd=None #双向链表尾结点
#方法功能: 把有序数组转换为二叉树
def arraytotree(self,arr,start,end):
root=None
if end＞=start:
root=BiTNode()
mid=(start+end+1)/2
#树的根结点为数组中间的元素
root.data=arr[mid]
#递归的用左半部分数组构造root的左子树
root.lchild=self.arraytotree(arr,start,mid-1)
#递归的用右半部分数组构造root的右子树
root.rchild=self.arraytotree(arr, mid+1, end)
else:
root=None
return root
"""
方法功能: 把二叉树转换为双向列表
输入参数: root:二叉树根结点
"""
def inOrderBSTree(self,root):
if root==None:
return
#转换root的左子树
self.inOrderB STree (root.lchild)
root,lchild=self.pEnd #使当前结点的左孩子指向双向链表中最后一个结点
if None==self.pEnd: #双向列表为空,当前遍历的结点为双向链表的头结点
self.pHead=root
else: #使双向链表中最后一个结点的右孩子指向当前结点
self.pEnd.rchild=root
self.pEnd=root #将当前结点设为双向链表中最后一个结点
#转换root的右予树
self.inOrderBSTree(root.rchild)
if __name__=="__main__":
arr=[1,2,3,4,5,6,7]
test=Test()
root=test.arraytotree(arr,O,len(arr)-1)
test.inOrderBSTree(root)
print "转换后双向链表正向遍历:",
#cur=BiTNode()
cur=test.pHead
while cur!=None:
print cur.data,
cur=cur.rchild
print \'\\n\'
print"转换后双向链表逆向遍历:",
cur=test.pEnd
while cur!=None:
print cur.data,
cur=cur.lchild
程序的运行结果为：
转换后双向链表正向遍历：1 2 3 4 5 6 7
转换后双向链表逆向遍历：7 6 5 4 3 2 1
算法性能分析：
这种方法与二叉树的中序遍历有着相同的时间复杂度O(N)。此外，这种方法只用了两个额外的变量pHead
与pEnd来记录双向链表的首尾结点，因此，空间复杂度为O(1)。
');
![\"360截图20190815221211808.jpg\"](\"http://www.alatiku.com/d/file/shiti/4f8adb79e6550c5369f28f02734d9fa5.jpg\")