Python

Question

我正在为一棵树创建一个 python class，其中每个节点都有 n 个子节点（但每个子节点只有一个节点）。我需要实现两种方法，预购和 post-order。我被困在预购中。

这是我目前拥有的：

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]（如下图，我认为preorder的输出应该是[20, 2, 1, 5, 123, 4, 438]。我现在的代码是输出[20, 2, 123, 1, 5, 40, 438]。

     20
   /    \
  2     123
 / \    / \
1   5  4  438

Answer 1

预序递归实现为

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

这是来自维基百科。

Answer 2

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

那么代码如下所示：

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

这个 post 顺序变体看起来非常相似，但是您只在 添加给定节点 之后添加了 children 的 [=21] =] 订单列表：

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]]

Python - k-ary tree list-representation前后序遍历

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

tree

traversal