排序算法：二叉排序树

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

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

1，如果节点非空：

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

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

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

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

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

C++代码实现

#include <iostream> #include <vector> using namespace std; template<typename T> void BinaryTreeSort(vector<T> &vec); int main() { int att[] = { 10, 4, 23, 46, 20, 5, 3, 88, 8, 44, 53, 25, 86, 32, 16, 11 }; vector<int> vec(&att[0], &att[sizeof(att) / sizeof(int)]); BinaryTreeSort(vec); return 0; } template<typename T> void BinaryTreeSort(vector<T> &vec) { int VSize = vec.size(); if (VSize <= 1) return; typedef struct _SortNode { T data; struct _SortNode *father; struct _SortNode *left; struct _SortNode *right; }SortNode; SortNode *headNode = new SortNode(); headNode->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; }