手机版
你好,游客 登录 注册
背景:
阅读新闻

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

[日期:2019-03-22] 来源:Linux社区  作者:primadonna [字体: ]

二叉树按层打印

算法

  1. 准备一个队列

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

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

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

  5. 将root节点首先放入队列中

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

代码准备工作

注:测试代码使用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

二叉树序列化

算法

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

代码准备工作

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!"

二叉树反序列化

算法

  1. 将序列化好的字符串按照节点结束符拆分成数组
  2. 根据前序、中序、后序的规则,将数组数据重新组成二叉树
  3. 为# 的时候为空节点,赋值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!#!#!#!"

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-03/157655.htm

linux
相关资讯       二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款