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

讀取二叉排序樹的操作為：

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

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

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

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

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

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

C++代碼實現(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;
}