博客

"""
二叉树的创建：
(1)实现二叉树的链式存储结构，创建二叉树
(2)二叉树的前中后序遍历
"""


class BinTree:
    # 二叉树的节点结构，包括存储数据、左指针、右指针
    class TreeNode:
        __slots__ = {'_element', '_left', '_right'}

        def __init__(self, element, left=None, right=None):
            self._element = element
            self._left = left
            self._right = right

    # 二叉树的初始化，初始时为空树，根节点为空
    # ls用于存储节点地址
    def __init__(self):
        self.root = None
        self.ls = []

    # 二叉树的节点插入操作，以创建完全二叉树的形式
    def add(self, data):
        node = self.TreeNode(data)
        # 如果根节点为空，创建根节点，并将根节点写入列表ls中
        if self.root is None:
            self.root = node
            self.ls.append(self.root)
        else:  # 如果根节点存在，就需要创建根节点的孩子
            rootNode = self.ls[0]
            if rootNode._left is None:
                rootNode._left = node
                self.ls.append(rootNode._left)
            elif rootNode._right is None:
                rootNode._right = node
                self.ls.append(rootNode._right)
                self.ls.pop(0)  # 弹出第一个位置的元素，也就是保证每次循环的第一个节点是接下来插入位置的父母节点

    # 前序遍历，根左右
    def preOrderTraversal(self, root):
        if root is None:
            return
        print(root._element, end=' ')
        self.preOrderTraversal(root._left)
        self.preOrderTraversal(root._right)

    # 中序遍历，左根右
    def inOrderTraversal(self, root):
        if root is None:
            return
        self.inOrderTraversal(root._left)
        print(root._element, end=' ')
        self.inOrderTraversal(root._right)

    # 后序遍历，左右根
    def postOrderTraversal(self, root):
        if root is None:
            return
        self.postOrderTraversal(root._left)
        self.postOrderTraversal(root._right)
        print(root._element, end=' ')

    # 层次遍历，也叫广度优先遍历
    def levelOrderTraversal(self, root):
        if root is None:
            return
        queue = []
        result = []
        node = root
        queue.append(node)
        while queue:
            node = queue.pop(0)
            result.append(node._element)
            if node._left is not None:
                queue.append(node._left)
            if node._right is not None:
                queue.append(node._right)
        for i in result:
            print(i, end=' ')

验证：创建一个序号为1-10的完全二叉树

from eighth_chapter.BinTree import BinTree


def createTree(tree):
    for i in range(1, 11):
        tree.add(i)


if __name__ == '__main__':
    bintree = BinTree()
    createTree(bintree)
    print('前序遍历：', end='')
    bintree.preOrderTraversal(bintree.root)
    print()
    print('中序遍历：', end='')
    bintree.inOrderTraversal(bintree.root)
    print()
    print('后序遍历：', end='')
    bintree.postOrderTraversal(bintree.root)
    print()
    print('层次遍历：', end='')
    bintree.levelOrderTraversal(bintree.root)

结果：
E:\python数据结构与算法\day\Scripts\python.exe E:/python数据结构与算法/eighth_chapter/createTree.py
前序遍历：1 2 4 8 9 5 10 3 6 7 
中序遍历：8 4 9 2 10 5 1 6 3 7 
后序遍历：8 9 4 10 5 2 6 7 3 1 
层次遍历：1 2 3 4 5 6 7 8 9 10 
Process finished with exit code 0