15数据结构tree_堆排序-创新互联
python内置数据结构——tree树
tree：
非线性结构，每个元素可以有多个前驱（前面）和后继（后面）；而线性结构中，前面有一个后面有一个；
树是n(n>=0)个元素的集合：
n=0时，称为空树；
树只有一个特殊的没有前驱的元素，称为树的root根；
树中除了根结点外，其余元素只能有一个前驱，可以有0个或多个后继；
递归定义：
树T是n(n>=0)个元素的集合，n=0时，称为空树；
有且只有一个特殊元素根，剩余元素都可被划分为m个互不相交的集合T1,T2,T3...Tn，而每一个集合都是树，称为T的子树SubTree，子树也有自己的根；
树的概念：
结点，树中的数据元素；
结点的degree度，结点拥有的子树的数目称为度，记作d(v)；
叶子结点，结点的度为0，称为叶子结点leaf、终端结点、末端结点；
分支结点，结点的度不为0，称为非终端结点或分支结点；
分支，结点之间的关系；
内部结点，除根结点外的分支结点，当然也不包括叶子结点，掐头去尾；
树的度是树内各结点的度的大值，D结点大为3，树的度数就是3；
child，孩子结点|儿子结点，结点的子树的根结点称为该结点的孩子，B是A的孩子结点；
parent，双亲结点|父结点，一个结点是它各子树的根结点的双亲，A是B的双亲结点；
sibling，兄弟结点，具有相同双亲结点的结点，B、C；
祖先结点，从根结点到该结点所经分支上所有的结点，A、B、D都是G的祖先结点，A、C、E是J的祖先结点；
子孙结点，结点的所有子树上的结点都称为该结点的子孙，B的子孙是D、G、H、I；
level，结点的层次，根节点为第一层，根的孩子为第二层，以此类推，记作L(v)，上图L(4)；
depth，树的深度|高度，树的层次的大值，上图树的深度为4；
堂兄弟，双亲在同一层的结点，D和E，D和F；
有序树，结点的子树是有顺序的（兄弟有大小，有先后次序），不能交换；（计算机要处理的数据都是有序的，所谓的随机是假随机）；
无序树，结点的子树是无序的，可以交换；
路径，树中的k个结点n1,n2...nk，满足ni是n(i+1)的双亲，称为n1到nk的一条路径，就是一条线串下来的，前一个都是后一个的双亲结点（父结点|前驱）；
路径长度=路径上结点数-1，也是分支树，上图路径长度为3；
森林，m(m>=)棵不相交的树的集合，对于结点而言，其子树的集合就是森林，A结点的2棵子树的集合就是森林；
树的特点：
唯一的根；
子树不相交；
除了根以外，每个元素只能有一个前驱，可以有0个或多个后继；
根结点没有双亲结点（前驱），叶子结点没有孩子结点（后继）；
vi是vj的双亲，则L(vi)=L(vj)-1，即双亲比孩子结点的层数少1；
堂兄弟的双亲是兄弟关系吗？不一定
二叉树：
每个结点最多2棵子树，二叉树不存在度数大于2的结点；
它是有序树，左子树、右子树是顺序的，不能交换次序；
即使某个结点只有一棵子树，也要确定它是在左子树还是右子树；
二叉树的五种基本形态：
空二叉树；
只有一个根结点；
根结点只有左子树；
根结点只有右子树；
根结点有左子树和右子树；
斜树：
左斜树，所有结点都只有左子树；
右斜树，所有结点都只有右子树；
满二叉树：
一棵二叉树的所有分支结点都存在左子树和右子树，并且所有叶子结点只存在最下面一层；
complete binary tree完全二叉树：
若二叉树的深度为k，二叉树的层数从1到k-1层的结点数都达到了大个数，在第k层的所有结点都集中在最左边，这就是完全二叉树；
完全二叉树由满二叉树引出；
满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树；
k为深度（1= 举例： 二叉树性质： 性质1： 在二叉树的第i层上至多有2**(i-1)个结点（i>=1），1,2,4,8,16； 性质2： 深度为k的二叉树，至多有(2**k)-1个结点（k>=1）； 一层2-1； 二层4-1=1+2=3； 三层8-1=1+2+4=7； 性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度数为2的结点为n2，则有n0=n2+1； 即，叶子结点数-1=度数为2的结点数； 证明： 总结点数为n=n0+n1+n2，n1为度数为1的结点总数； 一棵树的分支树为n-1，因为除了根结点外，其余结点都有一个分支，即n0+n1+n2-1； 分支树还等于n0*0+n1*1+n2*2，n2是2分支结点，所以乘以2，2*n2+n1； 可得2*n2+n1=n0+n1+n2-1==>n2=n0-1； 其它性质： 高度为k的二叉树，至少有k个结点（含有n(n>=1)的结点的二叉树高度至多为n）； 含有n(n>=1)的结点的二叉树的高度至多为n，最小为math.ceil(log2(n+1))，不小于对数值的最小整数向上取整； 假设高度为h，(2**h)-1=n，层次数是取整，如果是8个结果，3.1699要向上取整为4，为4层，h=log2(n+1)； 性质4： 具有n个结点的完全二叉树的深度为int(log2n)+1或math.ceil(log2(n+1))； 性质5： 如果有一棵n个结点的完全二叉树（深度为性质4），结点按照层序编号，i为结点编号； 如果i=1，则结点i是二叉树的根，无双亲； 如果i>1，则其双亲是int(i//2)，向下取整，子结点的编号整除2得到的就是父结点的编号；父结点如果是i，那么左孩子结点就是2i，右孩子结点就是2i+1； 如果2i>n，则结点i无左孩子，即结点i为叶子结点，否则其左孩子结点存在编号为2i； 如果2i+1>n，则结点i无右孩子，注意并不能说明结点i没有左孩子，否则右孩子结点存在编号为2i+1； 树的遍历： 二叉树的遍历： 遍历，迭代所有元素一遍； 树的遍历，对树中所有元素不重复的访问一遍，也称扫描； 广度优先遍历： 层序遍历，按树的层次，从第一层开始，自L左向R右遍历元素，如ABCDEFGHI； 深度优先遍历： 前序遍历，也叫先序遍历，也叫先根遍历，DLR，从根结点开始，先左子树后右子树，每个子树内部依然是先根结点，再左子树后右子树，递归遍历，如ABDGHCEIF； 中序遍历，也叫中根遍历，LDR，从根结点的械子树开始遍历，然后是根结点，再右子树，每个子树内部，先左子树，再根结点，再右子树，递归遍历，如GDHBAIECF，GDHBAEICF； 后序遍历，也叫后根遍历，LRD，先左子树，后右子树，再根结点，每个子树内部依然是先左子树，后右子树，再根结点，递归遍历，如GHDBIEFCA； 遍历序列： 将树中所有元素遍历一遍后，得到的元素的序列，将层次结构转换成了线性结构； heap sort，堆排序： heap堆，是一个完全二叉树； 完全二叉树的每个非叶子结点都要大于或等于其左右孩子结点的值，称为大顶堆； 完全二叉树的每个非叶子结点都要小于或等于其左右孩子结点的值，称为小顶堆； 根结点一定是大顶堆中的大值，一定是小顶堆中的最小值，即堆顶一定是一个极值（极大|极小）； 注： 不稳定，值相同的不同元素顺序是固定的； 1、构建完全二叉树： 待排序数字为3、2、8、4、5、1、6、7、9； 构建一个完全二叉树存放数据，并根据性质5对元素编号，放入顺序的数据结构中； 构造一个列表为[0,3,2,8,4,5,1,6,7,9]，列表的index与性质5中元素编号对应； 2、构建大顶堆： 核心算法是堆结点的调整； 度数为2的结点A，如果它的左右孩子结点的大值比它大的，将这个大值和该结点交换； 度数为1的结点A，如果它的左右孩子的值大于它，则交换； 如果结点A被交换到新的位置，还需要和其孩子结点重复上面的过程； 起点结点的选择： 从完全二叉树的最后一个结点的双亲结点开始，即最后一层的最右边叶子结点的父结点开始； 结点数为n，则起点结点的编号为n//2（性质5）； 下一个结点的选择： 从起始结点开始向左找其同层结点，到头后再从上一层的最右边结点开始继续向左逐个查找，直至根结点（编号为1，即索引为1）； 大顶堆的目标： 确保每个根结点的都比左右结点的值大； 排序： 将大顶堆根结点空上大值，和最后一个叶子结点交换，那么最后一个叶子结点就是大值，将这个叶子结点排队在待排序结点之外； 从根结点开始（新的根结点），重新调整为大顶堆后，重复上一步； 总结： 是复用堆性质的一种选择排序，在堆顶选出大值或最小值； 时间复杂度：O(nlogn）；由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏、平均时间复杂度均为O(logn；) 空间复杂度：只是使用了一个交换用的空间，空间复杂度O(1)； 稳定性：不稳定的排序算法； 打印出一个堆结构的完全二叉树？用于理解堆排序 思路：投影（光从顶照下来），网页编程中的栅格； 另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
标题名称：15数据结构tree_堆排序-创新互联
URL分享：http://scyanting.com/article/dsjepg.html
