1 class Node(object):
2 '''定义一个结点,有左孩子和右孩子'''
3 def __init__(self,data):
4 # 结点数据
5 self.data = data
6 # 左、右 孩子指向为空
7 self.lchild = None
8 self.rchild = None
9
10 class BinaryTree(object):
11 '''定义二叉树'''
12 def __init__(self):
13 # 根结点默认为空
14 self.root = None
15
16 def add(self,data):
17 # 添加数据到二叉树中 向最后进行添加数据
18 # 处理顺序：父结点 左孩子 右孩子
19 node = Node(data)
20 # 如果为空树
21 if self.root is None:
22 self.root = node
23 # 空树,加入数据则放在根节点处
24 return
25 queue = [self.root]
26 # 添加根节点,作为存在该结点的标志
27 while queue:
28 # 如果 queue 不为空
29 cur_node = queue.pop(0)
30 # 当前结点指向根节点,取第一个元素
31 if cur_node.lchild is None :
32 # 如果左结点为空
33 cur_node.lchild = node
34 return
35 else:
36 # 添加到指针内,证明存在左结点
37 queue.append(cur_node.lchild)
38 if cur_node.rchild is None:
39 # 如果右结点为空
40 cur_node.rchild = node
41 return
42 else:
43 # 添加到指针内,证明存在右结点
44 queue.append(cur_node.rchild)
45
46
47 def bread_travel(self):
48 '''广度遍历'''
49 if self.root is None:
50 # 如果为空树,则直接返回
51 return
52 queue = [self.root]
53 # 存储存在的元素,通过 cur_node 验证
54 while queue:
55 # pop 方法直到为 [] 为止
56 cur_node = queue.pop(0)
57 # 取出第一个元素
58 print(cur_node.data)
59 # 输出结点
60 if cur_node.lchild is not None:
61 # 如果存在左结点
62 queue.append(cur_node.lchild)
63 # 添加到列表后
64 if cur_node.rchild is not None:
65 # 如果存在右结点
66 queue.append(cur_node.rchild)
67 # 添加到列表后
2020-04-18