1. 数据结构与算法/

·260 字·2 分钟· loading
demo007x
作者
demo007x

获取二叉树每一层的最小元素
#

给定一个包含 n 个节点的二叉树,任务是打印二叉树每一层的最小元素

例子:

输入 :
          7
         / \
        6   5
       / \ / \
      4  3 2  1  
       
输出 每个层级的最低数值是:
第0层 = 7
第1层 = 5
第2层 = 1

输入 :  
           7
          / \
        16   1
       /  \      
      4   13    

输出 :每个层级的最低数值是:
第0层 = 7
第1层 = 1
第2层 = 4

方法一:使用中序遍历
#

方法: 这个想法是以有序方式递归遍历树。根被认为位于第零层。首先,找到树的高度并将其存储到 res 中。res 数组存储二叉树每一层中的每个最小元素。

<script>

	//JavaScript程序打印最小元素的每一级二进制树。
	
	let INT_MAX = 10e6;

	// 定义二叉树的节点
	class Node
	{
		constructor(data) {
		this.left = null;
		this.right = null;
		this.data = data;
		}
	}

	// 返回树的高度
	function heightoftree(root)
	{
		if (root == null)
			return 0;

		let left = heightoftree(root.left);
		let right = heightoftree(root.right);

		return ((left > right ? left : right) + 1);
	}

	// 订单遍历 搜索每个级别中的最小元素 将其存储到矢量数组中。
	function printPerLevelMinimum(root, res, level)
	{
		if (root != null)
		{
			printPerLevelMinimum(root.left, res, level + 1);

			if (root.data < res[level])
				res[level] = root.data;

			printPerLevelMinimum(root.right, res, level + 1);
		}
	}

	function perLevelMinimumUtility(root)
	{

		//向量数组大小的树的高度
		let n = heightoftree(root), i;

		//存储每个级别的所有最小值的向量
		let res = new Array(n);
		res.fill(INT_MAX);

		//使用有序遍历保存每个级别的最小值
		printPerLevelMinimum(root, res, 0);

		//打印每个级别的最小值
		document.write("Every level minimum is" + "</br>");
		for (i = 0; i < n; i++)
		{
			document.write("level " + i +
							" min is = " +
							res[i] + "</br>");
		}
	}

	//用于创建新树节点
	function newNode(data)
	{
		let temp = new Node(data);
		temp.data = data;
		temp.left = temp.right = null;

		return temp;
	}
	
	//让我们创建所示的二叉树
	let root = newNode(7);
	root.left = newNode(6);
	root.right = newNode(5);
	root.left.left = newNode(4);
	root.left.right = newNode(3);
	root.right.left = newNode(2);
	root.right.right = newNode(1);

	/*
  		 7
		 /   \
		6	    5
	/ \	   / \
 4  3   2   1		 
 
 */
	perLevelMinimumUtility(root);

</script>