tree1 = {
1: [2, 3],
2: [4, 5],
3: [6, None],
4: [None,None],
5: [None, None],
6: [None, None]
}
def leaves(tree,node):
if node is not None:
left_child, right_child = tree[node]
if left_child is None and right_child is None:
print(node, end = ' ')
leaves(tree,left_child)
leaves(tree,right_child)
leaves(tree1,1)
tree1 = {
1: [2, 3],
2: [4, 5],
3: [6, None],
4: [None, None],
5: [None, None],
6: [None, None]
}
def tree_height(tree,node):
if node is None:
return 0
else:
left_height = tree_height(tree,tree[node][0])
right_hight = tree_height(tree,tree[node][1])
return max(left_height, right_hight)+1
print(tree_height(tree1,1))
#建二元樹
def inorder_traversal(tree, node):
if node:
# 先遞歸遍歷左子樹
inorder_traversal(tree, tree[node][0])
# 訪問根節點
print(node, end=' ')
# 遞歸遍歷右子樹
inorder_traversal(tree, tree[node][1])
def preorder_traversal(tree, node):
if node:
# 訪問根節點
print(node, end=' ')
# 先遞歸遍歷左子樹
preorder_traversal(tree, tree[node][0])
# 遞歸遍歷右子樹
preorder_traversal(tree, tree[node][1])
def postorder_traversal(tree, node):
if node:
# 先遞歸遍歷左子樹
preorder_traversal(tree, tree[node][0])
# 遞歸遍歷右子樹
preorder_traversal(tree, tree[node][1])
# 訪問根節點
print(node, end=' ')
# 以剛才建立的二元樹為例
binary_tree = {
1: [2, 3],
2: [4, 5],
3: [6, None],
4: [None, None],
5: [None, None],
6: [None, None]
}
print("Inorder Traversal:")
inorder_traversal(binary_tree, 1)
print("\npreorder Traversal:")
preorder_traversal(binary_tree, 1)
print("\npostorder Traversal:")
postorder_traversal(binary_tree, 1)
# 執行結果
Inorder Traversal:
4 2 5 1 6 3
preorder Traversal:
1 2 4 5 3 6
postorder Traversal:
2 4 5 3 6 1
tree = {
1: [2, 3],
2: [4, 5],
3: [6],
4: [],
5: [],
6: []
}
# 遍歷樹狀結構（深度優先搜尋）
def dfs_traversal(tree, visited,node):
if node not in visited:
print(node,end=' ')
visited.append(node)
for nb in tree[node]:
dfs_traversal(tree, visited,nb)
# 遍歷樹狀結構（廣度優先搜尋）
visited = []
queue = []
def bfs_traversal(tree,visited,node):
queue.append(node)
while queue:
node = queue.pop(0)
if node not in visited:
print(node,end=' ')
visited.append(node)
for nb in tree[node]:
queue.append(nb)
# 新增節點
tree[7] = [8, 9]
tree[8] = []
tree[9] = []
# 刪除節點
# del tree[7]
# 修改節點的子節點
tree[1] = [2, 3, 7]
# 印出深度優先搜尋結果
visited=[]
print("DFS Traversal:")
dfs_traversal(tree,visited,1)
# 印出廣度優先搜尋結果
visited = []
print("\nBFS Traversal:")
bfs_traversal(tree,visited,1)
def dfs(graph, node, visited, leaf_nodes):
if node not in visited:
visited.add(node)
print(node, end=' ')
if not graph[node]: # 檢查節點是否為樹葉
leaf_nodes.append(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited, leaf_nodes)
# 使用範例
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['G'], 'F': [],'G':[]}
for k, v in graph.items():
visited = set()
leaf_nodes = []
dfs(graph, k, visited, leaf_nodes)
print(" -- Leaf nodes:", leaf_nodes)
# 執行結果
A B D E G C F -- Leaf nodes: ['D', 'G', 'F']
B D E G -- Leaf nodes: ['D', 'G']
C F -- Leaf nodes: ['F']
D -- Leaf nodes: ['D']
E G -- Leaf nodes: ['G']
F -- Leaf nodes: ['F']
G -- Leaf nodes: ['G']
#select sort
#d = [1,3,5,7,9,10,8,6,2,4]
#n = len(d)
#for i in range(n):
# imin = i
# for j in range(i+1,n):
# if d[j]<d[imin]:
# imin=j
# d[i],d[imin]=d[imin],d[i]
# print(d)
# insert sord
d = [3,1,5,7,9,10,8,6,2,4]
n= len(d)
dd = [-99,99]
for i in range(n):
j=0
while d[i]>dd[j] and j+1<len(dd):j+=1
dd = dd[:j]+[d[i]]+dd[j:]
dd = dd[1:-1]
print(dd)
#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# g = {
# 1:[2,3],
# 2:[4,5],
# 3:[6,7],
# 4:[],
# 5:[8],
# 6:[],
# 7:[],
# 8:[]
# }
d = '''
1 2
1 3
2 4
2 5
3 6
3 7
5 8
'''
d = d.strip()
e = [int(i) for i in d if i >='0' and i<='9']
d = [i.split() for i in d.split('\n')]
d = [[int(i[0]),int(i[1])] for i in d]
g = {}
for k in set(e):
a = []
for j in d:
if k == j[0]:
a.append(j[1])
g[k]=a
print(g)
g = {}
for key in set(e):
a =[]
for j in d:
if j[0]==key:
a.append(j[1])
g[key]=a
print(g)
v = []
def dfs(g,v,n):
print(n,end=' ')
v.append(n)
for nb in g[n]:
if nb not in v:
dfs(g,v,nb)
dfs(g,v,1)
print()
v=[]
q = []
def bfs(g,v,n):
q.append(n)
while q:
p=q.pop(0)
if p not in v:
print(p,end=' ')
v.append(p)
for nb in g[p]:
if nb not in v:
q.append(nb)
bfs(g,v,1)
# 執行結果
# 1 2 4 5 8 3 6 7
# 1 2 3 4 5 6 7 8
g = {
1:[2,3],
2:[4,5],
3:[6,7],
4:[],
5:[8],
6:[],
7:[],
8:[]
}
v = []
def dfs(g,v,n):
print(n,end=' ')
v.append(n)
for nb in g[n]:
if nb not in v:
dfs(g,v,nb)
dfs(g,v,1)
print()
v=[]
q = []
def bfs(g,v,n):
q.append(n)
while q:
p=q.pop(0)
if p not in v:
print(p,end=' ')
v.append(p)
for nb in g[p]:
if nb not in v:
q.append(nb)
bfs(g,v,1)
# 執行結果
# 1 2 4 5 8 3 6 7
# 1 2 3 4 5 6 7 8
for d in ['[][][]','{}[()]','{[()]}','{[()}]']:
left_stack = []
msg = 'OK'
for i in d:
if i in '([{':
left_stack.append(i)
else:
t = left_stack.pop()
ti = t+i
if not(ti =='()' or ti =='[]' or ti =='{}'):
msg = 'Error'
print(d,msg)
#執行結果
[][][] OK
{}[()] OK
{[()]} OK
{[()}] Error
d = list(range(1,15))
q = []+ d
print(q)
k = 7
i = 0
while len(q)>1:
t = q.pop(0)
i+=1
if i%k!=0:
q.append(t)
else:
print(q)
#執行結果
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[8, 9, 10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]
[9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6]
[3, 4, 5, 6, 9, 10, 11, 12, 13, 1]
[12, 13, 1, 3, 4, 5, 6, 9, 10]
[9, 10, 12, 13, 1, 3, 4, 5]
[5, 9, 10, 12, 13, 1, 3]
[5, 9, 10, 12, 13, 1]
[9, 10, 12, 13, 1]
[12, 13, 1, 9]
[9, 12, 13]
[12, 13]
[13]
