不是VIP会员,不能显示答案

题目解答

题目:
(笛卡尔树)对于一个给定的两两不等的正整数序列,笛卡尔树是这样的一棵二叉树:首先,它是一个最小堆,即除了根结点外,每个结点的权值都大于父结点的权值;其次,它的中序遍历恰好就是给定的序列。例如,对于序列7、2、12、1、10、5、15、3,下图就是一棵树对应的笛卡尔树。现输入序列的规模n(1<=n<100)和序列的n个元素,试求其对应的笛卡尔树的深度d(根节点深度为1),以及有多少个叶节点的深度为d。
const
	SIZE = 100;
	INFINITY = 1000000;
 
var
	n , maxDeep, num , i : integer;
	a : array[1..SIZE] of integer;
 
procedure solve(left , right , deep : integer);
var
	i,j,min: integer;
begin
	if deep>maxDeep then
	begin
		maxDeep :=deep;
		num := 1;
	end
	else if deep=maxDeep then
	inc(num)	;
	
	min := INFINITY;
	for i := left to right do
		if min > a[i] then
		begin
			min := a[i];
			j:=i ;
		end;
	if left < j then
		solve(left,j-1,deep+1) ;
	if j<right then
	solve(j+1,right,deep+1);
end;
 
begin
	readln(n);
	for i := 1 to n do
		read(a[i]);
	maxDeep:=0;
	solve( 1, n, 1);
	writeln(maxDeep, ‘ ‘, num);
end.
考点: 0
分析:
解答: 这题很容易,只要知道啥是中序遍历就能解。看solve这个过程,就是在left到right这个树中找到这个数的根然后根左根右分别继续solve。deep,字面就是深度,maxDeep就是最大深度,看输出,还有个num,这就是最大深度的叶节点的个数了。所以很容易得出第一空①。
     然后②那个地方就是找最小值,也就是这个子树的根,看程序,下面用到了j,而上面没有一处用j,所以这里应该有个j,用来记录根的位置。然后下面分治,根据中序遍历的性质,根的左边是左子树,右边是右子树,分别再solve进去,深度加一。
评论:
老师: 0