给定深度的Swift二叉树列表节点

嗨我正在写一个二叉树的快速算法。我的目标是在特定深度，以创建节点的列表像给定深度的Swift二叉树列表节点

func listNodeAt(_n: Int) --> [T] { 

}

这里是我的树类

public class BinaryTreeNode<T:Comparable> { 

    //Value and children vars 
    public var value:T 
    public var leftChild:BinaryTreeNode? 
    public var rightChild:BinaryTreeNode? 
    public weak var parent:BinaryTreeNode? 

    //Initialization 
    public convenience init(value: T) { 
     self.init(value: value, left: nil, right: nil, parent:nil) 
    } 

    public init(value:T, left:BinaryTreeNode?, right:BinaryTreeNode?, parent:BinaryTreeNode?) { 
     self.value = value 
     self.leftChild = left 
     self.rightChild = right 
     self.parent = parent 
    } 
}

我有建立一个辅助函数来计算节点的深度

//Depth 
    public func depth() -> Int { 
     guard var node = parent else { 
      return 0 
     } 

     var depth = 1 
     while let parent = node.parent { 
      depth = depth + 1 
      node = parent 
     } 

     return depth 
    }

我们如何才能实现愿望功能？任何建议都非常感谢。谢谢！

来源

2017-02-16 Lê Khánh Vinh

因此，使用相同的算法来查找树的深度。在while循环中使用数组总是在数组的开头插入父项。 –

谢谢你能给一点细节？我的深度func仅用于计算特定注释的深度 –

您是否想要将所有可能的节点列表列入一个阵列或多个阵列，并且可以实现此深度。 –

func listNodeAt(_ n: Int) -> [T] { 
    return getElementsAt(n, node: self) 
} 

private func getElementsAt(_ n: Int, node: BinaryTreeNode<T>, traversingDepth: Int = 0) -> [T] { 
     var array = Array<T>() 
     if traversingDepth < n { 
      if let left = node.leftChild { 
       array = array + getElementsAt(n, node: left, traversingDepth: traversingDepth + 1) 
      } 
      if let right = node.rightChild { 
       array = array + getElementsAt(n, node: right, traversingDepth: traversingDepth + 1) 
      } 
     } else if traversingDepth == n { 
      array.append(node.value) 
     } 
     return array 
    }

这是解决方案之一。假设这里自我是根节点。

来源

2017-02-16 05:21:21

非常感谢。相当不错的解决方案。 1个问题应该只在根节点上调用函数吗？（即：self必须是根节点）。我们应该检查node.parent ==零 –

是的，理想情况下，我没有添加像上面这样的额外检查，因为您需要计算基于根节点的深度。 –

它可以在你发送的任何节点上工作。 –

给定深度的Swift二叉树列表节点

回答

相关问题