试图在Python中实现树并计算它的高度

Question

class node:
    parent=None
    data=None
    children=[]


def __init__(self, parent, data):
    self.data=data
    self.parent=parent


def set_parent(self, parent):
    self.parent=parent

def set_data(self, data):
    self.data=data

def create_node(parent, data):
    return node(parent, data)

class tree:
    nodes=[]
    root=node(None, None)

    def set_root(self, data, parent=None):
        self.root=node(parent, data)
        return self.root

    def get_root(self):
        return self.root

   def get_nodes(self):
        return self.nodes


def cal_height(Tree):
    h=[]
    if len(Tree.root.children)==0:
        return 1
    for child in Tree.root.children:
        t=tree()
        t.set_root(child.parent, child.data)
        height= 1+ cal_height(t)
        h.append(height)
    return max(h)




l1=input()
l=input().split()
Tree=tree()
for n, i in enumerate(l):
    if n==-1:
        Tree.nodes.append(Tree.set_root(i))

    else:
        Tree.nodes.append(create_node(n, i))

for p in Tree.nodes:
    for c in Tree.nodes:
        if p.data==c.parent:
            p.children.append(c)

for j in Tree.nodes:
    print(j.children)

我一直在尝试创建一棵树并计算分配的高度。这是我到目前为止写的代码，但显然，没有一个孩子的节点附加。

代码的输入以 - 例如 - 4 -1 4 1 1

带有-1的索引值是根节点，而其他输入表示相应的值是其父节点。

Answer 1

您的代码中存在这些问题：

• 儿童被定义为类属性，因此每当您查看j.children时，它始终是 所有节点共享的列表。您的班级不应具有任何类属性。对于数据和parent属性，您的也将它们定义为实例属性，因此不会出现问题。修复如下：

   类节点：
      ＃删除类属性
  
      def __init __（自我，父，数据）：
          self.data =数据
          self.parent = parent
          self.Children = []＃添加
   

• 条件p.data == c.parent永远不正确，因为它将字符串与数字进行比较。为了避免这种情况，请首先将输入列表转换为程序开始时的数字列表：

    l = list（map（int，input（）。split（）））
   

• 枚举将以 first the Index返回元组，而< em>然后值。您以相反的方式拆开了元组，因此永远无法正确建造树。更改：

    n，i在枚举（l）中：
   

  to：

    i，n in Enumerate（l）中的n：
   

• 叶节点的高度应为0，因为高度的形式定义是从根到叶子的最长路径的长度。路径的长度在边缘的数量中表示。由于只有一个节点的树中没有边缘，因此该节点的高度应为0。

  so：

   如果len（tree.root.children）== 0：
      返回0＃不是1
   

• cal_height使用此语句设置新的根部时会出错：

    t.set_root（child.parent，child.data）
   

  在这里，您可以制作一个没有孩子的节点！因此，即使儿童有孩子，也不会考虑他们。递归调用cal_height现在不会带来任何有用的东西：它将始终返回1。

• cal_height不需要创建新的树和节点实例。您已经有了树，此功能不需要更改它。它应该是只读操作。

  需要对此功能进行全面审查。我提出了这一点：

    def cal_height（tree）：
  
      DEF高度（节点）：
          如果不是节点：
              返回-1
          返回1 + max（MAP（高度，Node.Children），默认值= -1）
  
      返回高度（树根）
   

随着这些更改，它将起作用。

没有树，

您实际上根本不需要创建树或节点。这可以通过仅列出每个节点的 的列表来完成。如果在每个节点（索引）中，您请按照父录制为止，直到遇到-1，那么您确实走到 up 并知道您启动的原始节点的深度。通过在途中注册所有节点的深度，您可以避免一遍又一遍地旅行相同的子路。深度最大的节点的深度等于树的高度。

扰流板解决方案：

def get_height（父母）：
深度= [-1] * len（父母）

def get_depth（i）：
如果i == -1：
返回-1
如果深度[i] == -1：
深度[i] = 1 + get_depth（父母[i]）
返回深度[i]

因为我在范围（len（父母））：
get_depth（i）
返回最大（深度）

n =输入（）
父母= list（MAP（int，input（）。split（）））
高度= get_height（父母）
打印（高度）