树形数据结构的高度

2 年 ago
清, 扬
2 minutes

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

二叉树

二叉树是一种数据结构，其中数据以分层的方式存储，而不是线性存储（如链表和数组）。 二叉树数据结构由节点组成。 每个节点保存数据以及对子节点（左侧和右侧）的引用。 二叉树的根节点是最顶层的节点（与实际生活中的树相反）。 下面是一棵具有一些节点的树的示例。 节点的高度是从该节点到叶子节点的最长向下路径的长度。 根节点的高度是整个树的高度。 因此，为了计算树的高度，我们需要遍历树的每个节点以获取所有的排列和组合。 有两种计算树高度的方法。

  • Recursive Way
  • Iterative Way

树的高度 – 递归方式

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

步骤涉及：

    要递归地计算树的高度，我们需要递归地找到它的左子树和右子树的高度，并将它们加一（即顶层节点与其子节点之间的高度）。每个子树本身可能有左子树和右子树，因此递归将一直应用到子树为空为止。空树节点的高度为-1。最后，我们将比较左子树和右子树的高度，并返回较大的那个。

下面的图例显示了计算二叉树高度的排列数目。让我们编写递归计算树高度的Java程序。首先，我们将实现基本的树数据结构。

package com.Olivia.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;
		}
	}
}

让我们来看看使用递归寻找树的高度的代码。

package com.Olivia.tree.height;

import com.Olivia.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;
	}
}

所以，在上述代码中，一旦我们到达最底层的子节点，我们将树的高度加一，并将结果返回给上一个调用。输出：树的高度为2。现在让我们以非递归的方式做同样的事情。

树的高度 – 迭代方式

为了迭代计算树的高度，我们只需计算树的层级数即可。

步骤参与

    1. 创建一个队列并将树的根节点加入队列。

 

    1. 从队列中弹出节点，并在将其子节点添加到队列时遍历队列下方。

 

    1. 在每次迭代中，弹出最新添加到队列的元素，并将下一层级的元素（属于此元素的）添加到队列中。

 

    1. 重复以上步骤直到队列大小变为零。这意味着下一层级没有任何元素。

 

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

以下是用迭代方法计算树高的程序。

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;
}

上述的代码会一直运行，直到队列为空为止。同时，它会在移除当前层级的元素时，不断添加下一层级的所有元素到队列中。

时间复杂度为O(n)。空间复杂度为O(1)。

您可以从我们的GitHub存储库中检查完整的代码和更多DS和算法示例。

bannerAds