码完第一次编译执行竟然就成功了。。。高兴~
问题描写叙述：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建不论什么新的结点，仅仅调整指针的指向。比如：
10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16
算法：
假设没有“不能创建不论什么新的结点”的限制，仅仅需进行一次中序遍历，对每一个节点的data值构造一个新节点就可以。
因为条件限制，如今我们仅仅能用现有的节点，调整他们的指针指向，把查找树转化为双向链表。算法完毕后，原来的查找树也不存在了。
与中序遍历相似，我们採用递归：将节点t的左右子树转化为的链表链接到t的左右两边。
值得注意的是，t的左右子树的链表返回值是不同的，t->left应返回链表的尾节点（最大的），t->right应返回链表的头节点（最小的），这就须要我们设置一个单数flag来区分眼下所处理的节点是一个左孩子还是右孩子。
代码实现：
#includeusing namespace std;//节点结构体struct BSTreeNode{ int data; BSTreeNode* left; BSTreeNode* right;};//父节点的左右子树的返回指针一头一尾，由flag来区分BSTreeNode* Transform(BSTreeNode* t,int flag){ if (t->left)//转左子树 { t->left = Transform(t->left, 0); t->left->right = t; } if (t->right)//转右子树 { t->right = Transform(t->right, 1); t->right->left = t; } if (flag == 0)//这是父节点的左子树，返回最右节点 { while (t->right) t = t->right; return t; } if (flag == 1)//这是父节点的右子树，返回最左节点 { while (t->left) t = t->left; return t; }}void main(){ BSTreeNode* n4 = new BSTreeNode; BSTreeNode* n6 = new BSTreeNode; BSTreeNode* n8 = new BSTreeNode; BSTreeNode* n10 = new BSTreeNode; BSTreeNode* n12 = new BSTreeNode; BSTreeNode* n14 = new BSTreeNode; BSTreeNode* n16 = new BSTreeNode; //构造二叉树 n4->data = 4; n4->left = n4->right = NULL; n8->data = 8; n8->left = n8->right = NULL; n12->data = 12; n12->left = n12->right = NULL; n16->data = 16; n16->left = n16->right = NULL; n6->data = 6; n6->left = n4; n6->right = n8; n14->data = 14; n14->left = n12; n14->right = n16; n10->data = 10; n10->left = n6; n10->right = n14; BSTreeNode* head=Transform(n10,1);//返回最左节点 while (head->right)//向右输出检验 { cout << head->data << ' ' ; head = head->right; } cout << head->data;//最右节点的data cout << endl; while (head->left)//向左输出检验 { cout << head->data << ' '; head = head->left; } cout << head->data;//最左节点的data cout << endl; system("pause");}
输出：
4 6 8 10 12 14 16
16 14 12 10 8 6 4