1. 把二元查找树转变成排序的双向链表（树）

 题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
   10
  / /
  6  14
 / / / /
4  8 12 16
 转换成双向链表

4=6=8=10=12=14=16。

实现如下：

#include<iostream>

using namespace std;


//定义二元查找树
struct BSTreeNode
{
	int m_nValue;
	BSTreeNode *left;
	BSTreeNode *right;
	BSTreeNode(int _value = 0):m_nValue(_value),left(NULL),right(NULL){}
	void add(BSTreeNode* _node)
	{
		if(_node->m_nValue > m_nValue)
		{
			if(right != NULL)
				right->add(_node);
			else
				right = _node;
		}
		else
		{
			if(left != NULL)
				left->add(_node);
			else
				left = _node;
		}
	}
};

//查找二元查找树的最右节点
BSTreeNode* findrightNode(BSTreeNode* BT)
{
	if(BT == NULL)
		return NULL;
	BSTreeNode* rBT = BT;
	while(rBT->right != NULL)
		rBT = rBT->right;
	return rBT;
}

//查找二元查找树的最左节点
BSTreeNode* findleftNode(BSTreeNode* BT)
{
	if(BT == NULL)
		return NULL;
	BSTreeNode* rBT = BT;
	while(rBT->left != NULL)
		rBT = rBT->left;
	return rBT;
}

//把二元查找树转成有序的双向链表
void BST_Blist(BSTreeNode* root)
{
	if(root == NULL)
		return;
	BSTreeNode* left = findrightNode(root->left);
	BSTreeNode* right = findleftNode(root->right);
	BST_Blist(root->left);
	BST_Blist(root->right);
	if(left == root)
		left = NULL;
	if(right == root)
		right = NULL;

	root->left = left;
	if(left != NULL)
		left->right = root;
	root->right = right;	
	if(right != NULL)
		right->left = root;
}

template <typename T> 
class Stack{
private:
	vector<T> vecdata;
public:
	void push(T& data)
	{
		vecdata.push_back(data);
	} 
	T& pop()
	{
		return vecdata.pop_back();
	}
};

int main()
{
	//构建二元查找树
	BSTreeNode *root = NULL;
	BSTreeNode node1(10);	
	BSTreeNode node2(6);	
	BSTreeNode node3(14);	
	BSTreeNode node4(4);	
	BSTreeNode node5(8);	
	BSTreeNode node6(12);	
	BSTreeNode node7(16);	
	root = &node1;
	root->add(&node2);
	root->add(&node3);
	root->add(&node4);
	root->add(&node5);
	root->add(&node6);
	root->add(&node7);

	//转化成排序的双向链表（树）
	BST_Blist(root);
	BSTreeNode *next = findleftNode(root);
	cout << "转化成排序的双向链表 结果为：" << endl;
	while(next != NULL)
	{
		if(next->right != NULL)
			cout << next->m_nValue << "==";
		else
			cout << next->m_nValue;
			
		
		next = next->right;
	}
}

输出结果为：

转化成排序的双向链表 结果为：
4==6==8==10==12==14==16

1. 把二元查找树转变成排序的双向链表（树）,布布扣,bubuko.com

1. 把二元查找树转变成排序的双向链表（树）

原文：http://blog.csdn.net/hhh3h/article/details/20483113