Pythonの再帰的完全バイナリツリー - ツリーが歪んでいる

Question

完全なバイナリツリーの再帰的な実装です（リストからPythonのバイナリ検索ツリーではありません。 。私はそれがキューで行うことができますが、私は再帰的な実装を必要と認識していますスキューツリーを生成し、書かれている

をここではコードです：。

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 = < 2 0、それが挿入されている...
...（あなたは、アルゴリズムは、あなたが期待していない何点に到達するまで、以下のことを行います。 ）

ヒント： #leftと#right ない何彼らが必要行っています。ルートの右のサブツリーに左の子として何かを挿入すると、#leftがインクリメントされます。ツリー全体に対して一度だけでなく、各ノードのこれらの値を維持してください。