二叉排序樹(shù)的基本思想是將序列中的數(shù)讀入一個(gè)二叉樹(shù)，在讀入時(shí)遵循一定的規(guī)則：比如，如果二叉樹(shù)的一個(gè)節(jié)點(diǎn)有左子節(jié)點(diǎn)，那么左子節(jié)點(diǎn)一定比父節(jié)點(diǎn)的值??；如果一個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn)，那么右子節(jié)點(diǎn)一定比父節(jié)點(diǎn)的值大。在二叉排序樹(shù)制造完成后，通過(guò)采用中序遍歷的方法讀取二叉樹(shù)節(jié)點(diǎn)的值到序列中，就可以得到一個(gè)升序序列。

讀取二叉排序樹(shù)的操作為：

1，如果節(jié)點(diǎn)非空：

1.1，如果節(jié)點(diǎn)的左子節(jié)點(diǎn)非空，將左子節(jié)點(diǎn)設(shè)為操作節(jié)點(diǎn)，返回1；

1.2，如果節(jié)點(diǎn)左子節(jié)點(diǎn)為空，取節(jié)點(diǎn)數(shù)據(jù)到序列中；

1.2.1，如果節(jié)點(diǎn)右子節(jié)點(diǎn)非空，并且節(jié)點(diǎn)的父節(jié)點(diǎn)非空，令當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)為父節(jié)點(diǎn)的子節(jié)點(diǎn)；如果父節(jié)點(diǎn)為空，令右子節(jié)點(diǎn)為操作節(jié)點(diǎn)；

1.2.2，如果右子節(jié)點(diǎn)為空，并且父節(jié)點(diǎn)非空，令父節(jié)點(diǎn)的左子節(jié)點(diǎn)為空，令父節(jié)點(diǎn)為操作節(jié)點(diǎn)，釋放當(dāng)前節(jié)點(diǎn)；,

2，如果節(jié)點(diǎn)為空，輸出序列。

C++代碼實(shí)現(xiàn)

#include#includeusing?namespace?std;

templatevoid?BinaryTreeSort(vector&vec);

int?main()
{
	int?att[]?=?{?10,?4,?23,?46,?20,?5,?3,?88,?8,?44,?53,?25,?86,?32,?16,?11?};
	vectorvec(&att[0],?&att[sizeof(att)?/?sizeof(int)]);

	BinaryTreeSort(vec);

	return?0;
}

templatevoid?BinaryTreeSort(vector&vec)
{

	int?VSize?=?vec.size();
	if?(VSize?data?=?vec[0];
	headNode->father?=?NULL;
	headNode->left?=?NULL;
	headNode->right?=?NULL;

	for?(int?vIdx?=?1;?vIdx?<?VSize;?vIdx++)
	{
		SortNode?*locNode?=?new?SortNode();
		locNode->data?=?vec[vIdx];
		locNode->father?=?NULL;
		locNode->left?=?NULL;
		locNode->right?=?NULL;

		SortNode?*tmpNode?=?headNode;

		while?(NULL?!=?tmpNode)
		{
			if?(locNode->data?<?tmpNode->data)
			{
				if?(NULL?==?tmpNode->left)
				{
					locNode->father?=?tmpNode;
					tmpNode->left?=?locNode;
					tmpNode?=?NULL;
				}
				else
				{
					tmpNode?=?tmpNode->left;
				}
			}
			else
			{
				if?(NULL?==?tmpNode->right)
				{
					locNode->father?=?tmpNode;
					tmpNode->right?=?locNode;
					tmpNode?=?NULL;
				}
				else
				{
					tmpNode?=?tmpNode->right;
				}
			}
		}
	}

	SortNode?*tmpNode?=?headNode;
	int?vIdx?=?0;
	while?(NULL?!=?tmpNode)
	{
		if?(NULL?==?tmpNode->left)
		{
			vec[vIdx++]?=?tmpNode->data;???//?if?left?child?is?null,?get?this?node?data
			if?(NULL?!=?tmpNode->right)????//?if?right?child?is?not?null,?set?right?child?as?father's?child
			{
				if?(NULL?!=?tmpNode->father)
				{
					if?(tmpNode?==?tmpNode->father->left)
						tmpNode->father->left?=?tmpNode->right;
					else?if?(tmpNode?==?tmpNode->father->right)
						tmpNode->father->right?=?tmpNode->right;
				}


				tmpNode->right->father?=?tmpNode->father;

				SortNode?*childNode?=?tmpNode->right;
				delete?tmpNode;
				tmpNode?=?childNode;
			}
			else
			{
				SortNode?*FartherNode?=?tmpNode->father;
				if?(NULL?!=?FartherNode)
					FartherNode->left?=?NULL;

				tmpNode->father?=?NULL;

				delete?tmpNode;
				tmpNode?=?FartherNode;
			}
		}
		else
		{
			tmpNode?=?tmpNode->left;
		}
	}

	vIdx?=?0;
	for?(;?vIdx?<?VSize;?vIdx++)
	{
		cout?<<?"index?"?<<?vIdx?<<?"?value?=?"?<<?vec[vIdx]?<<?endl;
	}


	return;
}