二叉搜索树 与 双向链表 代码(C++)

本文地址: http://blog.csdn.net/caroline_wendy

题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.

要求不能创建任何新的结点, 只能调整数中结点的指针的指向.

方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.

本程序包含算法原理, 测试程序, 及 输出.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct BinaryTreeNode {
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

void printTree (BinaryTreeNode* tree)
{
	BinaryTreeNode* node = tree;
	std::queue<BinaryTreeNode*> temp1;
	std::queue<BinaryTreeNode*> temp2;

	temp1.push(node);

	while (!temp1.empty())
	{
		node = temp1.front();
		if (node->m_pLeft != NULL) {
			temp2.push(node->m_pLeft);
		}

		if (node->m_pRight != NULL) {
			temp2.push(node->m_pRight);
		}

		temp1.pop();

		std::cout << node->m_nValue  << " ";

		if (temp1.empty())
		{
			std::cout << std::endl;
			temp1 = temp2;
			std::queue<BinaryTreeNode*> empty;
			std::swap(temp2, empty);
		}
	}
}

BinaryTreeNode* buildTree (const std::vector<int>& L)
{
	if (L.empty())
		return nullptr;

	std::queue<BinaryTreeNode*> parentQueue;
	std::queue<BinaryTreeNode*> childQueue;

	BinaryTreeNode* root = new BinaryTreeNode();
	root->m_nValue = http://www.mamicode.com/L[0];>


输出:
----Tree:----
10 
6 14 
4 8 12 16 
----List:----
4 6 8 10 12 14 16