【1】二元查找树转变成排序的双向链表

题目：

二元查找树【百度百科】

它首先要是一棵二元树，在这基础上它或者是一棵空树；或者是具有下列性质的二元树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
   
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 
   
3. 左、右子树也分别为二元查找树

分析

根据二元查找树的特点可知：节点A的左子树的值都小于A，A的右子树的值都大于A。

1. 所以双向链表中，A的左边的值为左子树最右子树节点的值，而A的右边的值为右子树最左的子树节点的值，当然，这种分析不大适合直接写程序，效率不高。
2. 对于只有三个节点的二元查找树，很容易获取其排序后的顺序值：左节点<父节点<右节点。找到了上述的规律后，用递归的思想，情况就变得比较简单了，比如对于一个节点A，其左子树构成的顺序表为LA，右子树构成的顺序表为RA，那么A以及其子节点构成的顺序表则是：LA。
3. 最后一种方法可根据树的遍历方法来排序的，还记得树的三种遍历方式（先序，中序，后续）？观察二元查找树的特殊性，发现：其左节点<中节点<右节点，这个顺序不是和树的中序遍历方式一样？那么可以直接套用二叉树的中序遍历来实现的啊！

中序遍历实现二元查找树转换为双向链表源码

class BSTreeNode
{
public:
	int				_value;
	BSTreeNode*		_pLeftTree;
	BSTreeNode*		_pRightTree;
	bool			_bSorted;
	BSTreeNode(int value)
	{
		_value		= value;
		_pLeftTree	= NULL;
		_pRightTree	= NULL;
		_bSorted	= false;
	}
};
// 二叉树中序遍历
void BTreeMid(BSTreeNode* r)
{
	stack	s;
	BSTreeNode*			p = NULL;

	s.push(r);
	while(!s.empty())
	{
		p = s.top();
		if(p && p->_bSorted == false)
		{
			s.push(p->_pLeftTree);
		}
		else
		{
			s.pop();
			if(!s.empty())
			{
				p = s.top();
				printf("%d ", p->_value);
				p->_bSorted = true;
				s.pop();
				s.push(p->_pRightTree);
			}
		}
	}
}
// 二叉树中序遍历转双向链表
void BSTreeToDQ(BSTreeNode* r)
{
	stack	s;
	BSTreeNode*			p = NULL;
	BSTreeNode*			q = NULL;
	BSTreeNode*			pHead = NULL;

	s.push(r);
	while(!s.empty())
	{
		p = s.top();
		if(p && p->_bSorted == false)
		{
			s.push(p->_pLeftTree);
		}
		else
		{
			s.pop();
			if(!s.empty())
			{
				p = s.top();
				if(q)
				{
					p->_pLeftTree = q;
					q->_pRightTree = p;
				}
				else
				{
					pHead = p;
				}
				q = p;
				p->_bSorted = true;
				s.pop();
				s.push(p->_pRightTree);
			}
		}
	}
	q->_pRightTree = pHead;
	pHead->_pLeftTree = q;

	/*for (p=pHead; p!=pHead->_pLeftTree; p=p->_pRightTree)
	{
	printf("%d ", p->_value);
	}*/
}

运行结果