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=<k<=n），由结点总数最大值为（2**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(log₂n)+1或math.ceil(log₂(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)；

稳定性：不稳定的排序算法；

打印出一个堆结构的完全二叉树？用于理解堆排序

思路：投影（光从顶照下来），网页编程中的栅格；