数据结构树高度

In this tutorial, we’ll be discussing Binary Trees. We’ll see how to calculate the height of a tree data structure recursively as well as iteratively.

在本教程中，我们将讨论二叉树。 我们将看到如何递归和迭代地计算树数据结构的高度。

二叉树 (Binary Trees)

Binary Trees are a data structure in which data is stored in a hierarchical manner rather than linear (as it is done in and Arrays).

二叉树是一种数据结构，其中的数据是以分层方式而不是线性方式存储的（就像在和Arrays中一样）。

A Binary tree data structure consists of nodes. Each node holds the data along with the reference to the child pointers (left and right).

二叉树数据结构由节点组成。 每个节点都保存数据以及对子指针（左和右）的引用。

The root of the binary tree is the topmost node. (So opposite of an actual living tree).

二叉树的根是最顶层的节点。 （与实际的活树相反）。

Following is an illustration of a tree with some nodes.

以下是带有某些节点的树的图示。

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.

节点的高度是从该节点到叶子的最长的向下路径的长度。 根的高度是树的高度。

So, in order to calculate the height of the tree, we need to go through each node of the tree in order to obtain all permutations and combinations.

因此，为了计算树的高度，我们需要遍历树的每个节点以获得所有排列和组合。

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

有两种计算树高的方法。

• Recursive Way
  递归方式
• Iterative Way
  迭代方式

树的高度–递归 (Height of a Tree – Recursively)

Recursion involves calculating the results of the subproblems and returning it back to the parent problem.

递归涉及计算子问题的结果并将其返回给父问题。

Following illustration shows the number of permutations to calculate the height of the binary tree.

下图显示了计算二叉树高度的排列数量。

Let’s write the Java program to calculate the height of the tree recursively. First of all, we will have a basic implementation of the Tree data structure.

让我们编写Java程序来递归计算树的高度。 首先，我们将对Tree数据结构进行基本的实现。

package com.journaldev.tree.height;public class BinaryTree {	TreeNode root;	public static class TreeNode {		TreeNode left;		TreeNode right;		Object data;		TreeNode(Object data) {			this.data = data;			left = right = null;		}	}}

Let’s see the code for finding the height of the tree using recursion.

让我们看一下使用递归查找树的高度的代码。

package com.journaldev.tree.height;import com.journaldev.tree.height.BinaryTree.TreeNode;public class HeightOfTree {	public static void main(String[] args) {		BinaryTree binaryTree = new BinaryTree();		/**		 * Binary Tree in our example, height = 2		 * 		1		(Root)		 * 	  2	  3		(Level 1)		 *  4    	 5		(Level 2)		 */		binaryTree.root = new TreeNode(1);		binaryTree.root.left = new TreeNode(2);		binaryTree.root.right = new TreeNode(3);		binaryTree.root.left.left = new TreeNode(4);		binaryTree.root.right.left = new TreeNode(5);		int heightOfTree = height(binaryTree.root);		System.out.printf("Height of tree is %d", heightOfTree);	}		public static int height(TreeNode root) {		if (root == null)			return -1;		int leftHeight = height(root.left);		int rightHeight = height(root.right);		return Math.max(leftHeight, rightHeight) + 1;	}}

So, in the above code, once we reach the bottom-most child node, we add one to the height of the tree and return the result to the previous call.

因此，在上面的代码中，一旦到达最底层的子节点，便将其加到树的高度，然后将结果返回到上一个调用。

Output: Height of tree is 2

输出： 树的高度为2

Let’s now do the same thing non-recursively.

现在让我们以非递归方式执行相同的操作。

树的高度–迭代 (Height of the Tree – Iteratively)

To calculate the height of the tree iteratively, we simply need to calculate the number of levels in the tree.

要迭代计算树的高度，我们只需要计算树中的级别数。

Following is the iterative program to calculate the height of the tree.

以下是计算树的高度的迭代程序。

public static int heightIteratively(TreeNode root) {    if (root == null)        return -1;    Queue
    
      queue = new LinkedList<>();    queue.add(root);    int height = -1;    while (!queue.isEmpty()) {        int size = queue.size();        height++;        while (size > 0) {            TreeNode treeNode = queue.remove();            if (treeNode.left != null)                queue.add(treeNode.left);            if (treeNode.right != null)                queue.add(treeNode.right);                        size--;        }    }    return height;}
    

The above code keeps running until the queue isn’t empty. And also, it keeps adding all the elements at the next level while removing the current level items from the queue.

上面的代码一直运行，直到队列不为空。 而且，它还在从队列中删除当前级别项目的同时，继续在下一级别添加所有元素。

翻译自:

数据结构树高度