これは私が何度か遭遇した問題であり、最も効率的なロジックを使用したとは確信が持てませんでした。
たとえば、2 つのツリーがあるとします。1 つはフォルダー構造で、もう 1 つはそのフォルダー構造のメモリ内「モデル」です。2 つのツリーを比較し、一方のツリーに存在し、もう一方のツリーには存在しないノードのリストを生成し、その逆も生成します。
これを処理するための受け入れられたアルゴリズムはありますか?
ベストアンサー1
基本的には、事前順序のトラバーサルを実行したいだけのように思えます。ノードを「訪問する」とは、あるバージョンにはあるが他のバージョンにはない子ノードをチェックすることを意味します。
より正確には、ルートから始めます。各ノードで、ノードの 2 つのバージョンのそれぞれからアイテムのセットを取得します。2 つのセットの対称差には、一方のセットのアイテムが含まれますが、もう一方のセットのアイテムは含まれません。それらを印刷/出力します。共通部分には、両方に共通するアイテムが含まれます。共通部分にある各アイテム (1 つのツリーから欠落しているアイテムをこれ以上調べることはないと思います) について、そのノードで "visit" を再帰的に呼び出して、その内容を確認します。これは O(n) 操作で、再帰オーバーヘッドが少しあります。