复习 二叉树的创建

 1 ‘‘‘
 2 树：
 3     每一个结点都有零个或多个子结点
 4     没有父节点的节点称为根节点
 5     每一个非根结点有且只有一个父结点
 6     除了根结点外,每一个子节点可以分为多个不相交的子树
 7 二叉树性质：
 8     在二叉树的第 i 层 最多有 2^(i-1) 个结点
 9     深度为 k 的二叉树最多有 2^k - 1 个结点
10     叶子结点数为 N0  度数为 2 的结点数为 N2
11         N0 = N2 + 1
12     具有 n 个结点的完全二叉树的深度为 log2(n+1)
13     完全二叉树:
14         编号为 i 的结点
15             左孩子 -> 2i
16             右孩子 -> 2i + 1
17         左孩子 的 父结点 编号必为 i/2
18 
19 ‘‘‘
20 class Node(object):
21     ‘‘‘定义一个结点,有左孩子和右孩子‘‘‘
22     def __init__(self,data):
23         # 结点数据
24         self.data = data
25         # 左、右 孩子指向为空
26         self.lchild = None
27         self.rchild = None
28 
29 class BinaryTree(object):
30     ‘‘‘定义二叉树‘‘‘
31     def __init__(self):
32         # 根结点默认为空
33         self.root = None
34 
35     def add(self,data):
36         # 添加数据到二叉树中 向最后进行添加数据
37         # 处理顺序：父结点 左孩子 右孩子
38         node = Node(data)
39         # 如果为空树
40         if self.root is None:
41             self.root = node
42             # 空树,加入数据则放在根节点处
43             return
44         queue = [self.root]
45         # 添加根节点,作为存在该结点的标志
46         while queue:
47             # 如果 queue 不为空
48             cur_node = queue.pop(0)
49             # 当前结点指向根节点,取第一个元素
50             if cur_node.lchild is None :
51                 # 如果左结点为空
52                 cur_node.lchild = node
53                 return
54             else:
55                 # 添加到指针内,证明存在左结点
56                 queue.append(cur_node.lchild)
57             if cur_node.rchild is None:
58                 # 如果右结点为空
59                 cur_node.rchild = node
60                 return
61             else:
62                 # 添加到指针内,证明存在右结点
63                 queue.append(cur_node.rchild)