linux数据结构-树形选择排序(treeselectionsort)详解及代码

《linux数据结构-树形选择排序(treeselectionsort)详解及代码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法逻辑:根据节点的大小，建立树，输出树的根节点，并把此重置为最大值，再重构树.因为树中保留了一些比较的逻辑，所以减少了比较次数.也称锦标赛排序，时间复杂度为O(nlogn),因为每个值(共n个)需要进行树的深度(logn)次比较.参考v数据结构〉(严蔚敏版)第278-279页.树形选择排序(treeselectionsort)是堆排序的一个过渡，并不是核心算法.但是完全按照书上算法，实现起來极其麻烦，几乎没有任何人实现过.需要记录建树的顺序，在重构时，才能减少比较.本着娱乐和分享的精神，应人之邀，简单的实现了一下.代码：/**TreeSelectionSo

2、rt.cpp**Createdon:2014.6.11*Author:Spike*//*eclipsecdt,gcc4.8.1*/#inelude#inelude#inelude#inelude#inelude#ineludeusingnamespacestd;/*树的结构*/structBinaryTreeNode{boolfrom;//判断来源,左true,右falseintValue;BinaryTreeNode*m_pLeft;BinaryTreeNo

3、de*m_pRight;};/*构建叶子节点*/BinaryTreeNode*buildList(conststd::vectorvint>&L)BinaryTreeNode*btnList=newBinaryTreeNode[L.size()];for(std::size_ti=0;i

4、点*/BinaryTreeNode*addMaxNode(BinaryTreeNode*list,intn){厂最大节点*/BinaryTreeNode*maxNode=newBinaryTreeNode();//最大节点，用于填充maxNode->from=true;maxNode->m_nValue=INT_MAX;maxNode->m_pLeft=NULL;maxNode->m_pRight=NULL;/*复制数组*/BinaryTreeNode*childNodes=newBinaryTreeNode[n+l];//增加一个节点for(inti=0;

5、ivn;++i){childNodes[i].from=list[i].from;childNodes[i].m_nValue=list[i].m_nValue;childNodes[i].m_pLeft=list[i].m_pLeft;childNodes[i].m_pRight=list[i].m_pRight;}childNodes[n]=*maxNode;delete[]list;list=NULL;returnchildNodes;}/*根据左右子树大小，创建树*/BinaryTreeNode*buildTree(BinaryTreeNode*ch

6、ildNodes,intn){if(n==1){returnchildNodes;if(n%2==1){childNodes=addMaxNode(childNodes,n);}intnum=n/2+n%2;BinaryTreeNode*btnList=newBinaryTreeNode[num];for(inti=0;im_nVal

7、ue<=btnList[i].m_pRight->m_nValue;btnList[i].from=less;btnList[i].m_nValue=less?btnList[i].m_pLeft->m_nValue:btnList[i].m_pRight->m_nValue;}buildTree(btnList?num);}厂返回树根，重新计算数*/intrebuildTree(BinaryTreeNode*tree){intresult=tree[O].m_nValue;std::stacknodes;BinaryTre

8、eNode*node=&tree[0];nodes.