数据结构与算法——树的广度优先遍历

在人生的道路上,不管是潇洒走一回,或者是千山独行,皆须是自己想走的路,虽然,有的人并不是很快就能找到自己的方向和道路,不过,只要坚持到底,我相信,就一定可以找到自己的路,只要找到路,就不必怕路途遥远了。

导读:本篇文章讲解 数据结构与算法——树的广度优先遍历,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

实现:往完全二叉树中添加一个节点,使得添加之后这棵树依旧是一棵完全二叉树

class Node:
    def __init__(self, val):
        self.val = val  # 数据域
        self.left = None  # 左指针域
        self.right = None  # 右指针域


class Tree:
    def __init__(self):
        self.root = None  # 树的根节点

    def add(self, val):
        # 层次遍历, 广度优先遍历
        # val 要添加的节点的值
        # 往树中添加一个节点,并保证添加之后这棵树依旧是一棵完全二叉树
        node = Node(val)
        # 判断树是否为空,如果为空,直接将node设置为根节点
        if not self.root:
            self.root = node
            return
        # 从上往下,从左往右的去遍历整棵树,然后找到第一个空位
        # 把节点添加进去
        queue = [self.root]  # 存每一层的节点
        while True:
            # 第一次 queue = [root]
            # 第二次 queue = [root.left, root.right]
            # queue = [root.right, root.left.left, root.left.right]
            # queue = [root.left.left, root.left.right, root.right.left, root.right.right]
            cur_node = queue.pop(0)
            # 先找左边,看有没有空位
            if not cur_node.left:
                cur_node.left = node
                return
            # 左边没有空位,就找右边
            elif not cur_node.right:
                cur_node.right = node
                return
            # 如果都没有空位,那就把左边节点与右边节点都加到之后要判断的节点中
            queue.extend((cur_node.left, cur_node.right))

    def show(self):
        # 展示树
        if not self.root:
            return
        # 从上往下,从左往右的去遍历整棵树,然后找到第一个空位
        # 把节点添加进去
        queue = [self.root]  # 存每一层的节点
        i = 1
        while queue:
            size = len(queue)  # 当前层的元素个数
            print(f'第{i}层', end='\t')
            for _ in range(size):
                node = queue.pop(0)  # 队列中的第一个元素抛出来
                print(node.val, end=' ')  # 对当前元素进行操作
                # 节点的左孩子与右孩子添加到队列里
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            print()
            i += 1
if __name__ == '__main__':
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.show()

执行结果:
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/123539.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!