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

刀豆文库小编猜你可能喜欢“排序树变成双向链表”。

二元查找树转换成一个排序的双向链表(（精选3篇））由网友“五月”投稿提供，下面是小编给大家带来二元查找树转换成一个排序的双向链表，一起来阅读吧，希望对您有所帮助。

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

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

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

// BST2list.cpp : 定义控制台应用程序的入口点。//#include stdafx.h #includeusing namespace std;#define INFINITY 1000000struct 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; 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数据放的位置不对，造成开始递归失败，

所以要特别注意以影响递归过程的变量的处理。

篇2：[剑指Offer]二叉搜索树与双向链表

#includeusing std::cout;using std::cin;using std::endl;struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};class Solution {public: TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* p = pRootOfTree; TreeNode* pl; TreeNode* pr; if( p != NULL ) { pl = Convert(p->left); pr = Convert(p->right); p->right= pr; if(pr){ pr->left = p; } while(pl&&pl->right){ pl = pl->right; } if(pl) pl->right= p; p->left= pl; while(p->left){ p = p->left; } } return p; }};int main(){ TreeNode* p1 = new TreeNode(1); TreeNode* p2 = new TreeNode(2); TreeNode* p3 = new TreeNode(3); TreeNode* p4 = new TreeNode(4); TreeNode* p5 = new TreeNode(5); TreeNode* p6 = new TreeNode(6); TreeNode* p7 = new TreeNode(7); p4->left = p2; p4->right= p6; p2->left = p1; p2->right= p3; p6->left= p5; p6->right= p7; Solution s; TreeNode* p = s.Convert(p4); while(p->right){cout<

val<< ;p = p->right; } cout<

val<< ; cout<<; while(p->left){cout<

val<< ;p = p->left; } cout<

val<< ;}

篇3：[剑指Offer]二叉搜索树与双向链表

使用递归，分别去将当前节点的左右子树变成双向链表，然后获取左边链表的最后一个元素，当前元素的左指针指向它，它的右指针指向当前元素；右边链表的第一个元素，它的左指针指向当前元素，当前元素的右指针指向它；然后从当前元素开始，不断从左边找，找到第一个元素，返回此元素的指针。

总结：

对这种涉及到二叉树的题目，可以使用测试驱动开始，先写测试用例，然后再编码。