笔试day2

发表于

#堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def adjustDown(a,int i, int N):
	#找到i节点的子节点
	j = i * 2 +1
	while j < N:
		#找到两个子节点中最小的那个
		if j + 1 < N and a[j] > a[j+1]:
			j +=1
		#如果父节点是最小的了，说明符合条件，则不进行交换
		if a[i] < a[j]:
			break
		#父节点和最小的子节点进行交换
		swap(i,j)
		#继续判断交换后的子节点的子树情况
		i = j
		j = j * 2 +1
	
def makeHeap(a,N):
	#找到该数组中的最后一个非叶子节点
	i = N /2 -1
	#从这个叶子节点开始判断调整堆
	for j in range(i,0,-1):
		adjustDown(a,i,N)

def HeapSort(a):
	N = len(a)
	#开始建堆
	makeHeap(a,N)
	#每次取出堆顶点，与最后的节点交换，再重新调整堆
	for i in range(N-1,0,-1):
		swap(0,i)
		adjustDown(a,0,i)

#二叉树遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Node:  
    def __init__(self,value=None,left=None,right=None):  
         self.value=value  
         self.left=left    #左子树
         self.right=right  #右子树
         
def preTraverse(root):  
    '''
    前序遍历
    '''
    if root==None:  
        return  
    print(root.value)  
    preTraverse(root.left)  
    preTraverse(root.right)  

def midTraverse(root): 
    '''
    中序遍历
    '''
    if root==None:  
        return  
    midTraverse(root.left)  
    print(root.value)  
    midTraverse(root.right)  
  
def afterTraverse(root):  
    '''
    后序遍历
    '''
    if root==None:  
        return  
    afterTraverse(root.left)  
    afterTraverse(root.right)  
    print(root.value)

###已知二叉树的前序遍历和中序遍历，求这棵二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
preList = list('12473568')
midList = list('47215386')
afterList = []

def findTree(preList, midList, afterList):
    if len(preList) == 0:
        return
    if len(preList) == 1:
        afterList.append(preList[0])
        return
    root = preList[0]
    n = midList.index(root)
    findTree(preList[1:n + 1], midList[:n], afterList)
    findTree(preList[n + 1:], midList[n + 1:], afterList)
    afterList.append(root)