ホームページ >バックエンド開発 >PHPチュートリアル >Tree_Graph はバイナリ ツリーのバランスをとるかどうかを決定します @CareerCup_PHP チュートリアル
Tree_Graph はバイナリ ツリーのバランスをとるかどうかを決定します @CareerCup_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 10:37:281299ブラウズ
二分木がバランスが取れているかどうかをチェックする関数を実装します。この質問の目的では、バランスの取れたツリーは、どのノードの 2 つのサブツリーの高さも 1 を超えて異なることがないようなツリーとして定義されます。
1) まず再帰的な木の高さ関数を作成し、サブツリーの高さの差が 1 より大きいかどうかを確認します
2) 最適化: 木の高さを見つける再帰関数にサブツリーの高さの差が 1 より大きいかどうかをチェックするロジックを組み込み、不均衡が発生した場合に適切なタイミングで戻ります。
この質問は、ツリーのバランスが取れているかどうかを尋ねることとは異なります (このツリーの任意の 2 つの葉ノードとルート ノードの間の距離の差が 1 以下であるかどうか)。
vcD4KPHA+PGJyPgo8L3A+CjxwPsjnyc/NvKOszqrGvbritv6y5sr3o6y1q7K7xr264qGjPC9wPgo8cD7F0LbP0ru/w8r3yse38ca9uuK/ydLUx/PK97XE1+6087jftsi6zdfu0KG4 37bI1q6y7srHt/G089PaMaGjPC9wPgo8cD7H88r3tcTX7tChuN+2yL/Jss6/vKO6aHR0cD ovL2Jsb2cuY3Nkbi5uZXQvZmlnaHRmb3J5b3VyZHJlYW0vYXJ0aWNsZS9kZXRhaWxzLzEy O DUxMjMxPC9wPgo8cD48YnI+CjwvcD4KPHA+we3Su9bWveK3qMrHv8nS1NPD1tDQ8rHpwP rH87XDyvfA77XEw7/Su7j20rbX07XEuN+2yKOsyLu687/JtcOhozwvcD4KPHA+ss6/vKO6 aHR0cDovL2hhd3N0ZWluLmNvbS9wb3N0cy80LjEuaHRtbDwvcD4KPHA+PGJyPgo8L3A+CjxwPs/Cw+bKx8XQts /Kx7fxxr264rb+subK97XEtPrC66O6PC9wPgo8cD48cHJlIGNsYX QUR ==="brush:java;">パッケージ Tree_Graph;
CtCILibrary.AssortedMethods をインポートします。
CtCILibrary.TreeNode をインポートします。
パブリック クラス S4_1 {
// ツリーが平衡二分木であるかどうかを再帰的に判断します
// 時間: O(N^2)
public static boolean isBalanced(TreeNode root) {
if (root == null) {
true を返します。
}
int heightDiff = getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff) > 1) { // アンバランス
false を返します。
} それ以外 {
return isBalanced(root.left) && isBalanced(root.right);
}
}
// 木の高さを再帰的に取得します
public static int getHeight(TreeNode root) {
if (root == null) {
0を返します。
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// ========================== 改善版 最適化版
//高さを計算する際にバランスが取れているかどうかを判定するロジックをcheckHeight関数に入れます。
// エッジがバランスしているかどうかを判断し、そうでない場合は直接 -1 を返します。
// 時間: O(N)、空間: O(H)、H: 木の高さ
public static boolean isBalanced2 (TreeNode ルート) {
if (checkHeight(root) == -1) {
false を返します。
} それ以外{
true を返します。
}
}
// バランスが取れているかを判断しながら高さを計算します
public static int checkHeight (TreeNode ルート) {
if (root == null) {
0を返します。
}
int leftHeight = checkHeight(root.left);
if (leftHeight == -1) {
-1 を返します。
}
int rightHeight = checkHeight(root.right);
if (rightHeight == -1) {
-1 を返します。
}
int heightDiff = leftHeight - rightHeight;
if (Math.abs(heightDiff) > 1) {
-1 を返します。
}
Math.max(leftHeight, rightHeight) + 1 を返します。
}
public static void main(String[] args) {
// バランスのとれたツリーを作成する
int[] 配列 = {1、2、3、4、5、6、7、8、9、10};
TreeNode ルート = TreeNode.createMinimalBST(array);
System.out.println("ルート? " + root.data);
System.out.println("バランスは取れていますか? " + isBalanced(root));
// 実際にはバランスが取れている可能性もありますが、その可能性は非常に低いです...
TreeNode のアンバランス = new TreeNode(10);
for (int i = 0; i
喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">
http://www.bkjia.com/PHPjc/735868.html
の 2 つのサブツリーの高さになるようなツリーとして定義されます。