ホームページ バックエンド開発 C#.Net チュートリアル C++は2つの二分探索ツリーが同じかどうかをチェックします

C++は2つの二分探索ツリーが同じかどうかをチェックします

Jan 25, 2019 pm 01:55 PM

2 つの二分探索ツリーのルート ノードが与えられたとします。 2 つの二分探索ツリーが同一の場合は 1 を出力し、そうでない場合は 0 を出力します。構造的に同一であり、同じ値のノードを持つ 2 つのツリーは同一です。

C++は2つの二分探索ツリーが同じかどうかをチェックします

#上の画像では、tree1 とtree2 は両方とも同じです。

2 つのツリーが同じかどうかを判断するには、両方のツリーを同時に走査する必要があり、走査中にデータとツリーの子ノードを比較する必要があります。

次は、2 つの BST が同じかどうかを確認するための段階的なアルゴリズムです:

1. 両方のツリーが空の場合は、1 を返します。

2. それ以外の場合、両方のツリーが空でない場合は

# - ルート ノードのデータを確認します (tree1-> data ==tree2-> data)

- 左側のサブツリーを再帰的にチェックします。つまり、sameTree(tree1-> left_subtree,tree2-> left_subtree) を呼び出します。

-右側のサブツリーを再帰的にチェックします。つまり、sameTree(tree1-> right_subtree を呼び出します) 、tree2-> right_subtree)

- 上記の 3 つの手順で返された値が true の場合、1 を返します。

3. それ以外の場合は 0 を返します (1 つは空で、もう 1 つは空ではありません)。

上記のメソッドの実装は次のとおりです:

// c++程序检查两个bst是否相同
  
#include <iostream> 
using namespace std; 
  
// BST节点
struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
// 创建新节点的实用程序函数 
struct Node* newNode(int data) 
{ 
    struct Node* node = (struct Node*) 
        malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return node; 
} 
  
//函数执行顺序遍历
void inorder(Node* root) 
{ 
    if (root == NULL) 
        return; 
  
    inorder(root->left); 
  
    cout << root->data << " "; 
  
    inorder(root->right); 
} 
  
// 函数检查两个bst是否相同
int isIdentical(Node* root1, Node* root2) 
{ 
    // 检查这两棵树是否都是空的 
    if (root1 == NULL && root2 == NULL) 
        return 1; 
    // 如果树中的任意一个为非空,另一个为空,则返回false
    else if (root1 != NULL && root2 == NULL) 
        return 0; 
    else if (root1 == NULL && root2 != NULL) 
        return 0; 
    else { 
    // 检查两个树的当前数据是否相等,并递归地检查左子树和右子树
        if (root1->data == root2->data && isIdentical(root1->left, root2->left) 
            && isIdentical(root1->right, root2->right)) 
            return 1; 
        else
            return 0; 
    } 
} 
  
// 驱动代码
int main() 
{ 
    struct Node* root1 = newNode(5); 
    struct Node* root2 = newNode(5); 
    root1->left = newNode(3); 
    root1->right = newNode(8); 
    root1->left->left = newNode(2); 
    root1->left->right = newNode(4); 
  
    root2->left = newNode(3); 
    root2->right = newNode(8); 
    root2->left->left = newNode(2); 
    root2->left->right = newNode(4); 
  
    if (isIdentical(root1, root2)) 
        cout << "Both BSTs are identical"; 
    else
        cout << "BSTs are not identical"; 
  
    return 0; 
}
ログイン後にコピー
出力:

Both BSTs are identical
ログイン後にコピー

この記事は、2 つの二分探索が正しいかどうかを確認する方法についてです。木々も同じです はじめに、困っている友達のお役に立てれば幸いです!

以上がC++は2つの二分探索ツリーが同じかどうかをチェックしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

C言語でさまざまなシンボルを使用する方法 C言語でさまざまなシンボルを使用する方法 Apr 03, 2025 pm 04:48 PM

c言語のシンボルの使用方法は、算術、割り当て、条件、ロジック、ビット演算子などをカバーします。算術演算子は基本的な数学的操作に使用されます。割り当てと追加、下位、乗算、除算の割り当てには、条件操作に使用されます。ポインター、ファイル終了マーカー、および非数値値。

マルチスレッドと非同期C#の違い マルチスレッドと非同期C#の違い Apr 03, 2025 pm 02:57 PM

マルチスレッドと非同期の違いは、マルチスレッドが複数のスレッドを同時に実行し、現在のスレッドをブロックせずに非同期に操作を実行することです。マルチスレッドは計算集約型タスクに使用されますが、非同期はユーザーインタラクションに使用されます。マルチスレッドの利点は、コンピューティングのパフォーマンスを改善することですが、非同期の利点はUIスレッドをブロックしないことです。マルチスレッドまたは非同期を選択することは、タスクの性質に依存します。計算集約型タスクマルチスレッド、外部リソースと相互作用し、UIの応答性を非同期に使用する必要があるタスクを使用します。

C言語でchar配列の使用方法 C言語でchar配列の使用方法 Apr 03, 2025 pm 03:24 PM

Char Arrayは文字シーケンスをC言語で保存し、char array_name [size]として宣言されます。アクセス要素はサブスクリプト演算子に渡され、要素は文字列のエンドポイントを表すnullターミネーター「\ 0」で終了します。 C言語は、strlen()、strcpy()、strcat()、strcmp()など、さまざまな文字列操作関数を提供します。

C文字列におけるcharの役割は何ですか C文字列におけるcharの役割は何ですか Apr 03, 2025 pm 03:15 PM

Cでは、文字列でCharタイプが使用されます。1。単一の文字を保存します。 2。配列を使用して文字列を表し、ヌルターミネーターで終了します。 3。文字列操作関数を介して動作します。 4.キーボードから文字列を読み取りまたは出力します。

C言語で特殊文字を処理する方法 C言語で特殊文字を処理する方法 Apr 03, 2025 pm 03:18 PM

C言語では、以下などのエスケープシーケンスを通じて特殊文字が処理されます。\ nはラインブレークを表します。 \ tはタブ文字を意味します。 ESACEシーケンスまたは文字定数を使用して、Char C = '\ n'などの特殊文字を表します。バックスラッシュは2回逃げる必要があることに注意してください。さまざまなプラットフォームとコンパイラが異なるエスケープシーケンスを持っている場合があります。ドキュメントを参照してください。

C言語でCharを変換する方法 C言語でCharを変換する方法 Apr 03, 2025 pm 03:21 PM

C言語では、charタイプの変換は、キャスト:キャスト文字を使用することにより、別のタイプに直接変換できます。自動タイプ変換:あるタイプのデータが別のタイプの値に対応できる場合、コンパイラは自動的に変換します。

C言語合計の機能は何ですか? C言語合計の機能は何ですか? Apr 03, 2025 pm 02:21 PM

C言語に組み込みの合計機能はないため、自分で書く必要があります。合計は、配列を通過して要素を蓄積することで達成できます。ループバージョン:合計は、ループとアレイの長さを使用して計算されます。ポインターバージョン:ポインターを使用してアレイ要素を指し示し、効率的な合計が自己概要ポインターを通じて達成されます。アレイバージョンを動的に割り当てます:[アレイ]を動的に割り当ててメモリを自分で管理し、メモリの漏れを防ぐために割り当てられたメモリが解放されます。

C言語のcharとwchar_tの違い C言語のcharとwchar_tの違い Apr 03, 2025 pm 03:09 PM

C言語では、charとwchar_tの主な違いは文字エンコードです。CharはASCIIを使用するか、ASCIIを拡張し、WCHAR_TはUnicodeを使用します。 Charは1〜2バイトを占め、WCHAR_Tは2〜4バイトを占有します。 charは英語のテキストに適しており、wchar_tは多言語テキストに適しています。 CHARは広くサポートされており、WCHAR_TはコンパイラとオペレーティングシステムがUnicodeをサポートするかどうかに依存します。 CHARの文字範囲は限られており、WCHAR_Tの文字範囲が大きく、特別な機能が算術演算に使用されます。

See all articles