数据结构树 python

ゝ一世哀愁。 2023-01-21 05:29 34阅读 0赞

### 基本功能 ###

1.  顺序存储
2.  前序遍历
3.  中序遍历
4.  前序遍历
5.  层级遍历
6.  顺序存储数据/中序数据+前序数据/中序数据+后序数据 确定一棵树

### 代码 ###

from queue import Queue
    
    
    class BinaryNode:
    
        def __init__(self, right=None, left=None, node=None):
            self.right = right
            self.left = left
            self.node = node
    
    
    class CompleteBinary:
        """
        完全二叉树，数据顺序存储
        如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点
        通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来
        """
    
        def __init__(self, base_data: list, mid_data: list = None, data_kind=0):
            """
            初始化树，此为 完全二叉树，会将数据转化成顺序存储
            顺序存储数据/中序+前序/中序+后序 可以唯一确定一棵树
            如果，使用的是非完全二叉树，可以使用None填充节点
            :param base_data: 原始数据，存储格式与data_kind对应
            :param mid_data: 中序数据
            :param data_kind: 取值，0：顺序数据；1：前序数据；2：后序数据
            """
            self.__init_tree(base_data, mid_data, data_kind)
            # 节点个数
            self.nodes = len(self.tree)
    
        @staticmethod
        def floor_traverse(root):
            """
            层级遍历
            """
            floor = Queue()
            floor.put(root)
            floor_data = []
            while True:
                if floor.empty():
                    break
                node = floor.get()
                if node is None:
                    continue
                if node.node is not None:
                    floor_data.append(node.node)
                if node.left is not None:
                    floor.put(node.left)
                if node.right is not None:
                    floor.put(node.right)
            return floor_data
    
        def __init_pre_mid(self, base_data: list, mid_data: list, root, i, j, length):
            """
            递归获取树
            :param base_data: 前序数据
            :param mid_data: 顺序数据
            :param root: 节点
            :param i: 根节点的位置
            :param j:
            :param length: 节点个数
            :return:
            """
            if length <= 0:
                return BinaryNode()
            if root is None:
                root = BinaryNode(node=base_data[i])
            else:
                root.node = base_data[i]
            mid = mid_data.index(base_data[i])
            root.left = self.__init_pre_mid(base_data, mid_data, root.left, i + 1, j, mid - j)
            root.right = self.__init_pre_mid(base_data, mid_data, root.right, i + (mid - j) + 1, mid + 1,
                                             length - 1 - (mid - j))
            return root
    
        def __init_preorder(self, base_data, mid_data):
            """
            前序数据 + 顺序数据 获取树形数据
            1. 确定根节点，树根是当前树中所有元素在前序遍历最先出现的元素
            2. 求解子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素都是右子树。
            3. 若根的左节点为空或右节点为空，则该方向子树为空，若都为空，则根节点已是叶子节点
            4. 递归求解树冒充度上述步骤
            :param base_data: 前序数据
            :param mid_data: 顺序数据
            :return:
            """
            root = BinaryNode(node=base_data[0])
            self.__init_pre_mid(base_data, mid_data, root, 0, 0, len(mid_data))
            self.tree = [''] + self.floor_traverse(root)
            print(self.tree)
    
        def __init_post_mid(self, base_data: list, mid_data: list, root, i, j, length):
            if length <= 0:
                return BinaryNode()
            if root is None:
                root = BinaryNode(node=base_data[i])
            else:
                root.node = base_data[i]
            mid = mid_data.index(base_data[i])
            root.left = self.__init_post_mid(base_data, mid_data, root.left, i - 1 - (length - 1 - (mid - j)), j, mid - j)
            root.right = self.__init_post_mid(base_data, mid_data, root.right, i - 1, mid + 1, length - 1 - (mid - j))
            return root
    
        def __init_post(self, base_data, mid_data):
            """
            后序数据 + 顺序数据 获取树形数据
            1. 确定根节点，树根是当前树中所有元素在后序遍历最后的元素
            2. 求解子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素都是右子树。
            3. 若根的左节点为空或右节点为空，则该方向子树为空，若都为空，则根节点已是叶子节点
            4. 递归求解树冒充度上述步骤
            :param base_data: 后序数据
            :param mid_data: 顺序数据
            :return:
            """
            root = BinaryNode(node=base_data[0])
            self.__init_post_mid(base_data, mid_data, root, len(base_data) - 1, 0, len(mid_data))
            self.tree = [''] + self.floor_traverse(root)
    
        def __init_tree(self, base_data, mid_data, data_kind):
            if data_kind == 0:
                self.tree = base_data
            elif data_kind == 1:
                self.__init_preorder(base_data, mid_data)
            elif data_kind == 2:
                self.__init_post(base_data, mid_data)
            else:
                raise ValueError("data_kind 必须是0或1或2")
    
        def __preorder_traversal(self, function, local=1):
            function(self.tree[local])
            if 2 * local < self.nodes:
                self.__preorder_traversal(function, 2 * local)
    
            if 2 * local + 1 < self.nodes:
                self.__preorder_traversal(function, 2 * local + 1)
    
        def preorder_traversal(self):
            """
            前序遍历
            :return:
            """
            if self.tree:
                self.__preorder_traversal(print)
    
        def __mid_traversal(self, function, local=1):
            if 2 * local < self.nodes:
                self.__mid_traversal(function, 2 * local)
            function(self.tree[local])
            if 2 * local + 1 < self.nodes:
                self.__mid_traversal(function, 2 * local + 1)
    
        def min_traversal(self):
            """
            中序遍历
            :return:
            """
            if self.tree:
                self.__mid_traversal(print)
    
        def __post_traversal(self, function, local=1):
            if 2 * local < self.nodes:
                self.__post_traversal(function, 2 * local)
            if 2 * local + 1 < self.nodes:
                self.__post_traversal(function, 2 * local + 1)
            function(self.tree[local])
    
        def post_traversal(self):
            """
            后序遍历
            :return:
            """
            if self.tree:
                self.__post_traversal(print)
    
    
    if __name__ == '__main__':
        # x_data = ['', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
        # data = ['a', 'b', 'd', 'h', 'i', 'e', 'j', 'c', 'f', 'g']
        data = ['h', 'i', 'd', 'j', 'e', 'b', 'f', 'g', 'c', 'a']
        m_data = ['h', 'd', 'i', 'b', 'j', 'e', 'a', 'f', 'c', 'g']
        o_tree = CompleteBinary(data, m_data, 2)
        o_tree.post_traversal()