数据结构树高度_树数据结构的高度

数据结构树高度

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 LinkedList and Arrays).

二叉树是一种数据结构，其中的数据是以分层方式而不是线性方式存储的（就像在LinkedList和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.

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

Steps involved: 涉及的步骤 ：
  1. To calculate the height of the tree recursively, we need to find the height of it’s left subtree and right subtree recursively and add 1 to them (height between the topmost node and its children).

    要递归计算树的高度，我们需要递归地找到它的左子树和右子树的高度，并将它们的值加1（最高节点及其子节点之间的高度）。
  2. Each of these subtrees could have a left and right subtree themselves, hence recursion would apply until the subtrees are NULL. The height of a null tree node is -1.

    这些子树中的每个子树本身都可以具有左右子树，因此递归将一直应用到子树为NULL为止。 空树节点的高度为-1。
  3. Finally, we’ll compare the heights of the left and right subtree and return the one which is greater.

    最后，我们将比较左右子树的高度，并返回更大的树。

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.

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

Steps involved 涉及的步骤
  1. Create a Queue and add the root of the tree to it.

    创建一个队列并将树的根添加到其中。
  2. Pop the node from the queue and traverse down the queue while adding the child nodes to the queue.

    从队列中弹出节点并遍历队列，同时将子节点添加到队列中。
  3. In each iteration pop, the latest element added to the queue and add the elements of the next level (of this element) to the queue.

    在每个迭代弹出窗口中，最新元素添加到队列中，并将下一级元素（此元素）添加到队列中。
  4. Do this until the queue size becomes zero. That would mean that the next level has zero elements.

    这样做直到队列大小变为零。 那将意味着下一级别具有零个元素。
  5. For every traversed level, add 1.

    对于每个遍历的级别，添加1。

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

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

public static int heightIteratively(TreeNode root) {

    if (root == null)
        return -1;

    Queue<TreeNode> 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.

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


Space Complexity is O(1).
空间复杂度为O（1）。
GitHub Repository. GitHub存储库中检出完整的代码以及更多DS和算法示例。

翻译自: https://www.journaldev.com/23022/height-of-a-tree-data-structure

数据结构树高度