説明する:
バイナリツリーの深さ:ツリーへのパスは、ルートノードからノード(ルートノードと葉のノードを含む)まで形成され、葉のノードを順番に通過します。最長の経路の長さは、木の深さです。
バイナリツリーの幅:バイナリツリーの各層には、一定数のノードがあります。レイヤー内のノードの数は、最大数のノードを持つノードの数は、バイナリツリーの幅と呼ばれます。
アイデア:再帰的実装。
1.各ノードはルートノードと見なすことができます
2。ルートノードの深さ(任意のノード)は、その左または右のサブツリー深さの最大+1に等しくなります
3.ルートノードからトラバースを開始します。リーフノードに移動する場合、深さは0です
//バイナリツリーの深さpublic static int dept(ノードルート){if(root == null){return 0; } int dl = depth(root.leftchild); int dr =深さ(root.rightchild); dl> drを返しますか? DL+1:DR+1; }2。バイナリツリーの幅
アイデア:レイヤーシーケンストラバーサル中にカウンターを追加して、各レイヤーのノードの数を記録する
1.各レイヤーがキューから外れている場合、次のレイヤーのノードの数は実際にはキューのサイズ()です。
2。各レイヤートラバーサルの端で、最大幅を現在のノードの数と比較し、最大値を記録します。
public static int width(node root){if(root == null)return 0; queue <node> q = new linkedlist <node>(); q.add(root); int width = 1; //最大幅int len = 1; //レイヤーの現在のノード数q.poll(); if(node.leftchild!= null){q.add(node.leftchild);} if(node.rightchild!= null){q.add(node.rightchild);}} len = q.size();幅:q.size();} return width;}要約します
上記は、バイナリツリーの深さと幅のJava言語の説明に関するものです。私はそれが誰にでも役立つことを願っています。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました!