Поиск высоты дерева java

Высота бинарного дерева

Я хочу знать логические причины этого кода. Как люди придумали это? Есть ли у некоторых индуктивные доказательства? Кроме того, я думал о том, что просто делал BFS с корнем двоичного дерева в качестве аргумента, чтобы получить высоту двоичного дерева. Является ли предыдущий подход лучше, чем мой? Почему?

4 ответа

Дети листовых узлов null . Поэтому это говорит о том, что после того, как мы пройдем мимо листьев, больше нет узлов.

Если мы не проходим мимо листовых узлов, мы должны вычислить высоту, и этот код делает это рекурсивно.

Текущая node добавляет высоту 1 к высоте вычисляемого поддерева.

 Math.max(heightOfBinaryTree(node.left), heightOfBinaryTree(node.right)); 

Мы рекурсивно вычисляем высоту левого поддерева ( node.left ) и правого поддерева ( node.right ). Поскольку мы вычисляем максимальную глубину, мы берем максимум этих двух глубин.

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

Здесь представлено графическое представление высоты дерева из этого документа. h — высота дерева, hl и hr — это высоты левого и правого поддеревьев соответственно.

Кроме того, я думал о том, чтобы просто BFS с корнем двоичного дерева как аргумент, чтобы получить высоту бинарное дерево. Является ли предыдущий лучше, чем мой? Почему?

Код, который вы предоставили, является формой DFS. Поскольку вам нужно обработать все узлы, чтобы найти высоту дерева, разница между DFS и BFS не будет разницу во времени выполнения, хотя BFS будет использовать память O (N), в то время как DFS будет использовать память O (logN). BFS также немного сложнее кодировать, поскольку для него требуется очередь, в то время как DFS использует «встроенный» рекурсивный стек.

Источник

How to find a height of a tree data structure in Java

The Tree is a non linear data structure consisting of nodes and edges. Depending upon the type of tree, it can have 0 or more child nodes. For example, Each node in a binary tree can have 0, 1 or 2 child nodes. Whereas, the B+ tree of order 5 can have 4 data values in each node and maximum 5 child nodes attached to a node.

Here, we will first construct a binary search tree in Java. Thereafter, we will write a java code to find the height of the binary tree. The height of a node is the length of the longest downward path from a root node till the leaf node. The height of the root is the height of the tree. Now, in order to calculate the height of the tree, we have to traverse through each node of the tree in order to get all permutations and combinations.

There are two ways to calculate the height of a tree.

Constructing a Binary Search Tree

In order to construct a binary search tree, we need to make sure that none of the properties of binary search tree is violated while inserting a node.
Here, the each call to the insertion method will insert one node to a binary search tree. The first call to insertion will make that node as a root node. All the other insertions will take place considering the value of root node. Here, we will construct the binary search tree as shown in the figure below.

The code below shows the insertion function which places the node in a tree such that none of the properties of binary search tree is violated.

// Creating a node class class Node < Node left; Node right; int data; // Initializing to null Node() < left = null; right = null; data = -1; >> // Inserting a node in Binary search tree public class Main < public static void main(String[] args) < // Creating a root node Node root = new Node(); Main m = new Main(); // Calling insertion function to insert some nodes m.insertion(root, 10); m.insertion(root, 5); m.insertion(root, 20); m.insertion(root, 30); m.insertion(root, 25); m.insertion(root, 2); >void insertion(Node root, int val) < // Condition if this is a first node then it will be considered as a root if (root.data == -1) < System.out.println(val + " Inserted as root"); root.data = val; // Else part will be executed for all the other insertions >else < // Pointer to move around tree to search for a place of new node Node p = root; // Creating a new node and writing a value in the data part Node n = new Node(); n.data = val; // Iterating to search for an appropriate place of new node while (true) < // if val is less than the current node p indicates that new node will be inserted on left subtree if (val < p.data) < if (p.left == null) < System.out.println(val + " Inserted on left of " + p.data); p.left = n; break; >else < p = p.left; >> // if val is greater than the current node p indicates that new node will be inserted on right subtree else < if (p.right == null) < System.out.println(val + " Inserted on right of" + p.data); p.right = n; break; >else < p = p.right; >> > > > >

10 Inserted as root 5 Inserted on left of 10 20 Inserted on right of10 30 Inserted on right of20 25 Inserted on left of 30 2 Inserted on left of 5

Different ways to finding the height of a tree

Method-1: Recursive Approach to find the Height of a Tree

When we want to find the height of a tree. Firstly, we will need to calculate the height of it’s left subtree and right subtree recursively. Now, each of these subtrees may have a left and right subtree attached, hence recursion would apply until the subtrees are null. Finally, we will compare the heights of the left and right subtree and return the maximum of two. Thereafter, we will add 1 to them as that is the height between the topmost node and its children to obtain the correct height of a tree.

Note that we will add the height function to the code we have written to construct binary search tree and call it from the main function. Here, for the tree shown above we will get the height of tree as 3.

Method-2: Iterative Approach to find the Height of a Tree

In this approach, to find the height of a tree we will calculate the number of levels in tree. So, we will use Queue to store the child nodes while traversing across the tree. We will create a queue and add root to it along with the child nodes of the root. Thereafter, we traverse along the tree and pop the node from the queue and traverse on tree. For each iteration we will pop the latest element added to the queue and add the elements of the next level to the queue. We will perform this until the queue size becomes zero. Here, we will add 1 for each traversed level.

Note that we will add the height function to the code we have written to construct binary search tree and call it from the main function. Here, for the tree shown above we will get the height of tree as 3.

int height1(Node root) < // Return if reached null node or last level if (root == null) return -1; // Creating an empty queue Queue queue = new LinkedList < >(); // Adding root to the queue and initialize the height queue.add(root); int height = -1; // Traverse a tree till queue is empty while (!queue.isEmpty()) < int size = queue.size(); height++; while (size >0) < Node Node = queue.remove(); if (Node.left != null) queue.add(Node.left); if (Node.right != null) queue.add(Node.right); size--; >> // return the height to the main function return height; >

Summary

The knowledge of obtaining the height of the tree is very useful while working on real time applications. In many situations, we will need to get the height of a tree. For example, while constructing an AVL tree, we will need to get the height of tree multiple times. In this tutorial, we covered creation, insertion and finding the height of a tree using both iterative and recursive approach with java code. As per the requirement of an application, we can choose an appropriate approach to find the height of a tree. We learned in detail about this with an example.

All in all, this tutorial, covers everything that you need to know in order to have a clear view on finding height of a tree using Java.

References

Didn’t find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment Cancel reply

Java Tutorial

• Set Up Java Environment
  • Set Up Java on Linux
  • Set up Java with BlueJ IDE
  • Set up Java with VSC IDE
  • Set up Java with Eclipse IDE
  • Java Multiline Comments
  • Java Variables
  • Java Global Variables
  • Java Date & Time Format
  • Different Java Data Types
  • Java Booleans
  • Java Strings
  • Java Array
  • Java Byte
  • Java convert list to map
  • Java convert double to string
  • Java convert String to Date
  • Java convert Set to List
  • Java convert char to int
  • Java convert long to string
  • Java Operators Introduction
  • Java Boolean Operators
  • Java Relational Operators
  • Java Arithmetic Operators
  • Java Bitwise Operators
  • Java Unary Operators
  • Java Logical Operators
  • Java XOR (^) Operator
  • Java Switch Statement
  • Java If Else Statement
  • Java While Loop
  • Java For / For Each Loop
  • Java Break Continue
  • Java Nested Loops
  • Java throw exception
  • Java Try Catch
  • Java Accessor and Mutator Methods
  • Java main() Method
  • IndexOf() Java Method
  • Java ListIterator() Method
  • Java create & write to file
  • Java read file
  • Java Parameter
  • Java Argument
  • Java Optional Parameters
  • Java Arguments vs Parameters
  • Java Arrays.asList
  • Java HashSet
  • Java Math
  • Java HashMap vs Hashtable vs HashSet
  • Java LinkedList
  • Linked List Cycle
  • Java List vs LinkedList
  • Java ArrayList vs LinkedList

  Источник

  Height of a binary tree

  I want to know the logical reasoning behind this code. How did people come up with it? Does some have an inductive proof? Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

  5 Answers 5

  The children of leaf nodes are null . Therefore this is saying that once we’ve gone past the leaves, there are no further nodes.

  If we are not past the leaf nodes, we have to calculate the height and this code does so recursively.

  The current node adds a height of 1 to the height of the subtree currently being calculated.

   Math.max(heightOfBinaryTree(node.left), heightOfBinaryTree(node.right)); 

  We recursively calculate the height of the left subtree ( node.left ) and right subtree ( node.right ). Since we’re calculating the maximum depth, we take the maximum of these two depths.

  I’ve shown above that the recursive function is correct. So calling the function on the parent node will calculate the depth of the entire tree.

  Here’s a graphical representation of the height of a tree from this document. h is the height of the tree, hl and hr are the heights of the left and right subtrees respectively.

  

  Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?

  The code you provided is a form of DFS. Since you have to process all nodes to find the height of the tree, there will be no runtime difference between DFS and BFS, although BFS will use O(N) memory while DFS will use O(logN) memory. BFS is also slightly more complex to code, since it requires a queue while DFS makes use of the «built-in» recursive stack.

  Источник

  Найдите высоту бинарного дерева, представленного родительским массивом

  Учитывая массив, представляющий отношения родитель-потомок в двоичном дереве, найдите высоту дерева, не строя его. Отношения между родителями и детьми определяются (A[i], i) для каждого индекса i в массиве A . Значение корневого узла будет i если -1 присутствует в индексе i в массиве.

  Глубина “узла” — это общее количество ребер от узла до корневого узла дерева. Корень — это единственный узел, глубина которого равна 0.

  Высота “узла” — это общее количество ребер на самом длинном пути от узла до листа. Высота “дерева” будет высотой его корневого узла или, что то же самое, глубиной его самого глубокого узла. Листовой узел будет иметь высоту 0.

  • -1 присутствует в индексе 0, что означает, что корень бинарного дерева является узлом 0.
  • 0 присутствует в индексах 1 и 2, что означает, что левый и правый потомки узла 0 — это 1 и 2.
  • 1 присутствует в индексе 3, что означает, что левый или правый дочерний элемент узла 1 равен 3.
  • 2 присутствует в индексах 4 и 5, что означает, что левый и правый потомки узла 2 — это 4 и 5.
  • 4 присутствует в индексах 6 и 7, что означает, что левый и правый потомки узла 4 — это 6 и 7.

  Соответствующее бинарное дерево:

  

  Связанный пост:

  Простым решением было бы построить двоичное дерево с использованием родительского массива, как показано в сообщении выше. После того, как дерево построено, рассчитайте его высоту. Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n размер родительского массива. Однако, согласно ограничениям задачи, высота должна рассчитываться без построения дерева.

  Идея состоит в том, чтобы вычислить глубину каждого узла, используя рекурсия и вернуть максимальную найденную глубину. Поскольку глубина узла — это общее количество ребер от узла к корню, нам нужно проследить путь узла к корневому узлу, используя отношение родитель-потомок. Мы можем сделать это, рекурсивно обходя родительский массив. Алгоритм может быть реализован следующим образом на C, Java и Python:

  C

  результат:

  The height of the binary tree is 3

  Java

  результат:

  The height of the binary tree is 3

  Python

  результат:

  The height of the binary tree is 3

  Временная сложность приведенного выше решения равна O(n 2 ) , куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(h) для стека вызовов, где h это высота дерева.

  Обратите внимание, что findDepth() рутина имеет оптимальное основание поскольку его можно рекурсивно разбить на более мелкие подпрограммы, т.е. findDepth(i) = 1 + findDepth(parent[i]) . Он также демонстрирует перекрывающиеся подзадачи так как одна и та же подзадача решается снова и снова.

  Мы знаем, что задачи, имеющие оптимальную подструктуру и перекрывающиеся подзадачи, могут быть решены с помощью динамического программирования. Ниже приведена реализация динамического программирования на C, Java и Python, где решения подзадач памятка, а не вычисляется повторно. Решение использует вспомогательный массив для хранения глубины каждого узла.

  Источник

  Читайте также:  Виды домашних растений деревьев