哈夫曼树中共有 99 个结点，则该树中有（）个叶子结点；若采用二叉链表作为存储结构，则该树中有（）个空指针域

设哈夫曼树中共有 99 个结点，则该树中有（）个叶子结点；若采用二叉链表作为存储结构，则该树中有（）个空指针域
哈夫曼树是正则二叉树，没有度为1的结点，N=N2+1+N0，N0=50，显然第一空是50，但是第二空做题时的答案为51，我填的100，网上找了一些观点看法，

img

第一个50是对的，第二个，二叉链表指向第一个孩子节点和兄弟节点，当没有孩子节点（叶子节点）或者兄弟节点（单节点）出现空域
因为有50个叶子，外加一个单节点，所以51

  • 这个问题的回答你可以参考下: https://ask.csdn.net/questions/366751
  • 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：4-14 还原二叉树 (15分) 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的
  • 除此之外, 这篇博客: 分治算法——求逆序对、n个点中求最近的两个点的距离、快速求解两个矩阵的乘积中的 二、二维平面上有n个点，快速计算出两个距离最近的点对 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • 用循环来做，时间复杂度为O(n^2)，采用分治，降低复杂度。

    #include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

const double INF = 1e20;
const int N = 65535;	// 用于申请数组长度为N

struct Point
{
	int x;
	int y;
}point[N];

int n;
int tmpt[N];	// 用于保存距离 mid 为d的长度中的点

// 按照x坐标从小到大排序Point数组
bool cmpxy(const Point &a, const Point &b)
{
	if(a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

// 按照y坐标从小到大排序Point数组
bool cmpy(const int &a, const int &b)
{
	return point[a].y < point[b].y;
}

// 找到小值输出
double min(double a, double b)
{
	return a < b ? a : b;
}

// 求下标为 i和 j的两点的Point，的距离
double dis(int i, int j)
{
	return sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x)
		+ (point[i].y - point[j].y) * (point[i].y - point[j].y));
}

//最近点对距离，递归求解
double Closest_Pair(int left, int right)
{
	double d = INF;
	if(left == right)	// 最后剩下一个点
		return d;
	if(left + 1 == right)	// 最后剩下两个点
		return dis(left, right);
	int mid = (left + right) >> 1;		// /2
	double d1 = Closest_Pair(left, mid);
	double d2 = Closest_Pair(mid + 1, right);
	d = min(d1, d2);
	int i, j, k = 0;
	for(i = left; i <= right; ++i)
	{
		if(abs(point[mid].x - point[i].x) <= d)
			tmpt[k++] = i;
	}
	sort(tmpt, tmpt + k, cmpy);
	for(i = 0; i < k; ++i)
	{
		for(j = i + 1; j < k && point[tmpt[j]].y - point[tmpt[i]].y < d; ++j)
		{
			double d3 = dis(tmpt[i], tmpt[j]);
			if(d > d3)
				d = d3;
		}
	}
	return d;
}

int main()
{
	cout << "请输入数组对数，并依次输入数组对 : " << endl;
	int n;
	while(1)
	{
		cin >> n;
		if(n == 0)
			break;
		for(int i = 0; i < n; i++)
		{
			cin >> point[i].x >> point[i].y;
		}
		sort(point, point + n, cmpxy);
		cout << "最近的距离为： "<< Closest_Pair(0, (n - 1)/2) << endl;
		cout << endl;
		cout << "如果继续，请输入需要的数组对数，并输入数组对。否则输入 0，退出程序。" << endl;
	}
	cout << "程序结束！" << endl;
	return 0;
}