二叉树构建、深度遍历、广度优先遍历

二叉树的构建：

class Tree:
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)
t = Tree()
for i in range(10):
    t.add(i)

深度优先遍历：

# 定义一个树节点
class TreeNode:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left     # 左子树
        self.right = right   # 右子树

# 实例化一个树节点
node1 = TreeNode("A",
                 TreeNode("B",
                          TreeNode("D"),
                          TreeNode("E")
                          ),
                 TreeNode("C",
                          TreeNode("F"),
                          TreeNode("G")
                          )
                 )

print(node1)
# 前序遍历
def preTraverse(root):
    if root is None:
        return None
    print(root.data,end=' ')
    preTraverse(root.left)
    preTraverse(root.right)


# 中序遍历
def midTraverse(root):
    if root is None:
        return
    midTraverse(root.left)
    print(root.data,end=' ')
    midTraverse(root.right)


# 后序遍历
def afterTraverse(root):
    if root is None:
        return
    afterTraverse(root.left)
    afterTraverse(root.right)
    print(root.data,end=' ')


if __name__ == "__main__":
    preTraverse(node1)
    print('\n')
    print("------------------------")
    midTraverse(node1)
    print('\n')
    print("------------------------")
    afterTraverse(node1)

广度优先遍历：

def BFS(root):
    res = []
    # 如果根节点为空，则返回空列表
    if root is None:
        return res
    # 模拟一个队列储存节点
    q = []
    # 首先将根节点入队
    q.append(root)
    # 列表为空时，循环终止
    while len(q) != 0:
        length = len(q)
        for i in range(length):
            # 将同层节点依次出队
            r = q.pop(0)
            if r.left is not None:
                # 非空左孩子入队
                q.append(r.left)
            if r.right is not None:
                # 非空右孩子入队
                q.append(r.right)
            print(r.data)

参考链接：http://www.cnblogs.com/kadycui/p/10184110.html，https://www.cnblogs.com/PrettyTom/p/6677993.html