25

これは私が何度か遭遇した問題であり、最も効率的なロジックを使用したとは確信していません。

例として、2 つのツリーがあるとします。1 つはフォルダー構造で、もう 1 つはそのフォルダー構造のメモリ内の「モデル」です。2 つのツリーを比較して、一方のツリーに存在し、他方のツリーには存在しないノードのリストを作成したいと考えています。逆もまた同様です。

これを処理するための受け入れられたアルゴリズムはありますか?

4

5 に答える 5

13

基本的に、事前注文のトラバーサルを行いたいだけのようです。ノードを「訪問」するということは、一方のバージョンにあるが他方のバージョンにない子をチェックすることを意味します。

より正確には、ルートから開始します。各ノードで、ノードの 2 つのバージョンのそれぞれでアイテムのセットを取得します。2 つのセットの対称的な差異には、一方のアイテムが含まれますが、他方のアイテムは含まれません。それらを印刷/出力します。交差点には、両方に共通する項目が含まれています。交差点の各アイテム (1 つのツリーから欠落しているアイテムを詳しく調べることはないと思います) について、そのノードで「visit」を再帰的に呼び出してその内容を確認します。これは O(n) 操作であり、再帰オーバーヘッドが少しあります。

于 2013-10-11T05:25:14.613 に答える
3 
public boolean compareTrees(TreeNode root1, TreeNode root2) {
  if ((root1 == null && root2 != null) || 
      (root1 != null && root2 == null)) {
    return false;
  }

  if (root1 == null && root2 == null) {
    return true;
  }

  if (root1.data != root2.data) {
    return false;
  }

  return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right);
}
于 2015-06-25T22:02:42.797 に答える
2

Python での簡単なサンプル コード。

class Node(object):
  def __init__(self, val):
    self.val = val
    self.child = {}

  def get_left(self):
    #if left is not in the child dictionary that means the element does not have a left child
    if 'left' in self.child:
      return self.child['left']
    else:
      return None

  def get_right(self):
    #if right is not in the child dictionary that means the element does not have a rigth child
    if 'right' in self.child:
      return self.child['right']
    else:
      return None


def traverse_tree(a):
  if a is not None:
    print 'current_node : %s' % a.val
    if 'left' in a.child:
      traverse_tree(a.child['left'])

    if 'right' in a.child:
      traverse_tree(a.child['right'])



def compare_tree(a, b):
  if (a is not None and b is None) or (a is None and b is not None):
    return 0
  elif a is not None and b is not None:
    print a.val, b.val
    #print 'currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s' % (a.val, b.val, a.child['left'].val, b.child['left'].val, a.child['right'].val, b.child['right'].val)
    if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()):
      return 1
    else:
      return 0
  else:
    return 1

#Example
a = Node(1)
b = Node(0)
a.child['left'] = Node(2)
a.child['right'] = Node(3)
a.child['left'].child['left'] = Node(4)
a.child['left'].child['right'] = Node(5)
a.child['right'].child['left'] = Node(6)
a.child['right'].child['right'] = Node(7)
b.child['left'] = Node(2)
b.child['right'] = Node(3)
b.child['left'].child['left'] = Node(4)
#b.child['left'].child['right'] = Node(5)
b.child['right'].child['left'] = Node(6)
b.child['right'].child['right'] = Node(7)
if compare_tree(a, b):
  print 'trees are equal'
else:
  print 'trees are unequal'
#DFS traversal
traverse_tree(a)

実行できる例も貼り付けます。

于 2015-08-28T06:04:15.117 に答える
1

AVL ツリーのようなソート ツリーを使用すると、ツリーを効率的に順序どおりにトラバースすることもできます。これにより、パスが「低」から「高」にソートされた順序で返されます。次に、ツリー アルゴリズムで使用するのと同じ比較方法を使用して、ディレクトリ配列を並べ替えることができます (例: クイック ソートを使用)。

次に、2 つを並べて比較し、ツリーを順番にトラバースして次の項目に進み、並べ替えられたディレクトリ配列内の次の項目をチェックします。

これは実際にはより効率的であるはずですが、ベンチマークだけがわかります。

于 2015-08-29T10:19:55.087 に答える