バイナリツリー JAVA

二分木 データを階層形式で格納するため、主に並べ替えや検索に使用されるツリー型の非線形データ構造です。このセクションでは、 Java でのバイナリツリーデータ構造の実装 。また、バイナリツリーデータ構造についても簡単に説明します。

二分木

各ノード (親) が最大 2 つの子ノード (左右) を持つツリーをバイナリツリーと呼びます。最上位のノードはルートノードと呼ばれます。バイナリツリーでは、ノードにはデータと左右の子ノードのポインタ (アドレス) が含まれます。

の身長二分木の 木のルート間のエッジの数 そしてその最も遠い（最も深い）葉。もしその木が空の、高さは 0 。ノードの高さは次のように表されます。 h 。

上の二分木の高さは 2 です。

次の式を使用して葉とノードの数を計算できます。

リーフノードの最大数はバイナリツリーです。 2^h
ノードの最大数はバイナリツリーです。 2^h+1-1

ここで、h は二分木の高さです。

二分木の例

二分木の種類

データ構造には次のタイプの二分木があります。

完全な/厳密なバイナリツリー
完全なバイナリツリー
完璧な二分木
バランスバイナリツリー
ルート化されたバイナリツリー
変性/病的な二分木
拡張バイナリツリー
歪んだ二分木
1. 左に歪んだ二分木
2. 右に傾いた二分木
スレッド化されたバイナリツリー
1. シングルスレッドバイナリツリー
2. ダブルスレッドバイナリツリー

Java でのバイナリツリーの実装

バイナリツリーを実装するにはさまざまな方法があります。このセクションでは、LinkedList データ構造を使用してバイナリツリーを実装します。それとともに、ノードを検索してバイナリツリーにノードを挿入する、走査順序も実装します。

LinkedListを使用したバイナリツリーの実装

アルゴリズム

データの左と右という 3 つの属性を含む Node クラスを定義します。ここで、left はノードの左の子を表し、right はノードの右の子を表します。

ノードが作成されると、データはノードの data 属性に渡され、左右の両方が null に設定されます。
属性ルートを持つ別のクラスを定義します。
Root はツリーのルートノードを表し、null に初期化します。

ルートが null かどうか、つまりツリーが空かどうかをチェックします。新しいノードがルートとして追加されます。
それ以外の場合は、root がキューに追加されます。
変数ノードは現在のノードを表します。
まず、ノードに左右の子があるかどうかを確認します。「はい」の場合、両方のノードがキューに追加されます。
左の子が存在しない場合は、新しいノードを左の子として追加します。
左側が存在する場合は、新しいノードを右側の子として追加します。

これはツリー全体を走査し、左の子、ルート、右の子の順に出力します。

BinarySearchTree.java

Javaのobjとは何ですか

 public class BinarySearchTree { //Represent the node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //factorial() will calculate the factorial of given number public int factorial(int num) { int fact = 1; if(num == 0) return 1; else { while(num &gt; 1) { fact = fact * num; num--; } return fact; } } //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key public int numOfBST(int key) { int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key)); return catalanNumber; } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Display total number of possible binary search tree with key 5 System.out.println(&apos;Total number of possible Binary Search Trees with given key: &apos; + bt.numOfBST(5)); } }

出力：

 Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7

二分木の演算

バイナリツリーでは次の操作を実行できます。

挿入
削除
検索
トラバーサル

バイナリツリーにノードを挿入する Java プログラム

BinaryTreeInsert.java

 public class BinaryTreeInsert { public static void main(String[] args) { new BinaryTreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println(&apos;Building tree with root value &apos; + rootnode.value); System.out.println(&apos;=================================&apos;); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); } public void insert(Node node, int value) { if (value node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(&apos; Inserted &apos; + value + &apos; to right of Node &apos; + node.value); node.right = new Node(value); } } } }

出力：

 Building tree with root value 25 ================================= Inserted 11 to left of Node 25 Inserted 15 to right of Node 11 Inserted 16 to right of Node 15 Inserted 23 to right of Node 16 Inserted 79 to right of Node 25

Java でノードを削除する Java プログラム

アルゴリズム

ルートから始めて、バイナリツリーの最も深い右端のノードと削除するノードを見つけます。
一番奥の右端のノードのデータを削除するノードに置き換えます。
次に、最も深い右端のノードを削除します。

次の図を考えてみましょう。

削除ノード.java

 import java.util.LinkedList; import java.util.Queue; public class DeleteNode { // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node(int key) { this.key = key; left = null; right = null; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null) return; inorder(temp.left); System.out.print(temp.key + &apos; &apos;); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue q = new LinkedList(); q.add(root); Node temp = null; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null; return; } if (temp.right!=null) { if (temp.right == delNode) { temp.right = null; return; } else q.add(temp.right); } if (temp.left != null) { if (temp.left == delNode) { temp.left = null; return; } else q.add(temp.left); } } } // Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null) return; if (root.left == null &amp;&amp; root.right == null) { if (root.key == key) { root=null; return; } else return; } Queue q = new LinkedList(); q.add(root); Node temp = null, keyNode = null; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } if (keyNode != null) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } } // Driver code public static void main(String args[]) { root = new Node(10); root.left = new Node(11); root.left.left = new Node(7); root.left.right = new Node(12); root.right = new Node(9); root.right.left = new Node(15); root.right.right = new Node(8); System.out.print(&apos;Inorder traversal before deletion: &apos;); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print(&apos;
Inorder traversal after deletion: &apos;); inorder(root); } }

出力：

 Inorder traversal before deletion: 7 11 12 10 15 9 8 Inorder traversal after deletion: 8 11 12 10 15 9

バイナリツリー内のノードを検索する Java プログラム

アルゴリズム

データの左と右の 3 つの属性を持つ Node クラスを定義します。ここで、left はノードの左の子を表し、right はノードの右の子を表します。
ノードが作成されると、データはノードの data 属性に渡され、左右の両方が null に設定されます。
ルートとフラグの 2 つの属性を持つ別のクラスを定義します。
1. Root はツリーのルートノードを表し、null に初期化されます。
2. Flag は、指定されたノードがツリー内に存在するかどうかを確認するために使用されます。最初は false に設定されます。

ルートが null かどうか、つまりツリーが空かどうかをチェックします。
ツリーが空でない場合は、temp のデータと値が比較されます。それらが等しい場合、フラグを true に設定して戻ります。
searchNode() を再帰的に呼び出して左のサブツリーをたどり、値が左のサブツリーに存在するかどうかを確認します。
searchNode() を再帰的に呼び出して右のサブツリーをトラバースし、値が右のサブツリーに存在するかどうかを確認します。

SearchBinaryTree.java

 public class SearchBinaryTree { //Represent a node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree() { root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value) { //Check whether tree is empty if(root == null) { System.out.println(&apos;Tree is empty&apos;); } else { //If value is found in the given binary tree then, set the flag to true if(temp.data == value) { flag = true; return; } //Search in left subtree if(flag == false &amp;&amp; temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false &amp;&amp; temp.right != null) { searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(11); bt.root.left = new Node(8); bt.root.right = new Node(12); bt.root.left.left = new Node(78); bt.root.right.left = new Node(23); bt.root.right.right = new Node(36); //Search for node 5 in the binary tree bt.searchNode(bt.root, 23); if(flag) System.out.println(&apos;Element is present in the binary tree.&apos;); else System.out.println(&apos;Element is not present in the binary tree.&apos;); } }

出力：

 Element is present in the binary tree.

バイナリツリートラバーサル

走査順序	初回訪問	2回目の訪問	3回目の訪問
順番に	左のサブツリーを順番に訪問します	ルートノードにアクセス	右のサブツリーを順番に訪問します
予約注文	ルートノードにアクセス	予約注文で左のサブツリーにアクセス	予約注文で右のサブツリーにアクセス
通販	ポストオーダーで左のサブツリーにアクセス	ポストオーダーで右のサブツリーにアクセスする	ルートノードにアクセス

注: 上記の 3 つの走査以外に、境界走査と呼ばれる別の走査順序があります。

インオーダー、プレオーダー、ポストオーダーのトラバーサルを行う Java プログラム

BinaryTree.java

 public class BinaryTree { // first node private Node root; BinaryTree() { root = null; } // Class representing tree nodes static class Node { int value; Node left; Node right; Node(int value) { this.value = value; left = null; right = null; } public void displayData() { System.out.print(value + &apos; &apos;); } } public void insert(int i) { root = insert(root, i); } //Inserting node - recursive method public Node insert(Node node, int value) { if(node == null){ return new Node(value); } // Move to the left if passed value is // less than the current node if(value node.value) { node.right = insert(node.right, value); } return node; } // Search node in binary search tree public Node find(int searchedValue) { Node current = root; while(current.value != searchedValue) { if(searchedValue = current = current.right; if(current == null) { return null; } } return current; } // For traversing in order public void inOrder(Node node) { if(node != null) { inOrder(node.left); node.displayData(); inOrder(node.right); } } // Preorder traversal public void preOrder(Node node) { if(node != null){ node.displayData(); preOrder(node.left); preOrder(node.right); } } // Postorder traversal public void postOrder(Node node) { if(node != null) { postOrder(node.left); postOrder(node.right); node.displayData(); } } public static void main(String[] args) { BinaryTree bst = new BinaryTree(); bst.insert(34); bst.insert(56); bst.insert(12); bst.insert(89); bst.insert(67); bst.insert(90); System.out.println(&apos;Inorder traversal of binary tree&apos;); bst.inOrder(bst.root); System.out.println(); System.out.println(&apos;Preorder traversal of binary tree&apos;); bst.preOrder(bst.root); System.out.println(); System.out.println(&apos;Postorder traversal of binary tree&apos;); bst.postOrder(bst.root); System.out.println(); } }

出力：

 Inorder traversal of binary tree 12 34 56 67 89 90 Preorder traversal of binary tree 34 12 56 89 67 90 Postorder traversal of binary tree 12 67 90 89 56 34

上記の演算の他に、大きいノード、最小のノード、全ノードの合計などの演算も実行できます。

バイナリツリー内の最大のノードを見つける Java プログラム

LargestNode.java

 public class LargestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public LargestNode() { root = null; } //largestElement() will find out the largest node in the binary tree public int largestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println(&apos;Tree is empty&apos;); return 0; } else { int leftMax, rightMax; //Max will store temp&apos;s data int max = temp.data; //It will find largest element in left subtree if(temp.left != null){ leftMax = largestElement(temp.left); //Compare max with leftMax and store greater value into max max = Math.max(max, leftMax); } //It will find largest element in right subtree if(temp.right != null){ rightMax = largestElement(temp.right); //Compare max with rightMax and store greater value into max max = Math.max(max, rightMax); } return max; } } public static void main(String[] args) { LargestNode bt = new LargestNode(); //Add nodes to the binary tree bt.root = new Node(90); bt.root.left = new Node(99); bt.root.right = new Node(23); bt.root.left.left = new Node(96); bt.root.right.left = new Node(45); bt.root.right.right = new Node(6); bt.root.right.left = new Node(13); bt.root.right.right = new Node(77); //Display largest node in the binary tree System.out.println(&apos;Largest element in the binary tree: &apos; + bt.largestElement(bt.root)); } }

出力：

 Largest element in the binary tree: 99

二分木の最小ノードを見つける Java プログラム

アルゴリズム

データ、左、右の 3 つの属性を持つ Node クラスを定義します。ここで、left はノードの左の子を表し、right はノードの右の子を表します。
ノードが作成されると、データはノードの data 属性に渡され、左右の両方が null に設定されます。
ルート属性を持つ別のクラスを定義します。

かどうかをチェックします ルートがnullです 、これはツリーが空であることを意味します。
Tree が空でない場合は、temp のデータを格納する変数 min を定義します。
smallestElement() を再帰的に呼び出して、左側のサブツリーの最小ノードを見つけます。その値を leftMin に保存します。 min の値を leftMin と比較し、最小値 2 を min に保存します。
smallestElement() を再帰的に呼び出して、右側のサブツリーの最小ノードを見つけます。その値を rightMin に保存します。 min の値を rightMin と比較し、最大値 2 を min に格納します。
最後に、min はバイナリツリー内の最小のノードを保持します。

SmallestNode.java

 public class SmallestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public SmallestNode() { root = null; } //smallestElement() will find out the smallest node in the binary tree public int smallestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println(&apos;Tree is empty&apos;); return 0; } else { int leftMin, rightMin; //Min will store temp&apos;s data int min = temp.data; //It will find smallest element in left subtree if(temp.left != null) { leftMin = smallestElement(temp.left); //If min is greater than leftMin then store the value of leftMin into min min = Math.min(min, leftMin); } //It will find smallest element in right subtree if(temp.right != null) { rightMin = smallestElement(temp.right); //If min is greater than rightMin then store the value of rightMin into min min = Math.min(min, rightMin); } return min; } } public static void main(String[] args) { SmallestNode bt = new SmallestNode(); //Add nodes to the binary tree bt.root = new Node(9); bt.root.left = new Node(5); bt.root.right = new Node(7); bt.root.left.left = new Node(1); bt.root.right.left = new Node(2); bt.root.right.right = new Node(8); bt.root.right.left = new Node(4); bt.root.right.right = new Node(3); //Display smallest node in the binary tree System.out.println(&apos;Smallest element in the binary tree: &apos; + bt.smallestElement(bt.root)); } }

出力：

 Smallest element in the binary tree: 1

二分木の最大幅を求める Java プログラム

アルゴリズム

データの左と右の 3 つの属性を持つ Node クラスを定義します。ここで、left はノードの左の子を表し、right はノードの右の子を表します。
ノードが作成されると、データはノードの data 属性に渡され、左右の両方が null に設定されます。
ルート属性を持つ別のクラスを定義します。

find最大幅()指定されたバイナリツリーの最大幅を調べます。

変数 maxWidth には、任意のレベルに存在するノードの最大数が格納されます。
キューはバイナリツリーをレベルごとに走査するために使用されます。
ルートが null かどうか、つまりツリーが空かどうかをチェックします。
そうでない場合は、ルートノードをキューに追加します。変数nodesInLevelは、各レベルのノードの数を追跡します。
nodesInLevel > 0 の場合、キューの先頭からノードを削除し、その左右の子をキューに追加します。最初の反復では、ノード 1 が削除され、その子ノード 2 と 3 がキューに追加されます。 2 回目の反復では、ノード 2 が削除され、その子 4 と 5 がキューに追加されます。
MaxWidth には max(maxWidth, NodesInLevel) が格納されます。したがって、任意の時点で、これはノードの最大数を表します。
これは、ツリーのすべてのレベルが走査されるまで続きます。

BinaryTree.java

 import java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree() { root = null; } //findMaximumWidth() will find out the maximum width of the given binary tree public int findMaximumWidth() { int maxWidth = 0; //Variable nodesInLevel keep tracks of number of nodes in each level int nodesInLevel = 0; //queue will be used to keep track of nodes of tree level-wise Queue queue = new LinkedList(); //Check if root is null, then width will be 0 if(root == null) { System.out.println(&apos;Tree is empty&apos;); return 0; } else { //Add root node to queue as it represents the first level queue.add(root); while(queue.size() != 0) { //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue nodesInLevel = queue.size(); //maxWidth will hold maximum width. //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel maxWidth = Math.max(maxWidth, nodesInLevel); //If variable nodesInLevel contains more than one node //then, for each node, we&apos;ll add left and right child of the node to the queue while(nodesInLevel &gt; 0) { Node current = queue.remove(); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); nodesInLevel--; } } } return maxWidth; } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); bt.root.left.left.left = new Node(8); //Display the maximum width of given tree System.out.println(&apos;Maximum width of the binary tree: &apos; + bt.findMaximumWidth()); } }

出力：

 Maximum width of the binary tree: 4

TechCodeview

二分木

二分木の例

二分木の種類

Java でのバイナリツリーの実装

LinkedListを使用したバイナリツリーの実装

アルゴリズム

二分木の演算

バイナリツリーにノードを挿入する Java プログラム

Java でノードを削除する Java プログラム

アルゴリズム

バイナリツリー内のノードを検索する Java プログラム

アルゴリズム

バイナリツリートラバーサル

注: 上記の 3 つの走査以外に、境界走査と呼ばれる別の走査順序があります。

インオーダー、プレオーダー、ポストオーダーのトラバーサルを行う Java プログラム

バイナリツリー内の最大のノードを見つける Java プログラム

二分木の最小ノードを見つける Java プログラム

アルゴリズム

二分木の最大幅を求める Java プログラム

アルゴリズム