binary-tree - 二分木でループを見つける

Question

二分木でループを見つける方法は? 訪問したノードを訪問済みとしてマークするか、アドレスハッシュを行う以外の解決策を探しています。何か案は？

Answer 1

二分木があるが、それを信頼せず、それがグラフであると考えているとします。一般的なケースでは、訪問したノードを記憶する必要があります。グラフから最小スパニング ツリーを構築するのは、いくぶん同じアルゴリズムであり、これは、空間と時間の複雑さが問題になることを意味します。

もう 1 つのアプローチは、ツリーに保存するデータを考慮することです。比較できるように、ハッシュの数があると考えてください。

疑似コードは、この条件をテストします。

1. すべてのノードには、最大 2 つの子と 1 つの親 (最大 3 つの接続) が必要です。3 つ以上の接続 => 二分木ではありません。
2. 親は子であってはなりません。

3. ノードに 2 つの子がある場合、左側の子は親よりも値が小さく、右側の子は値が大きくなります。したがって、これを考慮すると、リーフまたは内部ノードが上位レベル (親の親など) に子としていくつかのノードを持っている場合、値に基づいてループを決定できます。子が右ノードである場合、その値は親よりも大きくなければなりませんが、その子がループを形成する場合、それは親の左部分または右部分からのものであることを意味します。

   3.a. したがって、左部分からのものである場合、その値は兄弟よりも小さくなります。だから=>二分木ではありません。アイデアは、他の部分でも多少同じです。

テストはさておき、テストしたいツリーはどのような形ですか? すべてのノードには、その親へのポインタがあることに注意してください。this ポインターは、1 つの親を指します。したがって、ツリーの形式に応じて、これを利用できます。

Answer 2

すでに述べたように: ツリーには (定義により) サイクル (ループ) は含まれません。

有向グラフにサイクル (ツリーに既に追加されているノードへの参照) が含まれているかどうかをテストするには、ツリーを反復処理し、各ノードを訪問済みリスト (または、必要に応じてそのハッシュ) に追加し、新しいノードをそれぞれチェックします。それはリストにあります。グラフでサイクルを検出するためのアルゴリズムは、Google 検索ですぐに見つかります。