【数据结构】二叉搜索树——转换成有序双向链表

电玩女神 2022-06-01 09:25 202阅读 0赞

在上一篇博客中，我们对二叉搜索树已经有了简单的认识。下面我们看看怎样将二叉搜索树转换成有序的双向链表

在二叉搜索树中，左子树结点的值小于双亲结点的值，右子树结点的值大于双亲结点的值。在双向链表中，每个结点也有两个指针，分别指向前一个结点和后一个结点。因此我们可以通过改变指针指向将二叉搜索树转换成双向链表。

![SouthEast][]

![SouthEast 1][]

具体实现代码如下：

#pragma once
    #include <iostream>
    using namespace std;
    template <class K, class V>
    struct BSTreeNode
    {
    	BSTreeNode(const K& key, const V& value)
    	: _key(key)
    	, _value(value)
    	, _pLeft(NULL)
    	, _pRight(NULL)
    	, _pParent(NULL)
    	{}
    	BSTreeNode<K, V>* _pLeft;
    	BSTreeNode<K, V>* _pRight;
    	BSTreeNode<K, V>* _pParent;
    	K _key;
    	V _value;
    };
    
    template <class K, class V>
    class BSTree
    {
    	typedef BSTreeNode<K, V> Node;
    	typedef Node* pNode;
    public:
    	BSTree()
    		: _pRoot(NULL)
    	{}
    
    	bool Insert(const K& key, const V& value)//非递归插入
    	{
    		if (NULL == _pRoot)
    		{
    			_pRoot = new Node(key, value);
    			return true;
    		}
    		pNode pCur = _pRoot;
    		pNode pParent = NULL;
    		while (pCur)
    		{
    			pParent = pCur;
    			if (key < pCur->_key)
    				pCur = pCur->_pLeft;
    			else
    				pCur = pCur->_pRight;
    		}
    		pCur = new Node(key, value);
    		if (key < pParent->_key)
    			pParent->_pLeft = pCur;
    		else if (key > pParent->_key)
    			pParent->_pRight = pCur;
    		else
    			return false;
    		pCur->_pParent = pParent;
    		return true;
    	}
    
    	pNode BSTreeToList()
    	{
    		if (NULL == _pRoot)
    			return NULL;
    		pNode pHead = _pRoot;//定义链表的头结点
    		while (pHead->_pLeft)
    			pHead = pHead->_pLeft;
    		pNode prev = NULL;
    		_BSTreeToList(_pRoot, prev);
    		return pHead;
    	}
    private:
    	void _BSTreeToList(pNode pRoot, pNode& prev)
    	{
    		if (NULL == pRoot)
    			return;
    		_BSTreeToList(pRoot->_pLeft, prev);
    		pRoot->_pLeft = prev;
    		if (prev)
    			prev->_pRight = pRoot;
    		prev = pRoot;
    		_BSTreeToList(pRoot->_pRight, prev);
    	}
    private:
    	pNode _pRoot;
    };
    
    void Test()
    {
    	int arr[] = { 5, 3, 4, 1, 2, 0 };
    	BSTree<int, int> bt;
    	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    		bt.Insert(arr[i], arr[i]);
    	BSTreeNode<int, int>* pNode = bt.BSTreeToList();
    	BSTreeNode<int, int>* pCur = pNode;
    	while (pCur)//正向打印
    	{
    		cout << pCur->_key << " ";
    		pCur = pCur->_pRight;
    	}
    	cout << endl;
    	
    	pCur = pNode;//逆向打印
    	while (pCur->_pRight)
    		pCur = pCur->_pRight;
    	while (pCur)
    	{
    		cout << pCur->_key << " ";
    		pCur = pCur->_pLeft;
    	}
    }

测试结果：  
![SouthEast 2][]

[SouthEast]: /images/20220601/8bd6f4e069234644aee0000771ef4c15.png
[SouthEast 1]: /images/20220601/ffd053d720f241ec8699b9dcac9c4d33.png
[SouthEast 2]: /images/20220601/daeb6fa5ba6f45208d3767130e157f75.png