数据结构和算法-17-二叉树的广度优先遍历和二叉树节点插入操作

布满荆棘的人生 2021-12-20 11:15 251阅读 0赞

这篇来用代码实现一颗二叉树，在实现二叉树之前，我们需要分析，如何给一棵树添加元素，添加的规则，其实先要查找和判断节点，查找和判断节点的过程，我们使用了广度优先遍历方法。

1.二叉树的广度优先遍历

先摆放一颗二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

思路1，我们先要构造一个个节点，节点我们前面使用过，Node, 这里也一样，只不过这个节点属性，除了一个元素，还有一个左子节点和右子节点这两个属性。例如构造A节点，元素存储是A，左节点是B，右节点是C。

思路2：如何理解广度优先遍历

假如说，我们需要在上面这棵二叉树基础上，添加一个K元素，那么到底添加哪里，挂在哪个节点下呢。广度优先的是这么去理解。一开始，找到根节点A，然后判断A节点是否都有左右节点，发现有B C这两个左右节点。根据上到下，左到右原则。接下来跳到B节点，又判断B下有没有左右子节点，找出了D E，然后跳到C节点，判断C有没有左右节点，找出了FG，接下来第三层，跳转到D节点，又判断是否有左右节点，发现了H I节点，然后跳转E节点，判断是否有左右节点，发现只有J这个左节点，所以新插入节点就需要挂在E下作为E的右节点。而不是随便 F 或者G下挂。这种过程就是二叉树的广度优先遍历。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1][]

在上面查找节点过程和跳转下一个节点过程，这里其实产生了一个我们前面学习过的数据结构，叫队列，一头进，一头出的特点。

第一次：找到A节点，判断后，找出了 BC节点，数列为\[ABC\]，当前节点为A，队列可以这么表示\[A   BC\]

第二次：找到B节点，判断后，找出了DE节点，数列为\[ABCDE\]，当前节点是B,队列可以这么表示\[AB  CDE\]

第三次：找到C节点，判断后，找出了FG节点，数列为\[ABCDEFG\],当前节点是C，队列可以这么表示\[ABC DEFG\]

第四次：找到D节点，判断后，找出了HI节点，数列为\[ABCDEFGHI\],当前节点是D，队列可以这么表示\[ABCD EFGHI\]

看看这个数列被分成前后两部分，一部分查找过节点就往前部分数列靠拢，有点像排队出去的效果；每个左右子节点添加到数列的尾部，这个就像队列的元素添加；整个过程就像一个队列，所以，我们在实现二叉树的add方法的时候，就需要使用到队列这个数据结构。

2.代码实现

下面来按照广度优先的思路写一个遍历方法，并测试。

# coding:utf-8
    
    
    class Node(object):
        """节点"""
        def __init__(self, itme):
            self.ele = itme
            self.lchild = None
            self.rchild = None
    
    
    class BinaryTree(object):
        """二叉树"""
        def __init__(self):
            self.root = None
    
        def add(self, item):
            node = Node(item)
            if self.root is None:
                self.root = node
                return
            # 一个队列，添加根元素
            queue = [self.root]
            while queue:
                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)
    
        def breadth_travle(self):
            """广度遍历"""
            if self.root is None:
                return
            queue = [self.root]
            while queue:
                cur_node = queue.pop(0)
                print(cur_node.ele)
                if cur_node.lchild is not None:
                    queue.append(cur_node.lchild)
                if cur_node.rchild is not None:
                    queue.append(cur_node.rchild)
    
    if __name__ == "__main__":
        tree = BinaryTree()
        tree.add(1)
        tree.add(2)
        tree.add(3)
        tree.add(4)
        tree.add(5)
        tree.add(6)
        tree.breadth_travle()

运行结果

1
    2
    3
    4
    5
    6

因为插入和遍历都是按照广度优先，所以打印出来的效果就是这样顺序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20211220/c349db02e5654ca9ba68d6f6e7500d9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1]: /images/20211220/50a6d0624ec94a699373e451bce54e0a.png