Chương trình Java để thực hiện duyệt cây inorder

Trong bài viết này, chúng ta sẽ hiểu cách thực hiện chuyển qua cây inorder. Trong InOrder traversal, mỗi nút được xử lý giữa các cây con. Nói một cách đơn giản hơn, hãy truy cập vào cây con bên trái, nút và sau đó là cây con bên phải.

Dưới đây là một minh chứng về điều tương tự -

Giả sử đầu vào của chúng tôi là -

Run the program

Đầu ra mong muốn sẽ là -

The In-Order traversal of the tree_object is:
5->12->6->1->9->

Thuật toán

Step 1 - START
Step 2 - A class with the data specifications is previously defined.
Step 3 - Create a new instance of the class.
Step 4 - Initialize the instance with relevant values.
Step 5 - Invoke the method to perform inorder traversal.
Step 6 - Display the result
Step 7 - Stop

Ví dụ 1

Ở đây, chúng tôi đã sử dụng phương pháp đệ quy để duyệt theo thứ tự.

class Node {
   int item;
   Node left_node, right_node;
   public Node(int key) {
      item = key;
      left_node = right_node = null;
   }
}
public class Tree {
   Node root;
   Tree() {
      root = null;
   }
   void inOrder(Node node) {
      if (node == null)
         return;
      inOrder(node.left_node);
      System.out.print(node.item + "->");
      inOrder(node.right_node);
   }
   public static void main(String[] args) {
      Tree tree_object = new Tree();
      System.out.println("A tree_object object is defined: ");
      tree_object.root = new Node(1);
      tree_object.root.left_node = new Node(12);
      tree_object.root.right_node = new Node(9);
      tree_object.root.left_node.left_node = new Node(5);
      tree_object.root.left_node.right_node = new Node(6);
      System.out.println("The In-Order traversal of the tree_object is: ");
      tree_object.inOrder(tree_object.root);
   }
}

Đầu ra

A tree_object object is defined:
The In-Order traversal of the tree_object is:
5->12->6->1->9->

Ví dụ 2

Ở đây, chúng tôi đang sử dụng phương pháp không đệ quy để duyệt theo thứ tự.

import java.util.Stack;
class Node {
   int data;
   Node left_node, right_node;
   public Node(int item) {
      data = item;
      left_node = right_node = null;
   }
}
class tree {
   Node root;
   void inorder() {
      if (root == null)
         return;
      Stack<Node> temp_stack = new Stack<Node>();
      Node current_node = root;
      while (current_node != null || temp_stack.size() > 0) {
         while (current_node != null) {
            temp_stack.push(current_node);
            current_node = current_node.left_node;
         }
         current_node = temp_stack.pop();
         System.out.print(current_node.data + " ");
         current_node = current_node.right_node;
      }
   }
   public static void main(String args[]) {
      tree tree = new tree();
      System.out.println("A tree_object object is defined: ");
      tree.root = new Node(1);
      tree.root.left_node = new Node(2);
      tree.root.right_node = new Node(3);
      tree.root.left_node.left_node = new Node(4);
      tree.root.left_node.right_node = new Node(5);
      System.out.println("The In-Order traversal of the tree_object is: ");
      tree.inorder();
   }
}

Đầu ra

A tree_object object is defined:
The In-Order traversal of the tree_object is:
4 2 5 1 3