1、將二叉搜索樹轉換成一個排序的雙向鏈表。提示：要求不能創建任何新的結點，只能調整樹中結點指針的指向，也就是left當prev，right當next。--中序線索化的變型。?

Node* BSTreeToList() {if(_pRoot == NULL) return NULL; Node* pHead = _pRoot;//找到最左邊的結點，即轉換后鏈表的頭結點while(pHead->_pleft != NULL)pHead = pHead->_pleft; Node* prev = NULL; //進行轉換 _BSTreeToList(_pRoot, prev); return pHead; }void _BSTreeToList(Node*& pRoot, Node*& prev){if(pRoot){_BSTreeToList(pRoot->_pleft, prev);pRoot->_pleft = prev;//鏈表的左孩子指向上一個節點if(prev && prev->_pright == NULL)prev->_pright = pRoot;prev = pRoot;if(NULL != pRoot->_pright)_BSTreeToList(pRoot->_pright, prev);}}

完整代碼：

#include<iostream> #include<utility> using namespace std;template<class K, class V> struct BinarySearchTreeNode {BinarySearchTreeNode<K, V>*_pleft;BinarySearchTreeNode<K, V>*_pright;K _key;V _value;BinarySearchTreeNode(const K& key, const V& value):_pleft(NULL), _pright(NULL), _key(key),_value(value){} };template<class K, class V> class BinarySearchTree {typedef BinarySearchTreeNode<K, V> Node; public:BinarySearchTree():_pRoot(NULL){}BinarySearchTree(const BinarySearchTree<K, V>& tree):_pRoot(NULL){_pRoot = _CopyBSTree(tree._pRoot);}Node& operator=(Node& tree){if (this != &tree){BinarySearchTree<K, V> tmp(tree);swap(_pRoot, tmp._pRoot);}return *this;}~BinarySearchTree(){_Destory(_pRoot);} //插入（非遞歸）bool Insert(const K& key, const V& value){if (_pRoot == NULL){_pRoot = new Node(key, value);return true;}Node* pCur = _pRoot;Node* pParent = NULL;while (pCur){pParent = pCur;if (key < pCur->_key)pCur = pCur->_pleft;else if (key > pCur->_key)pCur = pCur->_pright;elsereturn false;}pCur = new Node(key, value);if (key < pParent->_key)pParent->_pleft = pCur;elsepParent->_pright = pCur;return true;}//插入（遞歸）bool Insert_R(const K& key, const V& value){return _Insert_R(_pRoot, key, value);}Node* Find(const K& key){if(NULL == _pRoot)return NULL;Node* pCur = _pRoot;while (pCur){if (key == pCur->_key)return pCur;if (key < pCur->_key)pCur = pCur->_pleft;elsepCur = pCur->_pright;}return NULL;}bool Remove(const K& key){Node* pCur = _pRoot;Node* pParent = NULL;while (pCur){if (key < pCur->_key){pParent = pCur;pCur = pCur->_pleft;}else if (key > pCur->_key){pParent = pCur;pCur = pCur->_pright;}elsebreak;}//跳出循環：pCur為空， 找到節點。//刪除節點pCur: 1、只有左子樹、左右子樹都沒有// 2、只有右子樹// 3、左右孩子都有。if(NULL == pCur)//空樹return false;if (pCur->_pright == NULL)//只有左子樹或左右子樹都沒有{if (pCur == _pRoot){_pRoot = pCur->_pleft;}else{if (pParent->_pleft == pCur)pParent->_pleft = pCur->_pleft;elsepParent->_pright = pCur->_pleft;}delete pCur;}else if (pParent->_pleft == NULL)//只有右子樹{if (pCur == _pRoot){_pRoot = pCur->_pright;}else{if (pParent->_pleft == pCur)pParent->_pleft = pCur->_pright;elsepParent->_pright = pCur->_pright;}delete pCur;}else//左右子樹都不為空:找右子樹最小節點（中序遍歷的第一個節點）把值互換，刪除找到的節點。{Node* firstInNode = pCur->_pright;pParent = pCur;while(firstInNode->_pleft){pParent = firstInNode;firstInNode = firstInNode->_pleft;}pCur->_key = firstInNode->_key;pCur->_value = firstInNode->_value;if(firstInNode == pCur->_pright)pParent->_pright = firstInNode->_pright;elsepParent->_pleft = firstInNode->_pright;delete firstInNode; }return true;}Node* BSTreeToList() {if(_pRoot == NULL) return NULL; Node* pHead = _pRoot;//找到最左邊的結點，即轉換后鏈表的頭結點while(pHead->_pleft != NULL)pHead = pHead->_pleft; Node* prev = NULL; //進行轉換 _BSTreeToList(_pRoot, prev); return pHead; }private:Node* _CopyBSTree(Node* pRoot){if (pRoot){Node* pNewRoot = new Node(pRoot->_key, pRoot->_value);pNewRoot->_pleft = _CopyBSTree(pRoot->_pleft);pNewRoot->_pright = _CopyBSTree(pRoot->_pright);return pNewRoot;}elsereturn NULL;}void _Insert_R(Node*& pRoot, const K& key, const V& value){if (_pRoot == NULL){_pRoot = new Node(key, value);return true;}if(key < pRoot->_key)return _Insert_R(pRoot->_pleft, key, value);else if(key > pRoot->_key)return _Insert_R(pRoot->_pright, key, value);elsereturn false;}void _Destory(Node* pRoot){if (_pRoot == NULL)return;_Destory(pRoot->_pleft);_Destory(pRoot->_pright);delete pRoot;}void _BSTreeToList(Node*& pRoot, Node*& prev){if(pRoot){_BSTreeToList(pRoot->_pleft, prev);pRoot->_pleft = prev;//鏈表的左孩子指向上一個節點if(prev && prev->_pright == NULL)prev->_pright = pRoot;prev = pRoot;if(NULL != pRoot->_pright)_BSTreeToList(pRoot->_pright, prev);}} private:BinarySearchTreeNode<K, V>* _pRoot; };int main() {int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };BinarySearchTree<int, int> t;t.Insert(5,5);t.Insert(3,3);t.Insert(4,4);t.Insert(1,1);t.Insert(7,7);t.Insert(8,8);t.Insert(2,2);t.Insert(6,6);t.Insert(0,0);t.Insert(9,9);BinarySearchTreeNode<int, int>* list = t.BSTreeToList(); system("pause");return 0; }

總結

以上是生活随笔為你收集整理的数据结构：将二叉搜索树转换成一个排序的双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。