Question

最优二叉树怎么画

Answer 1

最优二叉树绘画步骤如下：

1，构造森林全是根。

这一步就是把这 n 个点放入结构体数组中：有 n 个点，每一个点用一次，共产生 n-1 个点，所以用到的数组长度为 2n-1。

在实现的时候不用下标为 0 的位置，比较方便。

2，选择两小造新树。

就是在剩下没用过的点找到最小的两个数，即在那些没有父亲的结点中到最小的两个数。这些结点包括树叶也包括新出现的未来的内点。

3，删除两小添新人。

删除两小就是： 给找到的结点 认好父亲，这样就不会在下次中被找到。

添新人就是：给最小的没用过的结点与找到的结点建立联系。

4，重复  2，3操作。

可以发现 我们从 n-1 个结点循环，这样要找的结点正好是 循环变量 i 的前面的结点。

这个思路挺简单的：首先是可以确定树高最高为为 n-1，自己画一下就知道了。这样就可以用 n 给数组赋长了，这里用动态二维数组，比较专业，也可以不用动态，数组开大点就好了。

然后从树叶回溯到根，每一个结点判断一下是左节点还是右节点就好了。

因为由树高可知编码最长为 n-1，这样动用 下标为 0 的位置，可知 n-1 位为 '' ，然后往前赋值就可以了。

最后真正编码长度可以用回溯时的循环次数确定。