[数据结构与算法]实操：二叉树广度遍历

广度遍历

class Node(object):
    def __init__(self, item):  # 构造结点的时候，需要告知存的数据item
        self.elem = item  # 同链表
        # 跟链表不同的是，树是有分叉的，这种分叉表示如下
        # 要区分左子节点+右子节点
        self.lchild = None
        self.rchild = None


# 接下来，实现树
class Tree(object):

    # 构造函数
    def __init__(self):
        # 根的节点
        self.root = None

    # 定义一个i的方法，即，把定义的数据追加到这棵树上
    def add(self, item):
        # 只考虑末尾添加，不考虑头部添加和中间添加
        # 从上往下，一层一层地找，最后一层的位置，就是要添加节点的位置
        # 广度遍历=层次遍历
        # 先遍历A，看A有没有左子节点和右子节点
        # 然后处理左节点的B，B是不是有左右子节点
        # 然后处理A的子节点，C
        # 依此类推，就形成了：左边依次取出元素，而右边依次添加元素：ABC DEFG,即队列

        # 此处需要构造一个节点
        node = Node(item)
        # 布尔值：空列表返回False,[None]列表返回True,列表只要有元素就返回真，None会影响下方循环的结果，因此此处需要一个判断
        if self.root is None:
            self.root = node
            return
        # 因为查找的时候需要用到“队列”，因此要构造一个队列,用来存放即将处理的东西
        queue = []
        # 把根节点放进队列
        queue.append(self.root)
        # 上面两句可以写成queue=[self.root]

        while queue:  # 截止条件是：判断当前列表为空
            # 先从队列中取出一个节点，用cur_node表示当前的节点
            # 从队头开始取节点
            cur_node = queue.pop(0)
            # 一开始追加的是根，现在取出来的就也是根
            # 取出根之后，看当前根/节点的左孩子是否为空，如果为空，则可以把新建节点放在当前节点下端
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            # 如果不为空，左孩子存在，那么就把当前的左孩子追加到队列里
            else:
                queue.append(cur_node.lchild)

            # 然后，同理处理右孩子
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

            # 处理完之后，要开始从cur_node=queue.pop(0)循环，所以要写一个循环while，如上,直到找到任务节点为止

        # 开始遍历
    def breadth_tree(self):
        # 遍历过程的思路和def add(self,item)的思路是一样的
        '''广度遍历'''
        # 如果当前根节点是None,直接返回
        if self.root is None:
            return
            # 需要一个队列，记录处理情况
        queue = []
        queue.append(self.root)
        while queue:
                # 取出一个节点
            cur_node = queue.pop(0)
                # 需要先打印，打印当前节点的元素
            print(cur_node.elem)
                # 判断左孩子是否存在，如果存在，把左孩子追加到队列当中。即对应到上面算法中的else
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
                # 判断右孩子是否存在，如果存在，把右孩子追加到队列当中
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)
                # 结束后继续循环while


if __name__ == "__main__":
    tree = Tree()
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.breadth_tree()

结果

1
2
3
4
5