二分木 です 非線形データ構造 ここで、各ノードには最大 2 つの子があります。この記事では、バイナリ ツリーの基本、バイナリ ツリー上の操作、その実装、利点、欠点をすべて取り上げ、バイナリ ツリーに基づくすべての問題を解決するのに役立ちます。
目次
- バイナリーツリーとは何ですか?
- 二分木の表現
- 二分木の種類
- バイナリ ツリーの操作
- バイナリ ツリーでの補助操作
- バイナリツリーの実装
- 二分木演算の複雑さの分析
- バイナリーツリーの利点
- バイナリーツリーの欠点
- 二分木の応用
- バイナリーツリーに関するよくある質問
バイナリーツリーとは何ですか?
二分木とは、 ツリーデータ構造(非線形) 各ノードが持つことができるのは 子供はせいぜい2人 と呼ばれるもの 左の子 そしてその 右の子 。
バイナリ ツリーの最上位のノードは、 根 、最下位のノードは次のように呼ばれます。 葉 。バイナリ ツリーは、ルートが最上位、リーフが最下位の階層構造として視覚化できます。
二分木の表現
バイナリ ツリーの各ノードには 3 つの部分があります。
- データ
- 左の子へのポインタ
- 正しい子へのポインタ
以下は、さまざまな言語でのバイナリ ツリーのノードの表現です。
文字列フォーマッタC++
// Use any below method to implement Nodes of tree // Method 1: Using 'struct' to make // user-define data type struct node { int data; struct node* left; struct node* right; }; // Method 2: Using 'class' to make // user-define data type class Node { public: int data; Node* left; Node* right; };> C // Structure of each node of the tree struct node { int data; struct node* left; struct node* right; };> ジャワ // Class containing left and right child // of current node and key value class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } }> パイソン # A Python class that represents # an individual node in a Binary Tree class Node: def __init__(self, key): self.left = None self.right = None self.val = key>
C# // Class containing left and right child // of current node and key value class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } }> JavaScript >>
二分木の種類
バイナリ ツリーは、複数の要素に基づいて複数のタイプに分類できます。
- 子供の数に基づいて
- 完全なバイナリ ツリー
- 縮退したバイナリ ツリー
- 歪んだ二分木
- レベルの完了に基づいて
- 完全なバイナリ ツリー
- 完璧な二分木
- バランスの取れた二分木
- ノード値に基づいて:
- 二分探索木
- AVL ツリー
- レッドブラックツリー
- Bツリー
- B+ ツリー
- セグメントツリー
バイナリ ツリーの操作
1. バイナリツリーへの挿入
ノードを任意のノードの左または右の子として挿入するか、ノードをツリーのルートにすることによって、バイナリ ツリー内の任意の場所にノードを挿入できます。
バイナリ ツリーにノードを挿入するアルゴリズム:
- バイナリ ツリー内に左側の子が欠落しているノードがあるかどうかを確認します。そのようなノードが存在する場合は、新しいノードをその左の子として挿入します。
- バイナリ ツリー内に右側の子が欠落しているノードがあるかどうかを確認します。そのようなノードが存在する場合は、新しいノードをその右側の子として挿入します。
- 左側または右側の子が欠落しているノードが見つからない場合は、両方の子が欠落しているノードを見つけて、そのノードを左側または右側の子として挿入します。
2. 二分木の走査
バイナリ ツリーの走査には、バイナリ ツリーのすべてのノードを訪問することが含まれます。ツリー トラバーサル アルゴリズムは、大きく 2 つのカテゴリに分類できます。
- 深さ優先検索 (DFS) アルゴリズム
- 幅優先検索 (BFS) アルゴリズム
深さ優先検索 (DFS) アルゴリズム:
- 予約注文トラバーサル (現在-左-右): 左または右のサブツリー内のノードにアクセスする前に、現在のノードにアクセスしてください。ここでは、ルート - 左の子 - 右の子をたどります。これは、最初にルート ノードがトラバースされ、次にその左の子、最後に右の子がトラバースされることを意味します。
- インオーダートラバーサル (左→現在→右): 左側のサブツリー内のすべてのノードにアクセスした後、右側のサブツリー内のノードにアクセスする前に、現在のノードにアクセスします。ここで、トラバースは左の子 - ルート - 右の子です。これは、最初に左側の子がトラバースされ、次にそのルート ノードがトラバースされ、最後に右側の子がトラバースされることを意味します。
- 事後トラバーサル (左→右→現在): 左右のサブツリーのすべてのノードを訪問した後、現在のノードを訪問します。 ここで、走査は左の子 - 右の子 - ルートです。これは、最初に左側の子がトラバースされ、次に右側の子がトラバースされ、最後にそのルート ノードがトラバースされたことを意味します。
幅優先検索 (BFS) アルゴリズム:
- レベル順序のトラバーサル: 同じレベルでレベルごとに、左から右にノードを訪問します。ここでは、トラバースはレベルごとに行われます。これは、一番左の子が最初にトラバースし、次に同じレベルの他の子が左から右にトラバースしたことを意味します。
3. バイナリツリーの削除
バイナリ ツリー内の任意のノードを削除し、削除後にノードを再配置して有効なバイナリ ツリーを再度形成できます。
バイナリ ツリー内のノードを削除するアルゴリズム:
C# 日時
- ルートから始めて、バイナリ ツリーの最も深くて右端のノードと、削除するノードを見つけます。
- 一番奥の右端のノードのデータを削除するノードに置き換えます。
- 次に、最も深い右端のノードを削除します。
4. 二分木での検索
トラバーサル手法のいずれかを使用して、ノード内の要素を検索できます。
二分木内のノードを検索するアルゴリズム:
- ルートノードから開始します。
- 現在のノードの値がターゲット値と等しいかどうかを確認します。
- 現在のノードの値がターゲット値と等しい場合、このノードは必須ノードです。
- それ以外の場合、ノードの値がターゲット値と等しくない場合は、左右の子で検索を開始します。
- 値がターゲットと等しいノードが見つからない場合、その値はツリー内に存在しません。
バイナリ ツリーでの補助操作
- 木の高さを調べる
- バイナリツリー内のノードのレベルを検索します
- 木全体のサイズを調べる
バイナリツリーの実装
以下は、バイナリ ツリーの挿入、削除、および走査のためのコードです。
C #include // Node structure to define the structure of the node typedef struct Node { int data; struct Node *left, *right; } Node; // Function to create a new node Node* newNode(int val) { Node* temp = (Node*)malloc(sizeof(Node)); temp->データ = 値; 一時->左 = 一時->右 = NULL; 戻り温度; } // ノードを挿入する関数 Node* insert(Node* root, int data) { // ツリーが空の場合、新しいノードがルートになります if (root == NULL) { root = newNode(data); ルートを返します。 } // ツリーを横断してノードを挿入する位置を見つけるためのキュー Node* queue[100]; int フロント = 0、リア = 0; キュー[リア++] = ルート; while (フロント != リア) { ノード * 温度 = キュー[フロント++]; // ノードを親ノードの左の子として挿入します if (temp->left == NULL) { temp->left = newNode(data); 壊す; } // 左の子が null でない場合、キューにプッシュします。そうでない場合は queue[rear++] = temp->left; // ノードを親ノードの右側の子として挿入します if (temp->right == NULL) { temp->right = newNode(data); 壊す; } // 右の子が null でない場合は、キューにプッシュします。そうでない場合は queue[rear++] = temp->right; ルートを返します。 } /* バイナリ ツリー内の指定された最も深いノード (d_node) を削除する関数 */ void deletDeepest(Node* root, Node* d_node) { Node* queue[100]; int フロント = 0、リア = 0; キュー[リア++] = ルート; // 最後のノードまでレベル順のトラバーサルを実行します Node* temp; while (フロント != リア) { temp = queue[フロント++]; if (temp == d_node) { temp = NULL; 無料(d_node); 戻る; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; 無料(d_node); 戻る; else queue[rear++] = temp->right; if (temp->left) { if (temp->left == d_node) { temp->left = NULL; 無料(d_node); 戻る; else queue[rear++] = temp->left; } } } /* バイナリツリー内の要素を削除する関数 */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL; それ以外の場合はルートを返します。 ノード* キュー[100]; int フロント = 0、リア = 0; キュー[リア++] = ルート; ノード*の温度。 ノード* key_node = NULL; // レベル順のトラバーサルを実行して、最も深いノード (temp) と削除するノード (key_node) を見つけます。 while (front != Rear) { temp = queue[front++]; if (temp->data == key) key_node = temp; if (temp->left) queue[rear++] = temp->left; if (temp->right) queue[rear++] = temp->right; if (key_node != NULL) { int x = temp->data; キーノード->データ = x; deletDeepest(ルート, 一時); ルートを返します。 } // インオーダー ツリー トラバーサル (左 - ルート - 右) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(root->left); printf('%d ', root->data); inorderTraversal(root->right); } // 事前順序付けツリー トラバーサル (ルート - 左 - 右) void preorderTraversal(Node* root) { if (!root) return; printf('%d ', root->data); preorderTraversal(root->left); preorderTraversal(root->right); } // ポストオーダー ツリー トラバーサル (左 - 右 - ルート) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf('%d ', root->data); } // レベル順序ツリー走査の関数 void levelorderTraversal(Node* root) { if (root == NULL) return; // レベル順序トラバーサルのキュー Node* queue[100]; int フロント = 0、リア = 0; キュー[リア++] = ルート; while (フロント != リア) { ノード * 温度 = キュー[フロント++]; printf('%d ', temp->data); // if (temp->left) queue[rear++] = temp->left; 左の子をキューにプッシュします。 // if (temp->right) queue[rear++] = temp->right; // 右の子をキューにプッシュします。 } } /* 上記のアルゴリズムをチェックするドライバー関数。 */ int main() { ノード * ルート = NULL; // ノードの挿入 root = insert(root, 10); ルート = 挿入(ルート, 20); ルート = 挿入(ルート, 30); ルート = 挿入(ルート, 40); printf('事前注文トラバーサル: '); preorderTraversal(ルート); printf('
インオーダートラバーサル: '); inorderTraversal(ルート); printf('
ポストオーダー トラバーサル: '); postorderTraversal(ルート); printf('
レベル順序のトラバーサル: '); levelorderTraversal(ルート); // data = 20 のノードを削除 root = deletion(root, 20); printf('
削除後の順序トラバーサル: '); inorderTraversal(ルート); 0を返します。 }>> ジャワ import java.util.LinkedList; import java.util.Queue; // Node class to define the structure of the node class Node { int data; Node left, right; // Parameterized Constructor Node(int val) { data = val; left = right = null; } } public class BinaryTree { // Function to insert nodes public static Node insert(Node root, int data) { // If tree is empty, new node becomes the root if (root == null) { root = new Node(data); return root; } // Queue to traverse the tree and find the position to // insert the node Queueq = 新しい LinkedList(); q.offer(ルート); while (!q.isEmpty()) { ノード温度 = q.poll(); // ノードを親ノードの左側の子として挿入します if (temp.left == null) { temp.left = new Node(data); 壊す; } // 左の子が null でない場合は、 // キューにプッシュします。それ以外の場合は、 q.offer(temp.left); // ノードを親ノードの右側の子として挿入します if (temp.right == null) { temp.right = new Node(data); 壊す; } // 右の子が null でない場合は、 // キューにプッシュします。そうでない場合は、 q.offer(temp.right); ルートを返します。 } /* バイナリ ツリー内の指定された最も深いノード (d_node) を削除する関数 */ public static void deletDeepest(Node root, Node d_node) { Queueq = 新しい LinkedList(); q.offer(ルート); // 最後のノードまでレベル順序のトラバーサルを実行します。 Node temp; while (!q.isEmpty()) { temp = q.poll(); if (temp == d_node) { temp = null; d_node = null; 戻る; if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; 戻る; それ以外の場合は q.offer(temp.right); if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; 戻る; それ以外の場合は q.offer(temp.left); } } } /* バイナリツリー内の要素を削除する関数 */ public static Node deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; それ以外の場合はルートを返します。 } 列q = 新しい LinkedList(); q.offer(ルート); ノード温度 = 新しいノード(0); ノード key_node = null; // レベル順のトラバーサルを実行して、 // 最も深いノード (temp) と削除されるノード (key_node) を見つけます。 while (!q.isEmpty()) { temp = q.poll(); if (temp.data == key) key_node = temp; if (temp.left != null) q.offer(temp.left); if (temp.right != null) q.offer(temp.right); if (key_node != null) { int x = temp.data; key_node.data = x; deletDeepest(ルート, 一時); ルートを返します。 } // インオーダー ツリー トラバーサル (左 - ルート - 右) public static void inorderTraversal(Node root) { if (root == null) return; inorderTraversal(root.left); System.out.print(root.data + ' '); inorderTraversal(root.right); } // 事前順序付けツリー トラバーサル (ルート - 左 - 右) public static void preorderTraversal(Node root) { if (root == null) return; System.out.print(root.data + ' '); preorderTraversal(root.left); preorderTraversal(root.right); } // ポストオーダー ツリー トラバーサル (左 - 右 - ルート) public static void postorderTraversal(Node root) { if (root == null) return; postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.data + ' '); } // レベル順序ツリー走査の関数 public static void levelorderTraversal(Node root) { if (root == null) return; // レベル順序トラバーサルのキュー キューq = 新しい LinkedList(); q.offer(ルート); while (!q.isEmpty()) { ノード温度 = q.poll(); System.out.print(temp.data + ' '); // 左の子をキューにプッシュ if (temp.left != null) q.offer(temp.left); // 右の子をキューにプッシュ if (temp.right != null) q.offer(temp.right); } } /* 上記のアルゴリズムをチェックするドライバー関数。 */ public static void main(String[] args) { ノードルート = null; // ノードの挿入 root = insert(root, 10); ルート = 挿入(ルート, 20); ルート = 挿入(ルート, 30); ルート = 挿入(ルート, 40); System.out.print('事前注文トラバーサル: '); preorderTraversal(ルート); System.out.print('
インオーダー トラバーサル: '); inorderTraversal(ルート); System.out.print('
ポストオーダー トラバーサル: '); postorderTraversal(ルート); System.out.print('
レベル順序のトラバーサル: '); levelorderTraversal(ルート); // data = 20 のノードを削除 root = deletion(root, 20); System.out.print('
削除後の順序トラバーサル: '); inorderTraversal(ルート); } }>> パイソン from collections import deque # Node class to define the structure of the node class Node: def __init__(self, val): self.data = val self.left = self.right = None # Function to insert nodes def insert(root, data): # If tree is empty, new node becomes the root if root is None: root = Node(data) return root # Queue to traverse the tree and find the position to insert the node q = deque() q.append(root) while q: temp = q.popleft() # Insert node as the left child of the parent node if temp.left is None: temp.left = Node(data) break # If the left child is not null push it to the queue else: q.append(temp.left) # Insert node as the right child of parent node if temp.right is None: temp.right = Node(data) break # If the right child is not null push it to the queue else: q.append(temp.right) return root # Function to delete the given deepest node (d_node) in binary tree def deletDeepest(root, d_node): q = deque() q.append(root) # Do level order traversal until last node while q: temp = q.popleft() if temp == d_node: temp = None del d_node return if temp.right: if temp.right == d_node: temp.right = None del d_node return else: q.append(temp.right) if temp.left: if temp.left == d_node: temp.left = None del d_node return else: q.append(temp.left) # Function to delete element in binary tree def deletion(root, key): if not root: return None if root.left is None and root.right is None: if root.data == key: return None else: return root q = deque() q.append(root) temp = None key_node = None # Do level order traversal to find deepest node (temp) and node to be deleted (key_node) while q: temp = q.popleft() if temp.data == key: key_node = temp if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) if key_node is not None: x = temp.data key_node.data = x deletDeepest(root, temp) return root # Inorder tree traversal (Left - Root - Right) def inorderTraversal(root): if not root: return inorderTraversal(root.left) print(root.data, end=' ') inorderTraversal(root.right) # Preorder tree traversal (Root - Left - Right) def preorderTraversal(root): if not root: return print(root.data, end=' ') preorderTraversal(root.left) preorderTraversal(root.right) # Postorder tree traversal (Left - Right - Root) def postorderTraversal(root): if root is None: return postorderTraversal(root.left) postorderTraversal(root.right) print(root.data, end=' ') # Function for Level order tree traversal def levelorderTraversal(root): if root is None: return # Queue for level order traversal q = deque() q.append(root) while q: temp = q.popleft() print(temp.data, end=' ') # Push left child in the queue if temp.left: q.append(temp.left) # Push right child in the queue if temp.right: q.append(temp.right) # Driver function to check the above algorithm if __name__ == '__main__': root = None # Insertion of nodes root = insert(root, 10) root = insert(root, 20) root = insert(root, 30) root = insert(root, 40) print('Preorder traversal:', end=' ') preorderTraversal(root) print('
Inorder traversal:', end=' ') inorderTraversal(root) print('
Postorder traversal:', end=' ') postorderTraversal(root) print('
Level order traversal:', end=' ') levelorderTraversal(root) # Delete the node with data = 20 root = deletion(root, 20) print('
Inorder traversal after deletion:', end=' ') inorderTraversal(root)> C# using System; using System.Collections.Generic; // Node class to define the structure of the node public class Node { public int data; public Node left, right; // Parameterized Constructor public Node(int val) { data = val; left = right = null; } } public class Program { // Function to insert nodes public static Node Insert(Node root, int data) { // If tree is empty, new node becomes the root if (root == null) { root = new Node(data); return root; } // Queue to traverse the tree and find the position to insert the node Queueq = 新しいキュー(); q.エンキュー(ルート); while (q.Count != 0) { ノード温度 = q.Dequeue(); // ノードを親ノードの左側の子として挿入します if (temp.left == null) { temp.left = new Node(data); 壊す; } // 左の子が null でない場合は、それをキューにプッシュします。それ以外の場合は、q.Enqueue(temp.left); // ノードを親ノードの右側の子として挿入します if (temp.right == null) { temp.right = new Node(data); 壊す; } // 右の子が null でない場合は、それをキューにプッシュします。それ以外の場合は、q.Enqueue(temp.right); ルートを返します。 } /* バイナリ ツリー内の指定された最も深いノード (d_node) を削除する関数 */ public static void DeleteDeepest(Node root, Node d_node) { Queueq = 新しいキュー(); q.エンキュー(ルート); // 最後のノードまでレベル順序のトラバーサルを実行します。 Node temp; while (q.Count != 0) { temp = q.Dequeue(); if (temp == d_node) { temp = null; d_node = null; 戻る; if (temp.right != null) { if (temp.right == d_node) { temp.right = null; d_node = null; 戻る; q.Enqueue(temp.right); } else q.Enqueue(temp.right); if (temp.left != null) { if (temp.left == d_node) { temp.left = null; d_node = null; 戻る; q.Enqueue(temp.left); } else q.Enqueue(temp.left); } } } /* バイナリツリー内の要素を削除する関数 */ public static Node Deletion(Node root, int key) { if (root == null) return null; if (root.left == null && root.right == null) { if (root.data == key) return null; それ以外の場合はルートを返します。 } 列q = 新しいキュー(); q.エンキュー(ルート); ノード温度 = 新しいノード(0); ノード key_node = null; // レベル順のトラバーサルを実行して、最も深いノード (temp) と削除するノード (key_node) を見つけます while (q.Count != 0) { temp = q.Dequeue(); if (temp.data == key) key_node = temp; if (temp.left != null) q.Enqueue(temp.left); if (temp.right != null) q.Enqueue(temp.right); if (key_node != null) { int x = temp.data; key_node.data = x; DeleteDeepest(ルート, 一時); ルートを返します。 } // インオーダー ツリー トラバーサル (左 - ルート - 右) public static void InorderTraversal(Node root) { if (root == null) return; InorderTraversal(root.left); Console.Write(root.data + ' '); InorderTraversal(root.right); } // プレオーダー ツリー トラバーサル (ルート - 左 - 右) public static void PreorderTraversal(Node root) { if (root == null) return; Console.Write(root.data + ' '); PreorderTraversal(root.left); PreorderTraversal(root.right); } // ポストオーダー ツリー トラバーサル (左 - 右 - ルート) public static void PostorderTraversal(Node root) { if (root == null) return; PostorderTraversal(root.left); PostorderTraversal(root.right); Console.Write(root.data + ' '); } // レベル順序ツリー走査の関数 public static void LevelorderTraversal(Node root) { if (root == null) return; // レベル順序トラバーサルのキュー キューq = 新しいキュー(); q.エンキュー(ルート); while (q.Count != 0) { ノード温度 = q.Dequeue(); Console.Write(temp.data + ' '); // if (temp.left != null) q.Enqueue(temp.left); 左の子をキューにプッシュします。 // if (temp.right != null) q.Enqueue(temp.right); // 右の子をキューにプッシュします。 } } /* 上記のアルゴリズムをチェックするドライバー関数。 */ public static void Main(string[] args) { ノードルート = null; // ノードの挿入 root = Insert(root, 10); ルート = 挿入(ルート, 20); ルート = 挿入(ルート, 30); ルート = 挿入(ルート, 40); Console.Write('事前注文トラバーサル: '); PreorderTraversal(ルート); Console.Write('
インオーダー トラバーサル: '); InorderTraversal(ルート); Console.Write('
ポストオーダー トラバーサル: '); PostorderTraversal(ルート); Console.Write('
レベル順序のトラバーサル: '); LevelorderTraversal(ルート); // data = 20 のノードを削除 root = Deletion(root, 20); Console.Write('
削除後の順序トラバーサル: '); InorderTraversal(ルート); } }>> JavaScript // Node class to define the structure of the node class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } // Function to insert nodes function insert(root, data) { // If tree is empty, new node becomes the root if (root === null) { root = new Node(data); return root; } // queue to traverse the tree and find the position to // insert the node const q = []; q.push(root); while (q.length !== 0) { const temp = q.shift(); // Insert node as the left child of the parent node if (temp.left === null) { temp.left = new Node(data); break; } // If the left child is not null push it to the // queue else q.push(temp.left); // Insert node as the right child of parent node if (temp.right === null) { temp.right = new Node(data); break; } // If the right child is not null push it to the // queue else q.push(temp.right); } return root; } /* function to delete the given deepest node (d_node) in binary tree */ function deletDeepest(root, d_node) { const q = []; q.push(root); // Do level order traversal until last node let temp; while (q.length !== 0) { temp = q.shift(); if (temp === d_node) { temp = null; delete d_node; return; } if (temp.right) { if (temp.right === d_node) { temp.right = null; delete d_node; return; } else q.push(temp.right); } if (temp.left) { if (temp.left === d_node) { temp.left = null; delete d_node; return; } else q.push(temp.left); } } } /* function to delete element in binary tree */ function deletion(root, key) { if (!root) return null; if (root.left === null && root.right === null) { if (root.data === key) return null; else return root; } const q = []; q.push(root); let temp; let key_node = null; // Do level order traversal to find deepest // node(temp) and node to be deleted (key_node) while (q.length !== 0) { temp = q.shift(); if (temp.data === key) key_node = temp; if (temp.left) q.push(temp.left); if (temp.right) q.push(temp.right); } if (key_node !== null) { const x = temp.data; key_node.data = x; deletDeepest(root, temp); } return root; } // Inorder tree traversal (Left - Root - Right) function inorderTraversal(root) { if (!root) return; inorderTraversal(root.left); console.log(root.data + ' '); inorderTraversal(root.right); } // Preorder tree traversal (Root - Left - Right) function preorderTraversal(root) { if (!root) return; console.log(root.data + ' '); preorderTraversal(root.left); preorderTraversal(root.right); } // Postorder tree traversal (Left - Right - Root) function postorderTraversal(root) { if (root === null) return; postorderTraversal(root.left); postorderTraversal(root.right); console.log(root.data + ' '); } // Function for Level order tree traversal function levelorderTraversal(root) { if (root === null) return; // Queue for level order traversal const q = []; q.push(root); while (q.length !== 0) { const temp = q.shift(); console.log(temp.data + ' '); // Push left child in the queue if (temp.left) q.push(temp.left); // Push right child in the queue if (temp.right) q.push(temp.right); } } /* Driver function to check the above algorithm. */ let root = null; // Insertion of nodes root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); console.log('Preorder traversal: '); preorderTraversal(root); console.log('
Inorder traversal: '); inorderTraversal(root); console.log('
Postorder traversal: '); postorderTraversal(root); console.log('
Level order traversal: '); levelorderTraversal(root); // Delete the node with data = 20 root = deletion(root, 20); console.log('
Inorder traversal after deletion: '); inorderTraversal(root);> C++14 #include using namespace std; // Node class to define the structure of the node class Node { public: int data; Node *left, *right; // Parameterized Constructor Node(int val) { data = val; left = right = NULL; } }; // Function to insert nodes Node* insert(Node* root, int data) { // If tree is empty, new node becomes the root if (root == NULL) { root = new Node(data); return root; } // queue to traverse the tree and find the position to // insert the node queueq; q.push(ルート); while (!q.empty()) { ノード * 温度 = q.front(); q.pop(); // ノードを親ノードの左の子として挿入します if (temp->left == NULL) { temp->left = new Node(data); 壊す; } // 左の子が null でない場合は、 // キューにプッシュします。そうでない場合は、 q.push(temp->left); // ノードを親ノードの右側の子として挿入します if (temp->right == NULL) { temp->right = new Node(data); 壊す; } // 右の子が null でない場合は、 // キューにプッシュします。そうでない場合は、 q.push(temp->right); ルートを返します。 } /* バイナリ ツリー内の指定された最も深いノード (d_node) を削除する関数 */ void deletDeepest(Node* root, Node* d_node) { queueq; q.push(ルート); // 最後のノードまでレベル順のトラバーサルを実行します Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; 削除 (d_node); 戻る; } if (temp->right) { if (temp->right == d_node) { temp->right = NULL; 削除 (d_node); 戻る; それ以外の場合は q.push(temp->right); if (temp->left) { if (temp->left == d_node) { temp->left = NULL; 削除 (d_node); 戻る; それ以外の場合は q.push(temp->left); } } } /* バイナリツリー内の要素を削除する関数 */ Node* deletion(Node* root, int key) { if (!root) return NULL; if (root->left == NULL && root->right == NULL) { if (root->data == key) return NULL; それ以外の場合はルートを返します。 } 列q; q.push(ルート); ノード*の温度。 ノード* key_node = NULL; // レベル順のトラバーサルを実行して、 // 最も深いノード (temp) と削除するノード (key_node) を見つけます。 while (!q.empty()) { temp = q.front(); q.pop(); if (temp->data == key) key_node = temp; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); if (key_node != NULL) { int x = temp->data; キーノード->データ = x; deletDeepest(ルート, 一時); ルートを返します。 } // インオーダー ツリー トラバーサル (左 - ルート - 右) void inorderTraversal(Node* root) { if (!root) return; inorderTraversal(root->left); コート<< root->データ<< ' '; inorderTraversal(root->右）; } // 事前順序付けツリー トラバーサル (ルート - 左 - 右) void preorderTraversal(Node* root) { if (!root) return; コート<< root->データ<< ' '; preorderTraversal(root->左）; preorderTraversal(root->right); } // ポストオーダー ツリー トラバーサル (左 - 右 - ルート) void postorderTraversal(Node* root) { if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); コート<< root->データ<< ' '; } // Function for Level order tree traversal void levelorderTraversal(Node* root) { if (root == NULL) return; // Queue for level order traversal queueq; q.push(ルート); while (!q.empty()) { ノード * 温度 = q.front(); q.pop(); コート<< temp->データ<< ' '; // Push left child in the queue if (temp->左) q.push(temp->left); // 右の子をキューにプッシュ if (temp->right) q.push(temp->right); } } /* 上記のアルゴリズムをチェックするドライバー関数。 */ int main() { ノード * ルート = NULL; // ノードの挿入 root = insert(root, 10); ルート = 挿入(ルート, 20); ルート = 挿入(ルート, 30); ルート = 挿入(ルート, 40); コート<< 'Preorder traversal: '; preorderTraversal(root); cout << '
Inorder traversal: '; inorderTraversal(root); cout << '
Postorder traversal: '; postorderTraversal(root); cout << '
Level order traversal: '; levelorderTraversal(root); // Delete the node with data = 20 root = deletion(root, 20); cout << '
Inorder traversal after deletion: '; inorderTraversal(root); }> 出力
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30>
二分木演算の複雑さの分析
| オペレーション | 時間計算量 | 空間の複雑さ Javaの文字列.値 |
|---|---|---|
| 挿入 | の上） | の上） |
| 予約注文トラバーサル | の上） | の上） |
インオーダートラバーサル | の上） | の上） |
| 郵便為替トラバーサル | の上） | の上） |
| レベル順序のトラバーサル | の上） | の上） |
削除 | の上） | の上） Javaのループの終了 |
検索中 | の上） | の上） |
使用できます モリス・トラバーサル バイナリ ツリーのすべてのノードを O(1) 時間で走査します。
バイナリーツリーの利点
- 効率的な検索: バイナリ ツリーは、各ノードに最大 2 つの子ノードがあるため、特定の要素を検索する場合に効率的です。 メモリ効率が高い: バイナリ ツリーは、他のツリー データ構造と比較して必要なメモリが少ないため、メモリ効率が高くなります。
- バイナリ ツリーは、各ノードに最大 2 つの子 (左の子と右の子) があるため、実装と理解が比較的簡単です。
バイナリーツリーの欠点
- 限定された構造: バイナリ ツリーはノードあたり 2 つの子ノードに制限されているため、特定のアプリケーションでは有用性が制限される可能性があります。たとえば、ツリーがノードごとに 3 つ以上の子ノードを必要とする場合は、別のツリー構造の方が適している可能性があります。
- アンバランスな木: 一方のサブツリーが他方のサブツリーより大幅に大きいアンバランスなバイナリ ツリーでは、検索操作が非効率になる可能性があります。これは、ツリーのバランスが適切に取れていない場合、またはデータがランダムでない順序で挿入された場合に発生する可能性があります。
- スペース効率の悪さ: バイナリ ツリーは、他のデータ構造と比較すると、スペース効率が悪い場合があります。これは、各ノードに 2 つの子ポインターが必要であり、大きなツリーでは大量のメモリー オーバーヘッドになる可能性があるためです。
- 最悪の場合のパフォーマンスの低下: 最悪のシナリオでは、バイナリ ツリーが縮退または歪む可能性があり、各ノードの子が 1 つだけになる可能性があります。この場合、検索操作の時間計算量は O(n) に低下する可能性があります。ここで、n はツリー内のノードの数です。
二分木の応用
- バイナリ ツリーを使用すると、 階層データを表す 。
- ハフマンコーディングツリーは以下で使用されます。 データ圧縮アルゴリズム 。
- 優先キュー これは、O(1) 時間計算量の最大または最小を検索するために使用されるバイナリ ツリーのもう 1 つのアプリケーションです。
- データベースでセグメント化されたインデックス作成に役立ち、システムにキャッシュを保存するのに役立ちます。
- バイナリ ツリーは、分類と回帰分析に使用される機械学習アルゴリズムの一種であるデシジョン ツリーを実装するために使用できます。
バイナリーツリーに関するよくある質問
1. 二分木とは何ですか?
バイナリ ツリーはノードで構成される非線形データ構造で、各ノードには最大 2 つの子 (左の子と右の子) があります。
2. 二分木の種類は何ですか?
バイナリ ツリーは、完全なバイナリ ツリー、完全なバイナリ ツリー、完全なバイナリ ツリー、バランスの取れたバイナリ ツリー (AVL ツリーや赤黒ツリーなど)、および縮退した (または異常な) バイナリ ツリーを含むさまざまなタイプに分類できます。
3. 二分木の高さはどれくらいですか?
二分木の高さは、ルート ノードからリーフ ノードまでの最長パスの長さです。これは、ルート ノードからリーフ ノードまでの最長パス内のエッジの数を表します。
4. 二分木のノードの深さはどれくらいですか?
バイナリ ツリー内のノードの深さは、ルート ノードからその特定のノードまでのパスの長さです。ルートノードの深さは0です。
Javaの条件演算子
5. バイナリ ツリーでツリー トラバーサルを実行するにはどうすればよいですか?
バイナリ ツリーのツリー トラバーサルは、順序トラバーサル、前順序トラバーサル、事後トラバーサル、レベル順トラバーサル (幅優先トラバーサルとも呼ばれます) など、さまざまな方法で実行できます。
6. バイナリ ツリーの順序トラバーサルとは何ですか?
インオーダートラバーサルでは、ノードは左の子、ルート、右の子の順序で再帰的にアクセスされます。この走査により、二分探索ツリー内でノードが降順ではない順序でアクセスされることになります。
7. バイナリ ツリーのプレオーダー トラバーサルとは何ですか?
事前順序トラバーサルでは、ノードはルート、左の子、右の子の順序で再帰的にアクセスされます。この走査により、ルート ノードが最初に訪問されるノードになります。
8. バイナリ ツリーにおけるポストオーダー トラバーサルとは何ですか?
ポストオーダートラバーサルでは、ノードは左の子、右の子、ルートの順序で再帰的にアクセスされます。この走査により、ルート ノードが最後に訪問されるノードになります。
9. 二分木と二分探索木の違いは何ですか?
バイナリ ツリーは、各ノードに最大 2 つの子を持つ階層データ構造です。一方、バイナリ検索ツリーは、ノードの左側の子にノードの値より小さい値が含まれ、右側の子に値が含まれるタイプのバイナリ ツリーです。ノードの値より大きい。
10. バランスの取れた二分木とは何ですか?
バランスの取れた二分木は、すべてのノードの左右のサブツリーの高さが最大 1 つだけ異なる二分木です。バランスのとれたツリーは、O(log n) に近い時間計算量で検索、挿入、削除などの効率的な操作を維持するのに役立ちます。
結論：
ツリーは階層データ構造です。ツリーの主な用途には、階層データの維持、適度なアクセスの提供、および挿入/削除操作が含まれます。バイナリ ツリーは、すべてのノードに最大 2 つの子を持つツリーの特殊なケースです。
関連記事：
- 二分木の性質
- 二分木の種類