林　成

[摘要]首先介绍二叉树的编码情况,然后提出基于编码生成的二叉树算法,介绍它的算法思路、给出算法的具体步骤描述。

[关键词]编码 二叉树 堆

中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0810037-01

二叉树是计算机数据结构与算法分析中重要的非线性数据结构之一,被广泛应用于优先级队列、分支决策、分类学、计算机语言、组合优化、形式文法、图像处理等众多领域。借助于一定的编码方法,我们就可以得到一棵二叉树对应的编码,这样的编码称作“有效的(Feasible)”编码。

一、基于编码的二叉树算法

在堆的生成过程中,对于第k层上的可能符合条件的2k-1个节点值会进行判断和回溯。当k的值不断增大时,2k-1的值也更快地增大,导致第k层上的判断时间也迅速增加。在单个数判断法与层次判断法的基础上,采用子树生成算法可以有效的减少由k的增大带来的枚举生成所有堆所花费的时间。在算法中用到的一维数组:(注:以下所用的除号V/M均为除后取整,如:3/2=1),算法思想如下:

1.数组t,t_left,t_right。组成堆的n个数按从大到小的顺序放在一维数组t中;符合组成左子树条件的n_left个数按从大到小的顺序放在一维数组t_left中;组成右子树的n_right个数按从大到小的顺序放在一维数组t_right中。n_left和n_right的内容是随着左右子树根节点的变化而动态变化的。

2.数组po,po_left,po_right,po_mid。数组po用来表示在生成一个堆的过程中数组t中的某个数是否已经被选择。如po[f]=0。,则说明数组t中t[f]这个元素尚未被选中;如果数组t中的元素t[f]已被选中,则将t[f]这个元素放在堆中的位置,即在堆中所处的节点在顺序存储结构数组t中的编号放在po[f]中。……