二分木内のノードがその親への参照を保持するのは「伝統的」(または「倫理的」)ですか?
木は有向グラフであり、PARENT-->CHILD リンクが定義されているという事実は、CHILD --->PARENT も定義されていることを意味しないはずです。言い換えれば、親への参照を保持することで、何らかの方法でツリーのセマンティックを壊します。
しかし、私は人々がどう思うか知りたいですか？
ツリー内の 2 つの特定のノードの最小共通親を見つけるという問題が発生したため、質問しました。各ノードがその親への参照を持っている場合、問題は非常に簡単に解決できますが、それは不正行為のように感じます!
ありがとう
二分木をどのように実装するかは、ニーズによって異なります。
アプリケーションで葉から幹へのツリー トラバーサルが必要な場合、そのための最善の方法は、親ノードへの参照を実装することです。
他のロジックで回避策を試みるよりも、データ構造をニーズに合わせたほうがよいことがわかりました。結局のところ、なぜ木は有向グラフでなければならないのでしょうか? それを有向にすることは、リストとその特定の実装を一重または二重にリンクされたリストと同様に、特定の実装です。
Software Engineering Stack Exchangeからの相互投稿。
ウィキペディアの定義には、「たとえば、ツリーを全体として見ると、特定のノードの「親ノード」について話すことができますが、一般に、データ構造として、特定のノードにはその子のリストのみが含まれますが、親への参照が含まれていない場合 (存在する場合)。 "