数据结构 python：树简单操作

小鱼儿 2023-01-15 13:22 150阅读 0赞

### 数据结构：树的生成 ###

*   *   *  原始数据
         *  代码

**笔者提供的代码，都是基于python的语言特性实现的，简单明了为上**

### 原始数据 ###

1.  `child`: 子节点
2.  `parent`：父节点
3.  如果`parent==child`，则为根节点（这里是森林的结构）

child,parent
    a,b
    b,c
    c,c

### 代码 ###

1.  初始化树
2.  层级遍历
3.  前序遍历、后序遍历
4.  获取枝干，查找节点

import json
    
    from copy import deepcopy
    from collections import defaultdict, OrderedDict
    
    
    class Tree:
        def __init__(self, par2chi: list, parent_key='parent', child_key='child'):
            """
            有父子结构组成的数据体系，结束标志：obj[self.parent_key] == obj[self.child_key]
            :param par2chi: [{self.parent_key: '', self.child_key: ''}]
            """
            self.child_key = child_key
            self.parent_key = parent_key
            self.tree = self.init_tree(par2chi)
    
        def __end_signal(self, parent, child):
            """
            结束信号，森林的根节点的标志
            """
            return parent == child
    
        def init_tree(self, par2chi):
            """
            初始化树结构，主要是利用 python 的语言特性实现的，表面上看，时间复杂度是n，空间复杂度n，n为par2chi的大小
            """
            original = defaultdict(dict)
            original_c = defaultdict(dict)
            for row in par2chi:
                if row[self.child_key] not in original_c:
                    original_c[row[self.child_key]] = dict()
                if self.__end_signal(row[self.parent_key], row[self.child_key]):
                    original[row[self.parent_key]] = original_c[row[self.child_key]]
                else:
                    original_c[row[self.parent_key]][row[self.child_key]] = original_c[row[self.child_key]]
            return original
    
        def floor_traverse(self):
            """
            层级遍历，时间复杂度n，层节点最多的一层的节点个数
            :return: {"第几层": ["节点"]}
            """
            floor = defaultdict(list)
            floor_tree = deepcopy(self.tree)
            on_floor = 1
            while True:
                on_floor_tree = OrderedDict()
                for key, value in floor_tree.items():
                    floor[on_floor].append(key)
                    if value:
                        on_floor_tree.update(**value)
                if not on_floor_tree:
                    break
                floor_tree = on_floor_tree
                on_floor += 1
            return floor
    
        def __insert_node(self, c_tree, node):
            if node[self.parent_key] in c_tree:
                c_tree[node[self.parent_key]][node[self.child_key]] = {
        }
                return True
            for key, value in c_tree.items():
                if self.__insert_node(value, node):
                    return True
    
        def insert_node(self, node):
            """
            插入节点
            :param node: {self.parent_key: '', self.child_key: ''}
            :return:
            """
            self.__insert_node(self.tree, node)
    
        def __preorder_traversal(self, c_tree: dict, function):
            for key, value in c_tree.items():
                function(key)
                if value:
                    self.__preorder_traversal(value, function)
    
        def preorder_traversal(self):
            """
            前序遍历
            :return:
            """
            self.__preorder_traversal(self.tree, lambda x: '')
    
        def __post_order_traversal(self, c_tree: dict, function):
            for key, value in c_tree.items():
                if value:
                    self.__post_order_traversal(value, function)
                function(key)
    
        def post_order_traversal(self):
            """
            后序遍历
            :return:
            """
            self.__post_order_traversal(self.tree, lambda x: '')
    
        def get_level(self, c_tree: dict, result: list, add_signal, path=None):
            """
            获取需要新添加的数据
            :param c_tree: 原始数据
            :param result: 结果
            :param path:
            :param add_signal: 需要添加到结果的条件
            :return:
            """
            if path is None:
                path = []
            for k, v in c_tree.items():
                path_new = deepcopy(path)
                path_new.append(k)
                if add_signal(k, v):
                    result.append(path_new)
                if v:
                    self.get_level(v, result, add_signal, path=path_new)
    
        def branch(self):
            """
            获取分支，根节点到每个节点（或是到叶子节点）的路径，可以扩展为查找某个节点
            :return:
            """
            # 所有节点
            result = list()
            self.get_level(self.tree, result, lambda k, v: True)
            # print(result)
            # 叶子节点
            result = list()
            self.get_level(self.tree, result, lambda k, v: not v)
            # print(result)
            # 指定节点
            result = list()
            self.get_level(self.tree, result, lambda k, v: k in ['o', 'i', 'x'])
            # print(result)
            result = list()
            # 查找某个节点是否存在
            self.get_level(self.tree, result, lambda k, v: k in ['jq'])
            # print(bool(result))
    
    
    if __name__ == '__main__':
        data = [
            {
        'parent': 'y', 'child': 'y'},
            {
        'parent': 'y', 'child': 'a'}, {
        'parent': 'a', 'child': 'e'}, {
        'parent': 'a', 'child': 'f'},
            {
        'parent': 'a', 'child': 'g'}, {
        'parent': 'y', 'child': 'b'}, {
        'parent': 'b', 'child': 'm'},
            {
        'parent': 'b', 'child': 'n'}, {
        'parent': 'y', 'child': 'c'}, {
        'parent': 'c', 'child': 'h'},
            {
        'parent': 'y', 'child': 'd'}, {
        'parent': 'd', 'child': 'i'}, {
        'parent': 'd', 'child': 'j'},
            {
        'parent': 'd', 'child': 'k'}, {
        'parent': 'm', 'child': 'o'}, {
        'parent': 'm', 'child': 'p'},
            {
        'parent': 'i', 'child': 'q'}, {
        'parent': 'k', 'child': 'x'}
        ]
        tree = Tree(data)
        tree.insert_node({
        'parent': 'x', 'child': 'r'})
        print(json.dumps(tree.tree, indent=4))