Python - k-ary tree list-representation pre- and postorder t

Question

我正在为一棵树创建一个python类，其中每个节点都有n个子节点(但每个子节点只有一个节点(。我需要实现两种方法，预购和后购。我被困在预订中。

这是我到目前为止所拥有的：

class KTree:
  def __init__(self, n, lst = []):
    self._tree = lst
    self._n = n
  def children(self, i):
    tree = self._tree
    n = self._n
    result = []
    for k in range(n*i+1, n*i+n+1):
        if k<len(tree):
            result.append(tree[k])
        else:
            pass
    return result
  def child_indices(self, i): 
    #returns list of the indices of the children of i
    tree=self._tree
    n = self._n
    result=[]
    for k in range(n*i+1, n*i+n+1):
        if k<len(tree):
            result.append(k)
    return result
  def parent(self, i):
    tree = self._tree
    n = self._n
    result = (i-1)//n
    return tree[result]
  def pre_order(self):
    result=[]
    stack = []
    stack.append(0)
    k=0
    while k<len(stack):
        result.append(self._tree[stack[k]])
        for index in self.child_indices(k):
            stack.append(index)
        k+=1
    return result

对于树[20, 2, 123, 1, 5, 4, 438](如下图所示，我认为预购的输出应该是[20, 2, 1, 5, 123, 4, 438]。我当前的代码正在输出[20, 2, 123, 1, 5, 40, 438]。

     20
   /    
  2     123
 /     / 
1   5  4  438

Answer 1

你可以使用递归。为了实现这一点，您可以为函数定义一个参数：从哪里开始生成预购列表的索引。

然后代码如下所示：

def pre_order(self, k = 0):
    result = [self._tree[k]]
    for index in self.child_indices(k):
        result.extend(self.pre_order(index))
    return result

它的后序

变体看起来非常相似，但只有在添加子节点的后序列表后才能添加给定节点：

def post_order(self, k = 0):
    result = []
    for index in self.child_indices(k):
        result.extend(self.post_order(index))
    return result + [self._tree[k]]

Answer 2

预序递归实现为

检查当前节点是否为空/空。显示根节点(或当前节点(的数据部分。通过递归调用预购函数遍历左侧子树。通过递归调用预购函数遍历右侧子树。

这是来自维克百科。