现在的位置: 首页 > 操作系统 > 正文

二叉树-按层打印、序列化、反序列化

2020年02月06日 操作系统 ⁄ 共 6619字 ⁄ 字号 评论关闭
文章目录

二叉树按层打印

算法

    准备一个队列

    准备一个二叉树,不一定是完全二叉树

    准备一个变量last,表示当前层的最后一个节点

    准备一个变量next_last,表示下一层的最后一个节点

    将root节点首先放入队列中

    此时last 是root nlast还没有值从队列中拿出root节点,并打印判断root节点的子节点是否存在,如果存在放入队列中,每次放入节点的时候将子节点赋值给nlast拆开说明,假设root两个节点分别是A,B将A节点放入队列中,指定next_last为 A,因为此时并不知道是否有B存在,将B 节点放入队列中,指定next_last为B ,此时很明确第二层的最后一个节点是B如果A节点不存在的话,直接放入B即可,每次放入前需要进行判断是否存在如果没有子节点,队列中将没有节点可以打印,直接跳出循环此时判断一件事情,当前打印的节点root 切好等于 当前last存储的节点 root,打印换行'\n'并让last 等于 next_last也就说,当前层已经换成了第二层了。next_last目前保持不变梳理变量:last为节点B,next_last为节点B,队列中有A,B假设A 有一个左节点C ,B有一个有节点D由于放入了A B 两个节点循环继续,拿出A,并打印,将A的子节点C放入队列中,并使得next_last等于C此时还是判断当前打印的节点A与last中存储的节点B不相同,所以不换行,由于队列有值循环继续

    最终循环会因为队列中没有节点而停止

代码准备工作

注:测试代码使用Python,Python版本3.6

节点类:Node

# 每个节点需要的东西,# 1.节点存储的值# 2.节点的左子节点# 3.节点的右子节点class Node(): def __init__(self,value): self.value = value self.left_node=None self.right_node=None

队列类:Queue

# 队列即先进先出的list,队列类需要的属性# 1.队列大小# 2.队列中的值,用list表示# 3.队列的尾部# 4.在队列尾部插入数据# 5.在队列头部读取数据# 6.队列是否为空# 7.队列是否被塞满class Queue(): def __init__(self,size): self.size = size self.queue=[] self.end=-1 def in_queue(self,value): if self.queue_is_full(): print('Queue full') else: # append 在list尾端插入数据 self.queue.append(value) # 插入一个后top变成了0,依次+1 self.end = self.end+1 def out_queue(self): if self.queue_is_empty(): print('No data') else: # pop(0) 从list的头部拿出一个数据 data = self.queue.pop(0) self.end=self.end-1 return data def queue_is_full(self): # end 是顶部的index +1后等于size就证明没有位置了 if self.end+1 == self.size: return True else: return False def queue_is_empty(self): if self.end == -1: return True else: return False

代码实现

main函数

if __name__ == "__main__": # 创建二叉树 rootNode = Node('root') A = Node('A') B = Node('B') # 跟节点 有两个子节点 A B rootNode.left_node = A rootNode.right_node = B C = Node('C') D = Node('D') # A有左子节点C A.left_node = C # B有有子节点D B.right_node = D # 按层打印上面的二叉树 last = rootNode # 初始 nlast = rootNode # 初始 store_queue = Queue(5)#创建一个大小为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#### 结果 rootA BC D

快速创建二叉树,通过list进行创建

def make_binary_tree(list): if list is None: list = ['root',['A',['C'],None],['B',None,['D']]] rootNode = Node(list[0]) if len(list) >= 2 : if list[1] is not None: rootNode.left_node = make_binary_tree(list[1]) if len(list) >= 3 : if list[2] is not None : rootNode.right_node = make_binary_tree(list[2]) return rootNode

二次测试

if __name__ == "__main__": # make binary tree data ''' rootNode = Node('root') A = Node('A') B = Node('B') rootNode.left_node = A rootNode.right_node = B C = Node('C') D = Node('D') A.left_node = C B.right_node = D ''' list = [ 'root', ['A', ['C', ['E'], ['F'] ], ['D', ['G',['H'],None], None ] ], ['B', ['I',None,['J']], ['K',['L'],None] ] ] rootNode = make_binary_tree(list) # 按层打印上面的二叉树 last = rootNode # 初始 nlast = rootNode # 初始 store_queue = Queue(5)#创建一个大小为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## 结果rootA BC D I KE F G J LH

二叉树序列化

算法

    前序遍历:按照 根-左-右,中序遍历 左-根-右,后序遍历 左-右-根定义一个空字符串,取出根节点Value+‘!’,拼接字符串,‘!’是每个节点value的结束标志先判断左节点是否存在,存在如3的方式同样拼接不存在拼接 '#!'依次下去,直到遍历完毕所有的节点

代码准备工作

Node类

同上

创建二叉树方法

同上

序列化方法

# 前序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----------------------------rootA BC D I KE F G J LH"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!#!#!#!"

抱歉!评论已关闭.