同上
序列化方法 # 前序 def pre_serialize_binary_tree(node): string = '' string = string + str(node.value)+'!' if node.left_node is not None: string = string + serialize_binary_tree(node.left_node) else: string = string + "#!" if node.right_node is not None: string = string + serialize_binary_tree(node.right_node) else: string = string + "#!" return string # 中序 def mid_serialize_binary_tree(node): string = '' #string = string + str(node.value)+'!' if node.left_node is not None: string = string + mid_serialize_binary_tree(node.left_node) else: string = string + "#!" string = string + str(node.value)+'!' if node.right_node is not None: string = string + mid_serialize_binary_tree(node.right_node) else: string = string + "#!" return string # 后序 def back_serialize_binary_tree(node): string = '' if node.left_node is not None: string = string + back_serialize_binary_tree(node.left_node) else: string = string + "#!" if node.right_node is not None: string = string + back_serialize_binary_tree(node.right_node) else: string = string + "#!" string = string + str(node.value)+'!' return string 代码实现 main函数 if __name__ == "__main__": list = [ 'root', ['A', ['C', ['E'], ['F'] ], ['D', ['G',['H'],None], None ] ], ['B', ['I',None,['J']], ['K',['L'],None] ] ] rootNode = make_binary_tree(list) result1 = pre_serialize_binary_tree(rootNode) print("前序遍历") print(result1) #rootNode = ascertain_root_node(rootNode) print("中序遍历") result2 = mid_serialize_binary_tree(rootNode) print(result2) print("后序遍历") result3 = back_serialize_binary_tree(rootNode) print(result3) ## 结果 前序遍历 "root!A!C!E!#!#!F!#!#!D!G!H!#!#!#!#!B!I!#!J!#!#!K!L!#!#!#!" 中序遍历 "#!E!#!C!#!F!#!A!#!H!#!G!#!D!#!root!#!I!#!J!#!B!#!L!#!K!#!" 后序遍历 "#!#!E!#!#!F!C!#!#!H!#!G!#!D!A!#!#!#!J!I!#!#!L!#!K!B!root!" 二叉树反序列化 算法将序列化好的字符串按照节点结束符拆分成数组
根据前序、中序、后序的规则，将数组数据重新组成二叉树
为# 的时候为空节点，赋值None
代码准备工作 Node类同上
按层打印二叉树的方法同上
反序列化函数 # 前序 def pre_deserialize_binary_tree(node_list): tmp_node = node_list.pop(0) rootNode = Node(tmp_node) if tmp_node != "#": rootNode.left_node = pre_deserialize_binary_tree(node_list) rootNode.right_node = pre_deserialize_binary_tree(node_list) else: return None return rootNode # 中序 # 注：实在没找到中序反序列化的方法，望大神指点一下 按层打印二叉树方法 # 抽成方法 以备使用 def print_tree(rootNode): # 按层打印上面的二叉树 last = rootNode # 初始 nlast = rootNode # 初始 store_queue = Queue(100)#创建一个大小为5的队列 store_queue.in_queue(rootNode)# 初始放入rootNode while store_queue.queue: # 取出node tmp_node = store_queue.out_queue() # 打印 print(tmp_node.value,end=' ') # 放入子节点 if tmp_node.left_node is not None: store_queue.in_queue(tmp_node.left_node) nlast = tmp_node.left_node if tmp_node.right_node is not None: store_queue.in_queue(tmp_node.right_node) nlast = tmp_node.right_node # 判断是否换行 if tmp_node == last: print("\n") last = nlast 代码实现 main函数 if __name__ == "__main__": # make binary tree data list = [ 'root', ['A', ['C', ['E'], ['F'] ], ['D', ['G',['H'],None], None ] ], ['B', ['I',None,['J']], ['K',['L'],None] ] ] rootNode = make_binary_tree(list) result1 = pre_serialize_binary_tree(rootNode) print("前序遍历") print(result1) #rootNode = ascertain_root_node(rootNode) print("中序遍历") result2 = mid_serialize_binary_tree(rootNode) print(result2) print("后序遍历") result3 = back_serialize_binary_tree(rootNode) print(result3) # 直接使用上面序列化的结果 tree_list1 = result1.strip(" ").split('!') tree_list1.pop() de_result1 = pre_deserialize_binary_tree(tree_list1) # 按层打印 print_tree(de_result1) # 继续序列化进行对比 test = pre_serialize_binary_tree(de_result1) print(test) print(result1) # ----------------------------Result---------------------------- root A B C D I K E F G J L H "root!A!C!E!#!#!F!#!#!D!G!H!#!#!#!#!B!I!#!J!#!#!K!L!#!#!#!" "root!A!C!E!#!#!F!#!#!D!G!H!#!#!#!#!B!I!#!J!#!#!K!L!#!#!#!"