欢迎来到天天文库
浏览记录
ID:43325057
大小:57.50 KB
页数:6页
时间:2019-09-29
《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;i4、点*/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*ch6、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_nVal7、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;BinaryTre8、eNode*node=&tree[0];nodes.
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.
此文档下载收益归作者所有