二叉查找树转换成排序的双向链表

左手的ㄟ右手 2022-08-08 00:56 150阅读 0赞

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何  
新的结点，只调整指针的指向。  
比如将二元查找树  
10  
/ \\  
6 14  
/ \\ / \\  
4 8 12 16  
转换成双向链表

4=6=8=10=12=14=16。

思路：对于树的很多题目，都可以使用递归的方法来处理。这道题目也不例外。我们从最基本的思路来考虑这个题目。

把一个二叉树编程双向链表，最终是一个有序的序列，也就是中序遍历之后的结果，那么当我们采用中序遍历的方式遍历二叉树时，遍历到某个节点，是的前序节点的右指针指向当前节点，然后当前节点的左指针指向前序节点，然后使得前序节点指向当前节点。

BinTree* head =NULL;
    void helper(BinTree* root,BinTree*& pre)
    {
    	if(root == NULL && root == NULL)
    		return ;
    		
    	helper(root->left,pre);
    	if(head == NULL)
    		head = root;
    	if(pre == NULL)
    		pre = root;
    	else
    	{
    		root->left = pre;
    		pre->right = root;
    		pre = root;
    	}
    	//cout<<root->value<<"  "<<endl;
    	helper(root->right,pre);
    }
    BinTree* SearchTreeConverstToList(BinTree* root)
    {
    	BinTree* pre = NULL;
    	helper(root,pre);
    	return head;
    }

思路二：如果对于当前节点，我们把右子树转换成双向链表，然后把左子树转换成双向链表，转换的时候我们都标记了链表的头节点和尾节点，那么我们只需要将当前节点和左子树的尾部相连，和右子树的头部相连即可。

void helper_second(BinTree* root,BinTree*& head,BinTree*& tail)
    {
    	if(root==NULL || (root->left == NULL && root->right == NULL))
    	{
    		head = root;
    		tail = root;
    		return;
    	}
    	BinTree* left_head = NULL;
    	BinTree* left_tail = NULL;
    	BinTree* right_head = NULL;
    	BinTree* right_tail = NULL;
    	
    	helper_second(root->left,left_head,left_tail);
    	helper_second(root->right,right_head,right_tail);
    
    	if(left_head == NULL)
    		head = root;
    	else
    	{
    		head = left_head;
    		left_tail->right = root;
    		root->right = left_tail;
    	}		
    	if(right_head == NULL)
    		tail = root;
    	else
    	{
    		tail = right_tail;
    		root->right = right_head;
    		right_head->left = root;
    	}
    }
    
    BinTree* ConverstToList(BinTree* root)
    {
    	BinTree* head=NULL;
    	BinTree* tail = NULL;
    	helper_second(root,head,tail);
    	return head;
    }