从python中的二进制序列创建一个二叉树

我想从二进制序列如“100101” 二进制创建一棵树，然后我想这样创建树。（基本上1装置到正确的和0的手段去左边）从python中的二进制序列创建一个二叉树

       <Root node> 
            | 
            1 
           /
            0 
           /
           0 
           \ 
            1 
           /
           0 
           \ 
            1

所以我没有在这里是代码：其中值将是串序列（前值=“1001”）

def _inserto(root,value): 
    for i in value: 
     if root == None: 
      root = BSTNode(i) 
      current = root 
     elif i == "1": 
      if current.right is not None: 
       current.right = BSTNode(i) 
       current = current.right 
      else: 
       current.right = BSTNode(i) 
       current = current.right 
     elif i == "0": 
      if (current.left is not None): 
       current.left = BSTNode(i) 
       current = current.left 
      else: 
       current.left =BSTNode(i) 
       current = current.left 
    return root

现在的问题是，如果我想输入类似“01”的另一个序列，树看起来应该是这样

      <Root Node> 
           | 
           1 
          /
           0 
          /\ 
          0 1 
          \ 
           1 
          /
          0 
          \ 
           1

，但我真的很不好受，因为我的功能G希望覆盖老树。

来源

2012-07-22 Wobblester

这是什么部分，*确切*有问题吗？您也可以在python中保留对最后一个节点的外部引用。你知道python也有类和对象吗？ – Marcin 2012-07-22 20:46:54

“基本上1代表右移，0代表左移”Err ...从你的图表中看来，1代表左移。你的图是错的，还是我读错了？ – 2012-07-22 20:46:57

@MarkByers我在图表和'_insert'的代码之间分享你的“err ...” - 以1的初始根开始，接下来是0 <1，所以它向左，但是0不是<0 ，所以它应该是正确的（但显示为左边）...我希望OP能够澄清三个可能的结果中的哪一个是实际需要的。 – 2012-07-22 21:04:01

问题在于处理现有节点的代码。如果存在，代码将用新的BSTNode覆盖它，丢失它下面的所有现有节点。你需要的是这样的：

elif i == "1": 
     if current.right is None: 
      current.right = BSTNode(i) 
     current = current.right 
    elif i == "0": 
     if root.left is None: 
      current.left = BSTNode(i) 
     current = current.left

如果没有一个已经存在这将只分配一个节点，然后设置当前这个新的节点。

来源

2012-07-22 23:17:28

从python中的二进制序列创建一个二叉树

回答

相关问题