C++中的排序算法：二叉排序树

二叉排序树的基本思想是将序列中的数读入一个二叉树，在读入时遵循一定的规则：比如，如果二叉树的一个节点有左子节点，那么左子节点一定比父节点的值小；如果一个节点有右子节点，那么右子节点一定比父节点的值大。在二叉排序树制造完成后，通过采用中序遍历的方法读取二叉树节点的值到序列中，就可以得到一个升序序列。

读取二叉排序树的操作为：

1，如果节点非空：

1.1，如果节点的左子节点非空，将左子节点设为操作节点，返回1；

1.2，如果节点左子节点为空，取节点数据到序列中；

1.2.1，如果节点右子节点非空，并且节点的父节点非空，令当前节点的右子节点为父节点的子节点；如果父节点为空，令右子节点为操作节点；

1.2.2，如果右子节点为空，并且父节点非空，令父节点的左子节点为空，令父节点为操作节点，释放当前节点；,

2，如果节点为空，输出序列。

C++代码实现

#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;
}