1 ‘‘‘  2 Created on 2016/12/26  3 Created by freeol.cn  4 一些排序算法的Python实现  5 @author: 拽拽绅士  6 ‘‘‘  7   8 import sys  9 from _ast import While 10 from celery.bin.celery import result 11  12 ‘‘‘顺序存储的二叉树实现‘‘‘ 13 class node1(object): 14     def __init__(self, S, L, R, V): 15         self.S = S#自 16         self.L = L#左子 17         self.R = R#右子 18         self.V = V#值 19 class tree1(object): 20     def createTree(self, a): 21         data =http://www.mamicode.com/ [] 22         for n in a: 23             data.append(node1(n[0], n[1], n[2], n[3])) 24         return data 25     def getTree(self, a): 26         return self.createTree(a) 27  28 ‘‘‘链式存储的二叉树‘‘‘ 29 class tree2(object): 30     def __init__(self): 31         self.L = None#Left node 32         self.R = None#Right node 33         self.V = None#value 34         self.tmp = {} 35     def createTree(self, key, tree): 36         if key in self.tmp: 37             tmpN = self.tmp[key] 38             tree.V = tmpN[3] 39             Lkey = tmpN[1] 40             Rkey = tmpN[2] 41             if Lkey != None: 42                 Ltree = tree2() 43                 Ltree = self.createTree(Lkey, Ltree) 44                 tree.L = Ltree 45             if Rkey != None: 46                 Rtree = tree2() 47                 Rtree = self.createTree(Rkey, Rtree) 48                 tree.R = Rtree 49         return tree 50     def getTree(self, a): 51         for n in a: 52             self.tmp[n[0]] = n#收集各节点信息 53         tree = tree2() 54         return self.createTree(‘1‘, tree) 55  56 ‘‘‘判断二叉树存储结构‘‘‘ 57 def checkTree1orTree2(tree): 58     if type(tree) == list: 59         return 1#顺序存储 60     else: 61         return 2#链式存储 62  63 ‘‘‘获取根节点‘‘‘ 64 def root(tree): 65     chk = checkTree1orTree2(tree) 66     if chk == 1:#顺序存储 67         childKeys = {} 68         for t in tree: 69             if t.L != None: 70                 childKeys[t.L] = None 71             if t.R != None: 72                 childKeys[t.R] = None 73         for t in tree: 74             if t.S not in childKeys: 75                 return t 76     else:#链式存储 77         return tree 78  79 ‘‘‘获取二叉树的度‘‘‘ 80 def degree(tree): 81     chk = checkTree1orTree2(tree) 82     if chk == 1:#顺序存储 83         return len(tree) 84     else:#链式存储 85         cnt = 1 86         if tree.L != None: 87             cnt += degree(tree.L) 88         if tree.R != None: 89             cnt += degree(tree.R) 90         return cnt 91  92 ‘‘‘深度‘‘‘ 93 def deepDegree(tree): 94     chk = checkTree1orTree2(tree) 95     if chk == 1:#顺序存储 96         cnt = 0 97         leafs = []#叶子集 98         branchs = []#枝干集 99         for t in tree:100             if t.L==None and t.R == None:101                 leafs.append(t)102             else:103                 branchs.append(t)104         save_cnt = 0105         for leaf in leafs:#回溯法 叶->枝->根106             cnt = 1107             key = leaf.S108             tmpBranchs = branchs.copy()109             i = 0110             while i < len(tmpBranchs):111                 branch = tmpBranchs[i]112                 if branch.L == key or branch.R == key:113                     cnt+=1114                     key = branch.S115                     i = 0116                 else:117                     i+=1118             if cnt > save_cnt:119                 save_cnt = cnt120         return save_cnt121     else:#链式存储122         cnt = 1123         Lcnt = 0124         Rcnt = 0125         if tree == None:126             return 0127         if tree.L != None:128             Lcnt = deepDegree(tree.L)129         if tree.R != None:130             Rcnt = deepDegree(tree.R)131         if Lcnt > Rcnt:132             cnt += Lcnt133         else:134             cnt += Rcnt135         return cnt136 137 ‘‘‘链式结构二叉树138 前序遍历：根节点->左子树->右子树‘‘‘139 def preorder(tree, m, result):140     if m == 1:#非递归实现(栈)141         static = []#栈142         t = tree143         ‘‘‘法1144         while t != None or static != []:145             while t != None:146                 result.append(t)147                 static.append(t)148                 t=t.L149             if static != []:150                 t = static.pop()151                 t = t.R152         ‘‘‘153         static.append(tree)154         while static:155             n = static.pop()156             result.append(n)157             if n.R:158                 static.append(n.R)159             if n.L:160                 static.append(n.L)161 162     else:#递归实现163         if tree == None:164             return result165         result.append(tree)166         result=preorder(tree.L, 2, result)167         result=preorder(tree.R, 2, result)168     return result169 170 ‘‘‘链式结构二叉树171 中序遍历：左子树->根节点->右子树‘‘‘172 def inorder(tree, m, result):173     if m == 1:#非递归实现(栈)174         static = []#栈175         t = tree176         ‘‘‘法1177         while t != None or static != []:178             while t != None:179                 static.append(t)180                 t=t.L181             if static != []:182                 t = static.pop()183                 result.append(t)184                 t = t.R185         ‘‘‘186         while t != None or static != []:187             while t != None:188                 static.append(t)189                 t = t.L190             t = static.pop()191             result.append(t)192             t = t.R193     else:#递归实现194         if tree == None:195             return result196         result=inorder(tree.L, 2, result)197         result.append(tree)198         result=inorder(tree.R, 2, result)199     return result200 201 ‘‘‘链式结构二叉树202 后序遍历：左子树->右子树->根节点‘‘‘203 def postorder(tree, m, result):204     if m == 1:#非递归实现(栈)205         static = []#栈206         t = tree207         mk = None208         while t != None or static != []:209             while t != None:210                 static.append(t)211                 t = t.L212             t = static.pop()213             if t.R == None or t.R == mk:214                 result.append(t)215                 mk = t216                 t = None217             else:218                 static.append(t)219                 t = t.R220     else:#递归实现221         if tree == None:222             return result223         result = postorder(tree.L, 2, result)224         result = postorder(tree.R, 2, result)225         result.append(tree)226     return result227 228 ‘‘‘order value print‘‘‘229 def resultPrintV(msg, rs):230     v=[]231     for t in rs:232         v.append(t.V)233     print(msg, v)234 235 236 ‘‘‘期望高度‘‘‘237 238 239 def main():240     ‘‘‘    1241           ∧242         2    3243        ∧    ∧244       4  5  9  7245     ∧   ∧246    8 6 10 11‘‘‘247     data = http://www.mamicode.com/[ #原始数据248             [‘1‘, ‘2‘, ‘3‘, 1],#Self key, Left key, Right key, Value249             [‘2‘, ‘4‘, ‘5‘, 2],250             [‘3‘, ‘9‘, ‘7‘, 3],251             [‘4‘, ‘8‘, ‘6‘, 4],252             [‘5‘, ‘10‘, ‘11‘, 5],253             [‘9‘, None, None, 9],254             [‘7‘, None, None, 7],255             [‘8‘, None, None, 8],256             [‘6‘, None, None, 6],257             [‘10‘, None, None, 10],258             [‘11‘, None, None, 11],259            ]260     print(‘原始数据大小‘, sys.getsizeof(data))261     print(‘预计二叉树根节点值‘, 1)262     print(‘预计二叉树的度‘, 11)263     print(‘预计二叉树的深度‘, 4)264     print(‘预计前序遍历值的结果‘, [1, 2, 4, 8, 6, 5, 10, 11, 3, 9, 7])265     print(‘预计中序遍历值的结果‘, [8, 4, 6, 2, 10, 5, 11, 1, 9, 3, 7])266     print(‘预计后序遍历值的结果‘, [8, 6, 4, 10, 11, 5, 2, 9, 7, 3, 1])267 268     print(‘========>创建顺序结构二叉树‘)269     t1 = tree1().getTree(data)#顺序结构270     print(‘顺序结构二叉树大小‘, sys.getsizeof(t1))271     root1 = root(t1)272     print(‘顺序结构二叉树根节点值‘, root1.V)273     print(‘顺序结构二叉树的度‘, degree(t1))274     print(‘顺序结构二叉树的深度‘, deepDegree(t1))275 276     print(‘========>创建链式结构二叉树‘)277     t2 = tree2().getTree(data)#链式结构278     print(‘链式结构二叉树大小‘, sys.getsizeof(t2))279     root2 = root(t2)280     print(‘链式结构二叉树根节点值‘, root2.V)281     print(‘链式结构二叉树的度‘, degree(t2))282     print(‘链式结构二叉树的深度‘, deepDegree(t2))283     rs = [];resultPrintV(‘链式结构 前序遍历值的结果->非递归实现‘, preorder(t2, 1, rs))284     rs = [];resultPrintV(‘链式结构 前序遍历值的结果->递归实现‘, preorder(t2, 2, rs))285     rs = [];resultPrintV(‘链式结构 中序遍历值的结果->非递归实现‘, inorder(t2, 1, rs))286     rs = [];resultPrintV(‘链式结构 中序遍历值的结果->递归实现‘, inorder(t2, 2, rs))287     rs = [];resultPrintV(‘链式结构 后序遍历值的结果->非递归实现‘, postorder(t2, 1, rs))288     rs = [];resultPrintV(‘链式结构 后序遍历值的结果->递归实现‘, postorder(t2, 2, rs))289 290 if __name__ == ‘__main__‘:291     main()