二元查找树转换成一个排序的双向链表

绝地灬酷狼 2022-08-02 09:44 101阅读 0赞

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

最直观的一种思路就是每次从二分查找树中找到最小的数，加到链表中

</pre><pre name="code" class="cpp">// BST2list.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h" 
    #include<iostream> 
    using namespace std;
    #define INFINITY 1000000
    struct BiNOde
    {
    	int ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    int min;
    BiNOde*head, *tail;
    BiNOde*minnode;
    BiNOde*p;
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	root->ele = 45;
    	node1->ele = 38;
    	node2->ele = 55;
    	node3->ele = 33;
    	node4->ele = 43;
    	node5->ele = 19;
    	node6->ele = 16;
    	node7->ele = 52;
    	node8->ele = 58;
    	node9->ele = 50;
    	node10->ele = 41;
    	node11->ele = 35;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = node11;
    	node4->lnode = node10;
    	node4->rnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = NULL;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;  
    	//node12->ele = 12;  
    	//node12->lnode = NULL;  
    	//node12->rnode = NULL;  
    	//node6->lnode = node11;  
    	return root;
    }
    
    BiNOde*find_min(BiNOde*node)
    {
    	//minnode=node;这一句会使递归出错
    	if (node == NULL)
    		return NULL;
    	if (node->ele < min)
    	{
    		min = node->ele;
    		minnode = node;
    	}
    	if (node->lnode != NULL)
    	{
    		if (node->lnode->ele < min)
    		{
    			min = node->lnode->ele;
    			minnode = node->lnode;
    		}
    		find_min(node->lnode);
    	}
    	if (node->rnode != NULL)
    	{
    		if (node->rnode->ele < min)
    		{
    			min = node->rnode->ele;
    			minnode = node->rnode;
    		}
    
    		find_min(node->rnode);
    	}
    	return minnode;
    }
    
    void findparent(BiNOde*node, BiNOde*parent)
    {
    	if (parent == NULL)
    		return;
    	if (parent->lnode == node || parent->rnode == node)
    		{p = parent;return;}
    	findparent(node, parent->lnode);
    	findparent(node, parent->rnode);
    }
    
    
    BiNOde*BST2list(BiNOde*root)
    {
    	min = INFINITY;
    	minnode = NULL;
    	BiNOde*n = find_min(root);
    
    	while (n)
    	{
    		if (n == root)
    		{
    			if (n->rnode != NULL)
    				root = n->rnode;
    			else
    			{
    				tail->rnode = n;
    				n->lnode = tail;
    				tail = n;
    				return head;
    			}
    
    		}
    		else
    			if (n->rnode != NULL)
    			{
    			p = NULL;
    			findparent(n, root);
    			if (p != NULL)
    				p->lnode = n->rnode;
    			n->rnode = NULL;
    			}
    			else
    			{
    				p = NULL;
    				findparent(n, root);
    				if (p != NULL)
    					p->lnode = NULL;
    			}
    		if (head == NULL&&tail == NULL)
    		{
    			head = tail = n;
    
    		}
    		else if (head == tail)
    		{
    			tail->rnode = n;
    			n->lnode = tail;
    			tail = n;
    			head->rnode = tail;
    
    		}
    		else
    		{
    			tail->rnode = n;
    			n->lnode = tail;
    			tail = n;
    		}
    		min = INFINITY;
    		minnode = NULL;
    		n = find_min(root);
    	}
    
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
    	head = tail = NULL;
    	BiNOde*root = create_tree();
    	head = BST2list(root);
    
    
    	system("pause");
    	return 0;
    }

find\_min递归时minnode数据放的位置不对，造成开始递归失败。所以要特别注意以影响递归过程的变量的处理。