学步园

#include <iostream>
using namespace std;
/**
* 递归实现将二叉排序树BST转换成排序的双向链表。
* 递归左子树，将左子树的转换成的链表的尾节点和当前根节点连接，
* 然后当前根节点更新尾转换好链表的尾节点。 递归右子树
*/
typedef struct node{
	int value;
	struct node *lchild;
	struct node *rchild;
}NODE;

NODE *createNode(int v){
	NODE *p = (NODE *)malloc(sizeof(NODE));
	p->value = v;
	p->lchild = NULL;
	p->rchild = NULL;
	return p;
}

//创建一棵树作为测试
NODE *buildTree(){
	NODE *root,*p,*q;
	root = createNode(8);	
	p = createNode(4);
	root->lchild = p;	
	q = createNode(3);
	p->lchild = q;
	q = createNode(6);
	p->rchild = q;
	p = q;
	q = createNode(5);
	p->lchild = q;
	p = createNode(10);
	root->rchild = p;	
	q = createNode(9);
	p->lchild = q;
	q = createNode(12);
	p->rchild = q;
	return root;
}

/**
* 将BST递归转换成双向排序链表，随时维护已转换好的链表的尾节点
*/
void transformToList(NODE *root, NODE **listLastNode){
	//空节点，不进行任何转换
	if(root == NULL) return;

	//如果左子树不空，递归左子树
	if(root->lchild != NULL){
		transformToList(root->lchild, listLastNode);
	}

	//将自己和左子树转换成的链表的最后一个节点相互连接
	if(*listLastNode != NULL) (*listLastNode)->rchild = root;
	root->lchild = *listLastNode;

	//把当前节点作为转换好的链表的尾节点，递归处理右子树
	//右子树递归到最左孩子的时候，会和listLastNode相互连接的
	*listLastNode = root;
	if(root->rchild != NULL){
		transformToList(root->rchild, listLastNode);
	}
}

int main(){
	NODE *listLastNode = NULL;
	NODE *root = buildTree();
	
	//转换
	transformToList(root, &listLastNode);
	
	//逆序输出
	while(listLastNode != NULL){
		cout<<listLastNode->value<<" ";
		listLastNode = listLastNode->lchild;
	}
	cout<<endl;
	return 0;
}