将树转换为 S 表达式

Question

我已经实现了两个 classes 来表示 Python 中的一棵树。特别是，我使用它们的方法创建了树 class 和节点 class。每个节点都有一个关联的标签。我怎样才能（通过合适的库或算法）将这棵树转换为 S 表达式（http://web.cs.ucla.edu/~rosen/161/notes/listtree.html）？

这是我的代码：

class Node(object):
""" Node of a Tree """

def __init__(self, label='root', children=None, parent=None):
    """
    Constructor

    Parameters
    ----------
    label : string, optional
        Label of the node to create. The default is 'root'.
    children : list, optional
        Children of the node to create. The default is None.
    parent : Node, optional
        Parent of the node to create. The default is None.

    Returns
    -------
    None.

    """
    self.label = label
    self.parent = parent
    self.children = []
    if children is not None:
        for child in children:
            self.add_child(child)
            
def getLabel(self):
    """ Return the label of the node """
    return self.label

def setLabel(self, label):
    """ Set a node label """
    self.label = label

def getParent(self):
    """ Return the parent of the node """
    return self.parent

def setParent(self, parent):
    """
    Set the parent of the node

    Parameters
    ----------
    parent : Node
        Parent node to be set.

    Returns
    -------
    None.

    """
    self.parent = parent

def getChildren(self):
    """ Return the children's Array of a node"""
    return self.children

def setChildren(self, children):
    """
    Set the children of the node 

    Parameters
    ----------
    children : list
        New children's list of the node.

    Returns
    -------
    None.

    """
    self.children = children



def addChild(self, node):
    """ Add a child at node """
    node.parent = self
    assert isinstance(node, Node)
    self.children.append(node)

class Tree(object):

""" A Generic Tree """

def __init__(self):
   """ Constructor """
   self.root=None
   self.height=0
   self.nodes=[]
   self.edges=[]

def insert(self, node, parent):   
    """
    Insert a node into tree

    Parameters
    ----------
    node : Node
        Node to insert.
    parent : Node
        Parent of the node to insert.

    Returns
    -------
    None.

    """
    
    if parent is not None:
        parent.addChild(node)
        self.edges.append((parent, node))
    else:
        if self.root is None:
            self.root=node
    self.nodes.append(node)
    
def getRoot(self):
    """ Return the root of tree"""
    return self.root

def setRoot(self, root):
    """
    Set the root of the tree

    Parameters
    ----------
    root : Node
        Root of the tree to be set.

    Returns
    -------
    None.

    """
    self.root = root

def getNodes(self):
    """ Return the nodes of tree"""
    return self.nodes

def getEdges(self):
    """ Return the edges of tree"""
    return self.edges

def setEdges(self, edges):
    """
    Set the edges of the tree

    Parameters
    ----------
    edges : list
        List of pairs of nodes representing the new edges of the tree.

    Returns
    -------
    None.

    """
    self.edges = edges
           
def printAllNodes(self):
    """ Outputs all tree node labels """
    print("Nodes: ")
    for n in self.nodes:
        print(n.getLabel())

def preorder(self, root):
    """
    Visit the tree in pre-order and return the respective list of nodes

    Parameters
    ----------
    root : Node
        The root of the tree.

    Returns
    -------
    list
        The list of tree nodes visited in pre-order.

    """
    if not root:
        return []
    result = []
    if root.children:
        for node in root.children:
            result.extend(self.preorder(node))
    return [root] + result

Answer 1

节点的表示是一个元组，由该节点的标签和其所有子节点的表示组成。

class Node:
   ..
   def representation(self):
      label = self.getLabel()
      children = [child.representation() for child in self.getChildren()]
      # return a tuple of the label and the children
      return (label, *children)

将树转换为 S 表达式

Convert a tree to the S-expressions

python

tree

data-structures