Python中的递归完成二叉树 - 树偏斜

这里是一个完整的二叉树的递归实现（不是Python中的二叉搜索树，需要帮助构建平衡树的逻辑，逻辑i采写产生歪斜的树我知道它可以用队列来完成，但我需要一个递归实现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)

来源

2017-01-31 May13ank

想想会发生什么，当你的算法运行：

1成为根。（#left = 0，#right = 0）。
2成为根的左侧孩子（#left = 1，#right = 0）。
3成为根的右边的孩子（#left = 1，#right = 1）。
4触发else因为#left - #right = 0 < 2，将其插入...
...（这样做，直到你到了一个算法不你所期望的一个点。）

提示： #left和#right 不在做什么，他们应该。如果您在根的右侧子树中插入某个左侧子项，则#left会递增。尝试为每个节点维护这些值，而不是整个树的一次。

来源

2017-01-31 09:37:45 Hannes

提取根。从剩余列表的左半部分中构建左侧子树，并从右侧半部分中取出右侧子树。如果节点数量不完全正确，则需要不均匀分配。 –

Python中的递归完成二叉树 - 树偏斜

回答

相关问题