Q27：二叉搜索树与双向链表

Q：输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。要求不能创建任何新的结点。

分析：二叉搜索树的中序遍历就是一个有序的序列，而树的左孩子指针和有孩子指针当然就充当了前驱和后继指针，所以这种转换是自然的。

我们定义结构体如下：

struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int v) : val(v),left(0),right(0){}
};

void InOrderVisit(TreeNode *root)
{
	if(!root) return;
	InOrderVisit(root->left);
	visit(root);
	InOrderVisit(root->right);
}

那么现在我们设计下我们程序的大体流程，以及需要哪些参数。

首先，我们要不停的修改双向链表，所以要有一个二级指针，或者是一级指针的引用，这里我们选择使用引用&。

接下来，在visit功能块里，我们把访问的结点挂到链表的表尾。

因为是双向的，所以即使我们只记录链表尾结点，通过循环向前寻找，我们是可以得到链表的表头的。

void TreeToLink(TreeNode *root,TreeNode *&linkTail)
{
	if(!root) return ;
        //handle its left_sub_tree
	TreeToLink(root->left,linkTail);

        //similar to visit()
        //handle the first node
        if(linkTail == NULL)
		linkTail = root;
	else
	{
		linkTail->right = root;
		root->left = linkTail;
	        linkTail = root;
	}
        //handle its right_sub_tree
	TreeToLink(root->right,linkTail);
}

总结：

这类的问题很多，但都有一个共性，就是他们都是三种递归遍历的变种，不同的是visit的处理，但都可以套用模板。

参考书里给出的解法也不错，但个人觉得有点麻烦，既然有模板，我们还是推荐套用模板，就像我们高考时的作文，自己熟练掌握几套模板总是很受用的，所谓万变不离其踪。

Q27：二叉搜索树与双向链表,布布扣,bubuko.com

Q27：二叉搜索树与双向链表

原文：http://blog.csdn.net/shiquxinkong/article/details/22932979