Найти глубину дерева java

Поиск в ширину (BFS) и поиск в глубину (DFS) для двоичных деревьев в Java

Поиск в ширину и поиск в глубину — это два метода обхода графов и деревьев. В этом руководстве мы сосредоточимся в основном на обходах BFS и DFS в деревьях.

Что такое поиск в глубину (DFS)?

Алгоритм начинается с корневого узла, а затем исследует каждую ветвь перед возвратом. Он реализован с помощью стеков. Часто при написании кода мы используем стеки рекурсии для возврата. Используя рекурсию, мы можем воспользоваться тем фактом, что левое и правое поддеревья также являются деревьями и имеют одни и те же свойства.

Для двоичных деревьев существует три типа обхода DFS.

Что такое поиск в ширину (BFS)?

Этот алгоритм также начинается с корневого узла, а затем посещает все узлы уровень за уровнем. Это означает, что после корня он проходит по всем прямым дочерним элементам корня. После обхода всех прямых потомков корня он переходит к их потомкам и так далее. Для реализации BFS мы используем очередь.

Для бинарных деревьев у нас есть обход порядка уровней, который следует за BFS.

Реализация BFS и DFS на Java

Пусть рассматриваемое дерево:

Структура класса TreeNode выглядит следующим образом:

1. Обход предварительного заказа

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

Алгоритм обхода предварительного заказа следующий:

1. Обход корня.
2. Вызов preorder() для левого поддерева.
3. Вызов preorder() для правого поддерева.

Обход предварительного заказа дерева выше:

Java-код выглядит следующим образом:

 static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.item + "->"); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); > 

2. Обход по порядку

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

Алгоритм обхода по порядку следующий:

1. Вызов inorder() для левого поддерева.
2. Обход корня.
3. Вызовите inorder() для правого поддерева.

Порядок обхода дерева выше:

Java-код выглядит следующим образом:

 static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.item + "->"); // Traverse right inorder(TreeNode.right); > 

3. Обход после заказа

Обход двоичного дерева в обратном порядке сначала проходит по левому поддереву, затем по правому поддереву и, наконец, по корню.

Алгоритм обхода после заказа следующий:

1. Вызов postorder() для левого поддерева.
2. Вызов postorder() для правого поддерева.
3. Обход корня.

Пост-порядковый обход дерева выше:

Java-код выглядит следующим образом:

 static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.item + "->"); > 

4. Обход по уровням

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

1. Инициализировать пустую очередь
2. Начните с установки temp от имени пользователя root
3. Запускать цикл до тех пор, пока очередь не станет пустой
   1. Печатать данные из временного файла.
   2. Поставить дочерние элементы temp в порядке слева и справа.
   3. Удалить узел из очереди и присвоить его значение переменной temp.

   Обход по порядку уровней дерева выше:

   Java-код выглядит следующим образом:

    static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode temp = queue.poll(); System.out.print(temp.data + " "); /*add left child to the queue */ if (temp.left != null) < queue.add(temp.left); >/*add right right child to the queue */ if (temp.right != null) < queue.add(temp.right); >> > 

   Полная реализация кода BFS и DFS на Java

   Полный код Java приведен ниже:

   package com.JournalDev; import java.util.LinkedList; import java.util.Queue; public class Main < static class TreeNode < int data; TreeNode left, right; public TreeNode(int key) < data = key; left = right = null; >> static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.data + " "); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); >static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.data + " "); // Traverse right inorder(TreeNode.right); >static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.data + " "); >static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); /*add left child to the queue */ if (tempNode.left != null) < queue.add(tempNode.left); >/*add right right child to the queue */ if (tempNode.right != null) < queue.add(tempNode.right); >> > public static void main(String args[]) < TreeNode root = new TreeNode(0); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); System.out.println("Inorder traversal"); inorder(root); System.out.println("\nPreorder traversal "); preorder(root); System.out.println("\nPostorder traversal"); postorder(root); System.out.println("\nLevelorder traversal"); printLevelOrder(root); >> 

   Output : Inorder traversal 3 1 4 0 2 Preorder traversal 0 1 3 4 2 Postorder traversal 3 4 1 2 0 Levelorder traversal 0 1 2 3 4 

   

   Заключение

   Это руководство было посвящено обходам BFS и DFS в двоичных деревьях. Чтобы получить реализацию DFS на C++, обратитесь к этому руководству.

   Источник

   Поиск в ширину (BFS) и поиск в глубину (DFS) для двоичных деревьев в Java

   Поиск в ширину и поиск в глубину — это два метода обхода графов и деревьев. В этом руководстве мы сосредоточимся в основном на обходах BFS и DFS в деревьях.

   Что такое поиск в глубину (DFS)?

   Алгоритм начинается с корневого узла, а затем исследует каждую ветвь перед возвратом. Он реализован с помощью стеков. Часто при написании кода мы используем стеки рекурсии для возврата. Используя рекурсию, мы можем воспользоваться тем фактом, что левое и правое поддеревья также являются деревьями и имеют одни и те же свойства.

   Для двоичных деревьев существует три типа обхода DFS.

   Что такое поиск в ширину (BFS)?

   Этот алгоритм также начинается с корневого узла, а затем посещает все узлы уровень за уровнем. Это означает, что после корня он проходит по всем прямым дочерним элементам корня. После обхода всех прямых потомков корня он переходит к их потомкам и так далее. Для реализации BFS мы используем очередь.

   Для бинарных деревьев у нас есть обход порядка уровней, который следует за BFS.

   Реализация BFS и DFS на Java

   Пусть рассматриваемое дерево:

   

   Структура класса TreeNode выглядит следующим образом:

   1. Обход предварительного заказа

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

   Алгоритм обхода предварительного заказа следующий:

   1. Обход корня.
   2. Вызов preorder() для левого поддерева.
   3. Вызов preorder() для правого поддерева.

   Обход предварительного заказа дерева выше:

   Java-код выглядит следующим образом:

    static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.item + "->"); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); > 

   2. Обход по порядку

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

   Алгоритм обхода по порядку следующий:

   1. Вызов inorder() для левого поддерева.
   2. Обход корня.
   3. Вызовите inorder() для правого поддерева.

   Порядок обхода дерева выше:

   Java-код выглядит следующим образом:

    static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.item + "->"); // Traverse right inorder(TreeNode.right); > 

   3. Обход после заказа

   Обход двоичного дерева в обратном порядке сначала проходит по левому поддереву, затем по правому поддереву и, наконец, по корню.

   Алгоритм обхода после заказа следующий:

   1. Вызов postorder() для левого поддерева.
   2. Вызов postorder() для правого поддерева.
   3. Обход корня.

   Пост-порядковый обход дерева выше:

   Java-код выглядит следующим образом:

    static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.item + "->"); > 

   4. Обход по уровням

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

   1. Инициализировать пустую очередь
   2. Начните с установки temp от имени пользователя root
   3. Запускать цикл до тех пор, пока очередь не станет пустой
      1. Печатать данные из временного файла.
      2. Поставить дочерние элементы temp в порядке слева и справа.
      3. Удалить узел из очереди и присвоить его значение переменной temp.

      Обход по порядку уровней дерева выше:

      Java-код выглядит следующим образом:

       static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode temp = queue.poll(); System.out.print(temp.data + " "); /*add left child to the queue */ if (temp.left != null) < queue.add(temp.left); >/*add right right child to the queue */ if (temp.right != null) < queue.add(temp.right); >> > 

      Полная реализация кода BFS и DFS на Java

      Полный код Java приведен ниже:

      package com.JournalDev; import java.util.LinkedList; import java.util.Queue; public class Main < static class TreeNode < int data; TreeNode left, right; public TreeNode(int key) < data = key; left = right = null; >> static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.data + " "); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); >static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.data + " "); // Traverse right inorder(TreeNode.right); >static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.data + " "); >static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); /*add left child to the queue */ if (tempNode.left != null) < queue.add(tempNode.left); >/*add right right child to the queue */ if (tempNode.right != null) < queue.add(tempNode.right); >> > public static void main(String args[]) < TreeNode root = new TreeNode(0); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); System.out.println("Inorder traversal"); inorder(root); System.out.println("\nPreorder traversal "); preorder(root); System.out.println("\nPostorder traversal"); postorder(root); System.out.println("\nLevelorder traversal"); printLevelOrder(root); >> 

      Output : Inorder traversal 3 1 4 0 2 Preorder traversal 0 1 3 4 2 Postorder traversal 3 4 1 2 0 Levelorder traversal 0 1 2 3 4 

      

      Заключение

      Это руководство было посвящено обходам BFS и DFS в двоичных деревьях. Чтобы получить реализацию DFS на C++, обратитесь к этому руководству.

      Источник

      Поиск глубины дерева в Java

      Мне нужно создать дерево, и найти сумму которая ровняется умножению каждой вершины дерева на глубину.У меня есть два класса Node и Main . В классе Node я объявляю основные функции для роботы с деревом, в классе Main функцией readChildren заполняю дерево, но не знаю как найти глубину самого дерева (дерево не двоичное)

      public class Main < static NodetheNode; public static void main(String[] args) throws IOException < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Enter root value: "); Noderoot = new Node<>(Integer.parseInt(reader.readLine())); System.out.println("Enter childs with coma separator: "); System.out.println("For root element: "); readChildren(root); > public static void readChildren(Node child) throws IOException < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Enter children for " + child.getData() + ": "); String children = reader.readLine(); if (children.isEmpty()) return; String charr[] = children.split(","); int i = 0; for (String ch : charr) < child.addChild(Integer.parseInt(ch)); readChildren(child.getChildren().get(i++)); >> > import java.util.ArrayList; import java.util.List; public class Node < private List children = new ArrayList(); private Node parent = null; private T data = null; public Node(T data) < this.data = data; >public Node(T data, Node parent) < this.data = data; this.parent = parent; >public List getChildren() < return children; >public void setParent(Node parent) < // parent.addChild(this); this.parent = parent; >public void addChild(T data) < Nodechild = new Node(data); child.setParent(this); this.children.add(child); > public void addChild(Node child) < child.setParent(this); this.children.add(child); >public int getChildrenCount() < return this.getChildren().size(); >public T getData() < return this.data; >public void setData(T data) < this.data = data; >public boolean isRoot() < return (this.parent == null); >public boolean isLeaf() < if (this.children.size() == 0) return true; else return false; >public void removeParent() < this.parent = null; >> 

      Источник

      How to calculate the depth of a binary search tree

      I would like to calculate the summation of the depths of each node of a Binary Search Tree. The individual depths of the elements are not already stored.

      Changing the question after people have supplied answers is going to make the original answers seem unrelated to the latest question. Also you can’t Accept two answers. Would be better to ask a new question, i.e. on a new page. You might also want to Accept an answer to the original question.

      10 Answers 10

      int countChildren(Node node)

      And to get the sum of the depths of every child:

      int sumDepthOfAllChildren(Node node, int depth) < if ( node == null ) return 0; // starting to see a pattern? return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + sumDepthOfAllChildren(node.getRight(), depth + 1); >

      Now for a hopefully informative explanation in case this is homework. Counting the number of nodes is quite simple. First of all, if the node isn’t a node ( node == null ) it returns 0. If it is a node, it first counts its self (the 1 ), plus the number of nodes in its left sub-tree plus the number of nodes in its right sub-tree. Another way to think of it is you visit every node via BFS, and add one to the count for every node you visit.

      The Summation of depths is similar, except instead of adding just one for each node, the node adds the depth of its self. And it knows the depth of its self because its parent told it. Each node knows that the depth of it’s children are it’s own depth plus one, so when you get the depth of the left and right children of a node, you tell them their depth is the current node’s depth plus 1.

      And again, if the node isn’t a node, it has no depth. So if you want the sum of the depth of all the root node’s children, you pass in the root node and the root node’s depth like so: sumDepthOfAllChildren(root, 0)

      Recursion is quite useful, it’s just a very different way of thinking about things and takes practice to get accustomed to it

      Источник

      Читайте также:  Какое дерево по гороскопу друидов