Python 깊이 트리 수정

Question

깊이가 고정 된 트리 구조를 구현하고 싶습니다. 즉, 리프 노드에 자식을 추가 할 때 전체 트리 구조가 "위로 이동"해야합니다. 이것은 또한 여러 뿌리가 동시에 존재할 수 있음을 의미합니다. 다음 예제를 참조하십시오 : 이 예에서는 녹색 노드가 반복 1에 추가되고, 맨 위 노드 (회색)가 삭제되고 두 개의 파란색 노드가 K = 0 및 반복 1 루트 노드가됩니다.

어떻게 구현하나요?

Answer 1

각 노드를 상위 노드에 대한 참조와 함께 저장하십시오. 자식 노드로 노드를 추가 할 때 추가되는 노드에서 부모 노드까지 걸어 가서 모든 자식 노드에서 부모 참조를 None으로 설정 한 후 세 번째 노드를 삭제하십시오. 그런 다음 삭제 된 노드의 하위를 트리 목록에 추가하십시오.

class Node(object): 

    depth = 4 

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


def create_node(trees, parent, contents): 
    """Adds a leaf to a specified node in the set of trees. 

    Note that it has to have access to the container that holds all of the trees so 
    that it can delete the appropriate parent node and add its children as independent 
    trees. Passing it in seems a little ugly. The container of trees could be a class 
    with this as a method or you could use a global list. Or something completely 
    different. The important thing is that if you don't delete every reference to the 
    old root, you'll leak memory. 
    """ 
    parent.children.append(Node(parent, contents)) 

    i = 0: 
    L = Node.depth - 1 
    while i < L: 
     parent = parent.parent 
     if not parent: 
      break 
     i += 1 
    else: 
     for node in parent.children: 
      node.parent = None 
     trees.extend(parent.children) 
     i = trees.find(parent) 
     del trees[i]