什么是二叉树排序
扫描二维码
随时随地手机看文章
1、二叉树排序
--1)一个无序整数数组
--2)创建二叉树,数组第一个元素为根结点,数组中下一个元素小于根的值放左边,大于的放右边。
--3)中序遍历,结果即为数组从小到大的排序。
当n较大时,用快速排序、堆排序或归并排序。
当待排序的关键字是随机分布时,快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。
堆排序和快速排序都是不稳定的。
若要求排序稳定,可选用归并排序。但从单个记录起进行两两归并的排序算法并不值得提倡。通常可以将它和直接插入排序结合在一起使用。
稳定排序:直接插入排序、冒泡排序、归并排序
不稳定:堆排序、快速排序、希尔排序、选择排序
2、代码实现
#includeusing namespace std; #define dim(x) (sizeof(x)/sizeof(x[0])) void swap(int *x,int *y) { int t = *x; *x = *y; *y = t; } //定义二叉树结构体 struct NODE { int iData; NODE *pLChild; NODE *pRChild; }; //中序遍历 void InOrder(NODE *node) { if(node == NULL) return; InOrder(node->pLChild); printf("%d ",node->iData); InOrder(node->pRChild); } //创建二叉树 NODE * TreeSort(const int sz[],const int nLen) { //先创建好所有结点 NODE *tree = new NODE[nLen]; for(int i=0;i<nLen;i++) { tree[i].iData = sz[i]; tree[i].pLChild = NULL; tree[i].pRChild = NULL; } //根据规则,建立结点间的关系 NODE *pRoot = &tree[0]; //根结点选择数组第一个元素 for(int i=1;i<nLen;i++) { NODE *pCur = pRoot; bool bGo = true; //控制跳出循环的 while(bGo) { //判断新加入的结点是不是比当前节点小 while(tree[i].iData iData) { if(pCur->pLChild == NULL) { pCur->pLChild = &tree[i]; bGo = false; break; } pCur = pCur->pLChild; } //判断新加入的结点是不是比当前节点大 while(tree[i].iData > pCur->iData) { if(pCur->pRChild == NULL) { pCur->pRChild = &tree[i]; bGo = false; break; } pCur = pCur->pRChild; } } } return pRoot; } void main() { int a[] = {49,38,65,97,76,13,27}; NODE *pRoot = TreeSort(a,dim(a)); InOrder(pRoot); printf("n"); delete pRoot; system("pause"); }
输出: