二叉树按层打印 算法
准备一个队列
准备一个二叉树，不一定是完全二叉树
准备一个变量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 #### 结果 root A B C 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 ## 结果 root A B C D I K E F G J L H 二叉树序列化 算法前序遍历：按照 根-左-右，中序遍历 左-根-右，后序遍历 左-右-根
定义一个空字符串，
取出根节点Value+‘!’，拼接字符串，‘!’是每个节点value的结束标志
先判断左节点是否存在，存在如3的方式同样拼接
不存在拼接 '#!'
依次下去，直到遍历完毕所有的节点
代码准备工作 Node类同上
创建二叉树方法