Главная » Интересно

Вывод бинарного дерева в Java с примерами кода и решениями

На чтение 4 мин Опубликовано Обновлено 

public void printTree(Node node) {
if (node == null) {
return;
}
System.out.print(node.value + " ");
printTree(node.left);
printTree(node.right);
}



public void printTree(Node node) {
if (node == null) {
return;
}
printTree(node.left);
System.out.print(node.value + " ");
printTree(node.right);
}

Содержание
  1. Что такое бинарное дерево
  2. Примеры кода
  3. Решения

Что такое бинарное дерево

Бинарные деревья используются для различных целей, например, для хранения данных в отсортированном порядке или для решения задач поиска, добавления и удаления элементов. Также они широко используются в компьютерных алгоритмах и структурах данных.

В Java бинарное дерево может быть реализовано с использованием класса, представляющего узел дерева, а также методов для добавления, удаления и обхода этого дерева.

Примеры кода

Пример 1:

Ниже приведен пример реализации класса для бинарного дерева в Java:

class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree(int key) {
root = new Node(key);
}
BinaryTree() {
root = null;
}
void printInorder(Node node) {
if (node == null)
return;
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
void printInorder() {
printInorder(root);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Inorder traversal of binary tree is ");
tree.printInorder();
}
}

Пример 2:

class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree(int key) {
root = new Node(key);
}
BinaryTree() {
root = null;
}
String printTree(Node node) {
String result = "";
if (node != null) {
result += printTree(node.left);
result += node.data + " ";
result += printTree(node.right);
}
return result;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
String treeString = tree.printTree(tree.root);
System.out.println("Binary tree: " + treeString);
}
}

В приведенном выше коде демонстрируется метод printTree, который рекурсивно обходит бинарное дерево в порядке in-order и возвращает его элементы в виде строки.


public void printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
System.out.print(node.value + " ");
printInOrder(node.right);
}
}

В данном примере мы создаем функцию printInOrder, которая принимает в качестве аргумента узел дерева.

наконец, вызывает себя для правого поддерева. Таким образом, функция будет рекурсивно обходить все узлы дерева,


Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
printInOrder(root);

В результате выполнения данного кода будет выведено «4 2 5 1 3», что соответствует порядку инфиксного обхода данного бинарного дерева.

В Java существует несколько способов реализации стека. Один из самых простых способов — использование класса Stack из пакета java.util.


import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeTraversal {
public static void printTree(TreeNode root) {
if (root == null) {
return;
}
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
printTree(root);
}
}

Выходные данные приведенного кода будут:


1
2
4
5
3

Решения

  1. Рекурсивный метод обхода дерева:

    
public void printTree(TreeNode root) {
if (root != null) {
printTree(root.getLeftChild());
System.out.print(root.getData() + " ");
printTree(root.getRightChild());
}
}

  2. Обход дерева в ширину с использованием очереди:

    
public void printTree(TreeNode root) {
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.getData() + " ");
if (current.getLeftChild() != null) {
queue.add(current.getLeftChild());
}
if (current.getRightChild() != null) {
queue.add(current.getRightChild());
}
}
}

  3. Построение строкового представления дерева:

     
     public String treeToString(TreeNode root) {
     if (root == null) {
     return "";
     }
     StringBuilder sb = new StringBuilder();
     sb.append(root.getData());
     String leftChildString = treeToString(root.getLeftChild());
     String rightChildString = treeToString(root.getRightChild());
     if (!leftChildString.isEmpty()
Оцените статью