二元查找树转化成排序的双向链表

[java]代码库

#include
 <iostream>
  using 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");}
 </iostream>//源代码片段来自云代码http://yuncode.net