时间戳

首页 > 解决方案 > 如何从 Python 中的给定节点列表创建简单的非二叉树

python - 如何从 Python 中的给定节点列表创建简单的非二叉树

问题描述

我想这对于有经验的人来说是一个相当简单的问题。这是我第一次学习树结构，所以并不简单。问题如下：

给出一个包含 n 个元素的列表，如下所示：

4 -1 4 1 1

这与 n 大小列表的索引有关：

4 -1 4 1 1（父）

0 1 2 3 4（节点）

本质上，树需要创建在节点的值具有高于它的父节点的位置。如果一个节点的父节点值为-1，则该节点是根节点。

所以上面的树应该是这样的：

根 1，他的孩子是

3（没有孩子）和

4（有孩子 0 和 2）。

之后我需要使用一个简单的深度优先算法来确定树的深度，这个算法的输入是实际的树。说明提到我可以在列表中构建一棵树。现在我完全迷失了，因为我不知道使用哪种结构来构建树以及如何使用它？它应该是一个列表吗？还是一堂课？最终树是包含所有孩子的列表，还是包含所有孩子实例的类的实例？这是我的主要问题，之后我认为我能够实现深度算法。

标签： python

解决方案

好的，所以我想通了，我为节点创建了一个类和一个将这些类实例（实际节点）存储到数组中的函数。每个节点的索引是节点的实际值，每个节点都有存储它的子节点的变量。最后，该函数返回根节点，该根节点已将所有其他节点存储为其后代。现在这个新创建的函数 createTree 可用于创建树并遍历它或确定其深度或任何需要。

class Node():

    def __init__(self,name): 
        self.children = []
        self.name = name 

    def addChild(self, child):
        self.children.append(child)

    def returnChildren(self):
        return self.children

    def getName(self): 
        return self.name 

def createTree(elements):

    list_of_nodes = []

    for i in range(len(elements)):

        list_of_nodes.append(Node(i))


    for i in range(len(elements)):

        if elements[i] == -1:
            root = list_of_nodes[i]

        else:
            list_of_nodes[elements[i]].addChild(list_of_nodes[i])

    return root

推荐阅读