程序员面试100题(算法)之把二叉查找树转变成排序的双向链表(含二叉树前序创建、递归)

// Test2.cpp : 定义控制台应用程序的入口点。
//程序员面试100题(算法)之把二叉查找树转变成排序的双向链表

#include "stdafx.h"
#include<iostream>
#include<vector>

using namespace std;

struct BSTreeNode
{
	BSTreeNode *leftNode;
	BSTreeNode *rightNode;
	int value;
};

BSTreeNode* createBiTree(BSTreeNode *&tNode)
{
	int value = 0;

	cin >> value;
	if(value == -1)
	{
		tNode = NULL;
	}
	else
	{
		tNode = (BSTreeNode*)malloc(sizeof(BSTreeNode));
		if(!tNode)
		{
			cout << "Out of space!" << endl;
			return NULL;
		}
		else
		{
			tNode->value = value;
			createBiTree(tNode->leftNode);
			createBiTree(tNode->rightNode);
		}
	}

	return tNode;
}

void convertBSTreeToLinklist(BSTreeNode *node, BSTreeNode *&tailOfLinklist)
{
	if(!node)
	{
		return;
	}

	BSTreeNode *currentNode = node;

	if(currentNode->leftNode)
	{
		convertBSTreeToLinklist(currentNode->leftNode, tailOfLinklist);
	}

	currentNode->leftNode = tailOfLinklist;

	if(tailOfLinklist)
		tailOfLinklist->rightNode = currentNode;

	tailOfLinklist = currentNode;

	if(currentNode->rightNode)
	{
		convertBSTreeToLinklist(currentNode->rightNode, tailOfLinklist);
	}
}

BSTreeNode *convertSolution(BSTreeNode *root)
{
	BSTreeNode *tailOfLinklist = NULL;

	convertBSTreeToLinklist(root, tailOfLinklist);

	while(tailOfLinklist->leftNode)
	{
		tailOfLinklist = tailOfLinklist->leftNode;
	}

	return tailOfLinklist;
}

void printLinklist(BSTreeNode *head)
{
	if(head)
	{
		while(head)
		{
			cout << head->value << "\t";
			head = head->rightNode;
		}

		cout << endl;
	}
	else
	{
		cout << "The double link list is empty" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	BSTreeNode* bTree = NULL;
	BSTreeNode* headOfLinklist = NULL;

	cout << "Create the BSTree with preorder:" <<endl;
	cout << "Please enter the integer, -1 means node is empty." <<endl;
	bTree = createBiTree(bTree);
	cout << "Starting convert the BSTree to double link list" <<endl;
	headOfLinklist = convertSolution(bTree);
	cout << "Print the double link list" <<endl;
	printLinklist(headOfLinklist);

	return 0;
}