class Node:
def __init__(self, left=None, right=None, value=None):
self.left = left
self.right = right
self.value = value
def build_child(node, value, path):
branch, path = path[:1], path[1:]
if branch == 'L':
if node.left is None:
node.left = Node()
return build_child(node.left, value, path)
elif branch == 'R':
if node.right is None:
node.right = Node()
return build_child(node.right, value, path)
else:
if node.value is None:
node.value = value
return True
else:
return False
def build_tree(input):
tree = Node()
for value, path in input:
if not build_child(tree, value, path):
return
return tree
def is_complete(node):
if node is None:
return True
elif node.value is not None and is_complete(node.left) and is_complete(node.right):
return True
else:
return False
def breadth_first_search(node):
q = [node]
path = []
while q:
node = q.pop(0)
if node is None or node in path:
continue
path.append(node.value)
q.append(node.left)
q.append(node.right)
return path
def solve(input):
tree = build_tree(input)
if tree and is_complete(tree):
print breadth_first_search(tree)
else:
print 'not complete'
def test():
import re
s = """
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (8,LL)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
"""
t = []
for x in re.findall('\((.*?)\)', s):
if not x:
solve(t)
t = []
else:
t.append(x.split(','))
if __name__ == '__main__':
test()
import re
def solve(input):
complete = [True]
#
# build complete binary tree
#
tree = [None]*256
def put(node, index, path):
if not path:
if tree[index] is None:
tree[index] = node
else:
complete[0] = False
elif path[0] == 'L':
put(node, 2*index+1, path[1:])
elif path[0] == 'R':
put(node, 2*index+2, path[1:])
for node, path in input:
put(node, 0, path)
#
# check completeness -- all nodes except the root have parent
#
for i in range(1, len(tree)):
if tree[i] is not None:
if tree[(i-1)/2] is None:
complete[0] = False
break
if complete[0]:
print [x for x in tree if x is not None]
else:
print 'not complete'
def solve_all():
s = """
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (8,LL)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
"""
t = []
for x in re.findall('\((.*?)\)', s):
if not x:
solve(t)
t = []
else:
t.append(x.split(','))
solve_all()
import re
def solve(input):
#
# build complete binary tree
#
tree = [None]*256
def put(node, index, path):
if not path:
tree[index] = node
elif path[0] == 'L':
put(node, 2*index+1, path[1:])
elif path[0] == 'R':
put(node, 2*index+2, path[1:])
input = [x.split(',') for x in re.findall('\((.*?)\)', input)]
for node, path in input:
put(node, 0, path)
#
# check completeness -- all nodes except the root have parent
#
complete = True
for i in range(1, len(tree)):
if tree[i] is not None:
if tree[(i-1)/2] is None:
complete = False
break
if complete:
print [x for x in tree if x is not None]
else:
print 'not complete'
solve('(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR)')
solve('(3,L) (4,R)')
[游戏]猛男测试，挑战 fsg 2.0 脱壳
参考资料
[1] Kahn, A. B. (1962), "Topological sorting of large networks", Communications of the ACM 5 (11): 558–562, doi:10.1145/368996.369025.
[2] Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, P. 146-160.
[3] Robertson,Edward L. (1977) Code Generation for Short/Long Address Machines.
活跃值：
在线值：
浏览人数：614
最近活跃：2019-8-2 12:49
注册时间：2004-04-17
