TechCodeview

עץ בינארי הוא מבנה נתונים לא ליניארי מסוג עץ המשמש בעיקר למיון וחיפוש מכיוון שהם מאחסנים נתונים בצורה היררכית. בחלק זה נלמד את ה יישום של מבנה נתוני עץ בינארי ב-Java . כמו כן, מספק תיאור קצר של מבנה נתוני עץ בינארי.

עץ בינארי

עץ שבו לכל צומת (הורה) יש לכל היותר שני צמתים בני (ימין ושמאל) נקרא עץ בינארי. הצומת העליון ביותר נקרא צומת השורש. בעץ בינארי צומת מכיל את הנתונים ואת המצביע (הכתובת) של צומת הילד השמאלי והימני.

ה גוֹבַה של עץ בינארי הוא מספר הקצוות בין שורש העץ והעלה הרחוק ביותר (העמוק ביותר) שלו. אם העץ כן ריק , הגובה הוא 0 . גובה הצומת מסומן ב ח .

גובה העץ הבינארי לעיל הוא 2.

נוכל לחשב את מספר העלים והצומת באמצעות הנוסחה הבאה.

היסטוריה בג'אווה

• המספר המרבי של צמתים עלים הוא עץ בינארי: 2^ח
• המספר המרבי של צמתים הוא עץ בינארי: 2^h+1-1

איפה, h הוא גובה העץ הבינארי.

דוגמה לעץ בינארי

סוגי עץ בינארי

ישנם את הסוגים הבאים של עץ בינארי במבנה הנתונים:

1. עץ מלא / בינארי למהדרין
2. השלם עץ בינארי
3. עץ בינארי מושלם
4. איזון עץ בינארי
5. עץ בינארי מושרש
6. עץ בינארי מנוון/פתולוגי
7. עץ בינארי מורחב
8. עץ בינארי עקום
   1. עץ בינארי מוטה שמאלה
   2. עץ בינארי מוטה ימינה
9. עץ בינארי מושחל
   1. עץ בינארי עם חוטים בודדים
   2. עץ בינארי עם חוטים כפולים

יישום עץ בינארי בג'אווה

ישנן דרכים רבות ליישם עץ בינארי. בחלק זה, ניישם עץ בינארי באמצעות מבנה הנתונים LinkedList. יחד איתו, ניישם גם את סדרי המעבר, חיפוש צומת ונכניס צומת בעץ בינארי.

ראג'יניקנת'

יישום של עץ בינארי באמצעות LinkedList

אַלגוֹרִיתְם

הגדר מחלקה Node המכילה שלוש תכונות, כלומר: נתונים משמאל וימין. כאן, שמאל מייצג את הילד השמאלי של הצומת וימין מייצג את הילד הימני של הצומת.

• כאשר צומת נוצר, הנתונים יעברו לתכונת הנתונים של הצומת וגם שמאל וימין יוגדרו ל- null.
• הגדר מחלקה אחרת שיש לה שורש תכונה.
• שורש מייצג את צומת השורש של העץ ואתחול אותו ל- null.

לְהַכנִיס()יוסיף צומת חדש לעץ:
• זה בודק אם השורש ריק, מה שאומר שהעץ ריק. זה יוסיף את הצומת החדש כשורש.
• אחרת, זה יוסיף שורש לתור.
• הצומת המשתנה מייצג את הצומת הנוכחי.
• ראשית, הוא בודק אם לצומת יש ילד שמאל וימין. אם כן, זה יוסיף את שני הצמתים לתור.
• אם הילד השמאלי אינו נוכח, הוא יוסיף את הצומת החדש בתור הילד השמאלי.
• אם השמאל קיים, הוא יוסיף את הצומת החדש בתור הילד הימני.
בסדר()יציג צמתים של העץ בצורה לא מסודרת.
• הוא חוצה את כל העץ ואז מדפיס ילד שמאל ואחריו שורש ואחריו הילד הימני.

BinarySearchTree.java

 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 > 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('Total number of possible Binary Search Trees with given key: ' + 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('Building tree with root value ' + rootnode.value); System.out.println('================================='); 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(' Inserted ' + value + ' to right of Node ' + node.value); node.right = new Node(value); } } } } 

תְפוּקָה:

string.format java

 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

אַלגוֹרִיתְם

1. החל מהשורש, מצא את הצומת העמוק והימני ביותר בעץ ובצומת בינאריים שאנו רוצים למחוק.
2. החלף את הנתונים של הצומת הימני העמוק ביותר בצומת שיימחק.
3. לאחר מכן מחק את הצומת העמוק ביותר הימני.

שקול את הדמות הבאה.

מחקNode.java

25 ג עד ק

 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 + ' '); 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 && 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('Inorder traversal before deletion: '); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print('
Inorder traversal after deletion: '); inorder(root); } } 

תְפוּקָה:

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

תוכנית Java לחיפוש צומת בעץ בינארי

אַלגוֹרִיתְם

• הגדר מחלקה Node שיש לה שלוש תכונות, כלומר: נתונים משמאל וימין. כאן, שמאל מייצג את הילד השמאלי של הצומת וימין מייצג את הילד הימני של הצומת.
• כאשר צומת נוצר, הנתונים יעברו לתכונת הנתונים של הצומת וגם שמאל וימין יוגדרו ל- null.
• הגדר מחלקה אחרת שיש לה שני תכונות שורש ודגל.
  1. שורש מייצג את צומת השורש של העץ ומאתחל אותו ל- null.
  2. הדגל ישמש כדי לבדוק אם הצומת הנתון קיים בעץ או לא. בתחילה, הוא יוגדר כ-false.

searchNode()יחפש צומת מסוים בעץ הבינארי:
• זה בודק אם השורש ריק, מה שאומר שהעץ ריק.
• אם העץ לא ריק, הוא ישווה את נתוני הזמפ' עם הערך. אם הם שווים, זה יקבע את הדגל ל-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('Tree is empty'); } 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 && temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false && 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('Element is present in the binary tree.'); else System.out.println('Element is not present in the binary tree.'); } } 

תְפוּקָה:

 Element is present in the binary tree. 

חצת עצים בינאריים

הערה: מלבד שלושת המעברים לעיל, יש סדר חצייה נוסף שנקרא מעבר גבול.

תוכנית ג'אווה למעבר הזמנה, הזמנה מראש ומעבר הזמנה לאחר הזמנה

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 + ' '); } } 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('Inorder traversal of binary tree'); bst.inOrder(bst.root); System.out.println(); System.out.println('Preorder traversal of binary tree'); bst.preOrder(bst.root); System.out.println(); System.out.println('Postorder traversal of binary tree'); 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('Tree is empty'); return 0; } else { int leftMax, rightMax; //Max will store temp'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('Largest element in the binary tree: ' + bt.largestElement(bt.root)); } } 

תְפוּקָה:

רשימת מערך ממוינת

 Largest element in the binary tree: 99 

תוכנית Java למציאת הצומת הקטן ביותר בעץ בינארי

אַלגוֹרִיתְם

1. הגדר מחלקה Node שיש לה שלוש תכונות כלומר: נתונים, שמאל וימין. כאן, שמאל מייצג את הילד השמאלי של הצומת וימין מייצג את הילד הימני של הצומת.
2. כאשר צומת נוצר, הנתונים יעברו לתכונת הנתונים של הצומת וגם שמאל וימין יוגדרו ל- null.
3. הגדר מחלקה אחרת שיש לה שורש תכונה.
   שורשמייצגים את צומת השורש של העץ ומאתחלים אותו ל- null.

smallestElement()יגלה את הצומת הקטן ביותר בעץ הבינארי:
1. זה בודק אם השורש הוא ריק , כלומר העץ ריק.
2. אם העץ אינו ריק, הגדר משתנה min שיאחסן את נתוני הטמפ'.
3. גלה את הצומת המינימלי בתת-עץ השמאלי על ידי קריאה רקורסיבית ()smallestElement. אחסן את הערך הזה ב-leftMin. השווה את הערך של min עם leftMin ואחסן את המינימום של שניים עד דקות.
4. גלה את הצומת המינימלי בתת-עץ הימני על ידי קריאה רקורסיבית ()smallestElement. אחסן את הערך הזה ב-rightMin. השווה את הערך של min עם rightMin ואחסן את המקסימום של שניים עד דקות.
5. בסוף, 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('Tree is empty'); return 0; } else { int leftMin, rightMin; //Min will store temp'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('Smallest element in the binary tree: ' + bt.smallestElement(bt.root)); } } 

תְפוּקָה:

 Smallest element in the binary tree: 1 

תוכנית Java למציאת הרוחב המרבי של עץ בינארי

אַלגוֹרִיתְם

1. הגדר מחלקה Node שיש לה שלוש תכונות, כלומר: נתונים משמאל וימין. כאן, שמאל מייצג את הילד השמאלי של הצומת וימין מייצג את הילד הימני של הצומת.
2. כאשר צומת נוצר, הנתונים יעברו לתכונת הנתונים של הצומת וגם שמאל וימין יוגדרו ל- null.
3. הגדר מחלקה אחרת שיש לה שורש תכונה.
   שורשמייצג את צומת השורש של העץ ומאתחל אותו ל- null.

1. Variable maxWidth יאחסן את המספר המרבי של צמתים הקיימים בכל רמה.
2. התור משמש למעבר עץ בינארי ברמה ברמה.
3. זה בודק אם השורש ריק, מה שאומר שהעץ ריק.
4. אם לא, הוסף את צומת השורש לתור. nodesInLevel משתנים עוקב אחר מספר הצמתים בכל רמה.
5. אם nodesInLevel > 0, הסר את הצומת מחזית התור והוסף את הצאצא השמאלי והימני שלו לתור. עבור האיטרציה הראשונה, צומת 1 יוסר והילדים שלו צמתים 2 ו-3 יתווספו לתור. באיטרציה השנייה, צומת 2 יוסר, ילדיו 4 ו-5 יתווספו לתור וכן הלאה.
6. MaxWidth יאחסן את max(maxWidth, nodesInLevel). אז, בכל נקודת זמן נתונה, הוא ייצג את המספר המרבי של צמתים.
7. זה יימשך עד שיעברו את כל רמות העץ.

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('Tree is empty'); 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'll add left and right child of the node to the queue while(nodesInLevel > 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('Maximum width of the binary tree: ' + bt.findMaximumWidth()); } } 

תְפוּקָה:

 Maximum width of the binary tree: 4