파이썬의 재귀 완전한 이진 트리 - 트리가 비뚤어 짐

Question

다음은 완전한 이진 트리의 재귀 구현입니다 (파이썬에서 이진 검색 트리가 아닙니다. 목록에서 균형 잡힌 트리를 작성하는 데 도움이 필요합니다. 논리 i 생성 작성한 왜곡 된 나무 나는 그것이 큐와 함께 할 수 있지만 재귀 구현을 필요로 알고 여기

코드입니다 :..

class Node: 
    """A simple Binary Node to be used in a Tree""" 

    def __init__(self, value=-1, leftNode=None, rightNode=None): 
     self.value = value 
     self.leftNode = leftNode 
     self.rightNode = rightNode 

class BinaryTree: 
def __init__(self, root=None): 
    self.root = root 
    self.noOfLeftNodes = 0 
    self.noOfRightNodes = 0 

def addNode(self, root, node): 
    if self.root is None: 
     self.root = node 
     return 
    if root.leftNode is None: 
     root.leftNode = node 
     self.noOfLeftNodes += 1 
     return 
    elif root.rightNode is None: 
     root.rightNode = node 
     self.noOfRightNodes += 1 
     return 

    else: 
     if self.noOfLeftNodes - self.noOfRightNodes < 2: 
      self.addNode(root.leftNode, node) 
     else: 
      self.addNode(root.rightNode, node) 

def preorder(self, root): 
    if root is None: 
     return 
    print(root.value) 
    self.preorder(root.leftNode) 
    self.preorder(root.rightNode) 

#Test stub 
    bt = BinaryTree() 
    nodes = [1, 2, 3, 4, 5, 6, 7] 
    for i in range(len(nodes)): 
     bt.addNode(bt.root, Node(nodes[i])) 
    print('---Binary Tee---') 
    bt.preorder(bt.root) 

Answer 1

일어나는 일에 대해 생각 할 때 알고리즘 실행 :

• 1이 루트가됩니다. (#left = 0, # right = 0).
• 2가 루트의 왼쪽 하위 항목이됩니다 (#left = 1, # right = 0).
• 3이 루트의 오른쪽 하위 항목이됩니다 (#left = 1, # right = 1).
• 4 트리거 else 때문에 #left - #right = <이 0이 삽입 ...
(당신이 알고리즘은 예상하지 않는다 어떤 점에 도달 할 때까지, 그 작업을 수행합니다.)

힌트 : #left 및 #right 은 그들이 무엇을해야 일을하지. 루트의 오른쪽 하위 트리에 왼쪽 자식으로 무언가를 삽입하면 #left가 증가합니다. 전체 트리에 대해 한 번만이 아니라 각 노드에 대해이 값을 유지하십시오.