2017-02-16 10 views
0

こんにちは、私はバイナリツリーのための迅速なアルゴリズムを書いています。私の目標は、特定の深さでのノードリストを作成するために、ここでスウィフトバイナリツリー指定された深さのノードのリスト

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 
    } 

私たちはどのように欲求の機能を果たすことができますか?どんな提案も非常に感謝しています。ありがとう!

+0

したがって、ツリーの深さを見つけるのと同じアルゴリズムを使用します。 whileループの配列を使用すると、常に配列の先頭に親を挿入します。 –

+0

もう少し詳細を教えていただけますか?私の深さ関数は特定の音符の深さを計算することのみです –

+0

可能なすべてのノードのリストを1つの配列にまとめるか、この深さが実現できる複数の配列にリストしますか? –

答えて

2
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 
    } 

これは解決策の1つです。ここでは、自己がルートノードであると仮定します。

+0

ありがとうございます。かなり良い解決策。 1つの質問は、ルートノード上でのみ呼び出されるべきですか? (つまり、自己はルートノードでなければなりません)。私たちはnode.parent == nilを調べるべきです –

+0

ええ、理想的には、上記のような追加のチェックを追加しませんでした。 –

+0

あなたが送るどのノードでも動作します。 –

関連する問題