企业做网站平台的好处,网站建设公司的电话,wordpress的轮播图,学院网站建设自评1、将二叉搜索树转换成一个排序的双向链表。提示#xff1a;要求不能创建任何新的结点#xff0c;只能调整树中结点指针的指向#xff0c;也就是left当prev#xff0c;right当next。--中序线索化的变型。 Node* BSTreeToList() {if(_pRoot NULL) return NULL; Node* p…1、将二叉搜索树转换成一个排序的双向链表。提示要求不能创建任何新的结点只能调整树中结点指针的指向也就是left当prevright当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);}}完整代码 #includeiostream
#includeutility
using namespace std;templateclass K, class V
struct BinarySearchTreeNode
{BinarySearchTreeNodeK, V*_pleft;BinarySearchTreeNodeK, V*_pright;K _key;V _value;BinarySearchTreeNode(const K key, const V value):_pleft(NULL), _pright(NULL), _key(key),_value(value){}
};templateclass K, class V
class BinarySearchTree
{typedef BinarySearchTreeNodeK, V Node;
public:BinarySearchTree():_pRoot(NULL){}BinarySearchTree(const BinarySearchTreeK, V tree):_pRoot(NULL){_pRoot _CopyBSTree(tree._pRoot);}Node operator(Node tree){if (this ! tree){BinarySearchTreeK, 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:BinarySearchTreeNodeK, V* _pRoot;
};int main()
{int a[] { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };BinarySearchTreeint, 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);BinarySearchTreeNodeint, int* list t.BSTreeToList(); system(pause);return 0;
}
