python实现二叉树

1.二叉树

• 关于树实际是编程中遇到数据结构，根节点之外每个节点都有一个父节点，根节点没有父节点，除叶子节点之外所有节点都有一个或是多个子叶子节点，父节点何子节点之间通过指针连接(Go/Java有指针的概念，简单说指针就是地址)

• 二叉树排序方式

  • 广度遍历（层次遍历）
    • 广度优先按照层次，一层一层遍历
  • 深度遍历
    • 前序：根左右（把跟放到最前面）
    • 中序：左根右（把根放到中间）
    • 后序：左右根（把根放到最后）

2.排序二叉树

• 代码实现：

class Node():
    """封装节点对象"""
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None

class Tree():
    def __init__(self):
        # 构造出一颗空的二叉树
        # root要指向第一个节点的地址，如果root指向了None,则意味着该二叉树为空
        self.root = None
    def insert(self,item):
        node = Node(item)
        cur = self.root
        if cur is None:
            self.root = node
            return
        while True:
            # 这里用while循环判断根，左，右节点是否为None逐级插入数据
            if item < cur.item:
                if cur.left is None:
                    cur.left = node
                    return
                else:
                    cur = cur.left
            else:
                if cur.right is None:
                    cur.right = node
                    return
                else:
                    cur = cur.right
    def pre_sequence(self,root):
        #前序
        if root is None:
            return
        print(root.item,end = " ")
        self.pre_sequence(root.left)
        self.pre_sequence(root.right)
    def middle_sequence(self,root):
        #中序
        if root is None:
            return
        self.middle_sequence(root.left)
        print(root.item, end=" ")
        self.middle_sequence(root.right)
    def back_sequence(self,root):
        #后续
        if root is None:
            return
        self.back_sequence(root.left)
        self.back_sequence(root.right)
        print(root.item,end=" ")
        def travel(self,root):
        if root == None:
            return
        cur = root
        # 队列先进先出
        queue = [cur,]
        while queue:
            # 循环，pop，获取pop节点，左右子节点，不为None,加入队列继续循环
            n = queue.pop(0)
            print(n.item, end = " ")
            if n.left != None:
                queue.append(n.left)
            if n.right != None:
                queue.append(n.right)
tree = Tree()
tree.insert(3)
tree.insert(8)
tree.insert(5)
tree.insert(7)
tree.insert(6)

tree.pre_sequence(tree.root)#
print("
")
tree.middle_sequence(tree.root)
print("
")
tree.back_sequence(tree.root)
print("
")
tree.travel(tree.root)
"""
打印结果：
前序：3 8 5 7 6 

中序：3 5 6 7 8 

后续：6 7 5 8 3

广度:3 8 5 7 6
"""

• 在执行insert方法时最终构建二叉树如下图：