基于编码的二叉树生成算法

林　成

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

[关键词]编码 二叉树 堆

中图分类号: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]中。同样,po_left,po_right分别表示在生成左右子树过程中t left,t right中的某个数是否已经被选择;po_mid用来在左子树生成完成之后,将po和po_left的结果合并,表示在右子树生成之前,哪些数字已经被选中。

3.数组nch,nch_left,nch_right。因为堆是完全二叉树,已知组成堆的节点数目n,则堆的形状是不变的。堆中编号为d的节点的左右子树中的孩子节点总数是固定的,将此总数值放在nch[d]中。同理,左子树中每个节点的左右子树的孩子总数放在数组nch_left中:右子树中每个节点的左右子树的孩子总数放在数组nch_right中。

4.数组left。将所有可能作为左子树根节点的节点值按照从大到小的顺序存放在一维数组left中。

除了全局的4个一维数组,本算法还用到下面的栈:

s_left,s_right:堆是一种二叉树,此算法将左右子树在生成过程中每个节点的值分别存储在一维数组s_left和s_right中,同时s_left,s right又是顺序栈,j_left,j_right分别为栈顶指针。

栈st_left,st right:栈st_left的栈顶指针为top_left,其每个节点有两个字段,v和ind.v为数组t中某个元素的值,ind为该元素在数组t中的下标。根据上面的叙述,我们知道:如果po_left[st_left[top_left].

ind]=0,则表示v所在的这个元素在生成左子树的过程中尚未被选中;否则,表示这个元素在左子树中所处节点的编号值。同样,栈st_right表示右子树生成过程中v所在节点是否已被选中,和选中的编号值。top_left和top_right为st_left和st_rightd的栈顶指针。

二、子树算法描述

其中,n为组成整个堆元素的总个数,n_left为左子树的元素总个数,n_right为右子树的元素总个数,则n=n_left+n_right+1;k_left是在生成左子树的过程中的当前最大层数,左子树的根的层数规定为1;k-right是在生成右子树的过程中的当前最大层数,右子树的根的层数规定为1。

1.置初值,把数组t中的数按从大到小排序,并且将数组t中第一个元素作为整个堆的根节点,即po[1]=1。根据单个数判断法的条件,从数组t中除去根节点外的元素中寻找出所有可以作为左子树根节点的元素,按从大到小的顺序放入数组left中,元素个数放在left[0]中;用h作为数组left的指针,h=1。

2.从数组left中选出当前的元素作为左子树的根节点,s_left[1]=

left[h];如果h>left[0],则结束算法。

3.从数组t中,找出所有值小于或者等于s_left[1]的元素,按从大到小的顺序放入数组t left中,用来生成左子树。值得注意的是,数组t_left的元素个数会大于左子树的应有的元素个数。

4.j_left=j_left+1,如果左子树中栈s_left的当前节点指针j_left等于n_left,即左子树生成了一个堆,则转到6。如果top_left=0,说明当前左子树根节点的所有可能已经枚举完毕,h=h+1转3。

5.开始右子树的生成:将数组po和po_left中所有已经被选中过的元素合并放入数组po_mid中,由此可以将数组t中尚未被选中的元素按从大到小的顺序放入数组t_fight作为组成右子树的元素。t_right中元素个数与右子树应有元素个数相同。

6.把数组t_right中最大的数t right[1]作为右子树根节点,st_rig

ht[1]=t_right[1],po_right[1]=1,j_right=1。

7.j_ right=j_right+1,如果j_right等于n_right,则右子树生成了一个堆,此时左右子树都满足堆的条件,即整个堆找到完整的结果集,转9。

8.如果top right=0,说明当前左子树的情况下,右子树所有可能组合已经生成完毕,s_left和st_left退栈转5生成左子树的下一个结果。

9.打印由栈s_left和s_right组成的整个堆,s_right和st_right退栈转8。

综上所述基于编码的二叉树算法首先选根;然后生成堆的左子堆中的节点,每当左子堆满足构成堆的条件时,就转到右子堆进行生成:右子堆也满足构成堆的条件后,将左右子堆和根一起组合成完整的堆。在左右子堆的生成过程当中,由于将堆分成左右两个子堆来生成,也就将生成整个堆的过程从生成层数为k(k为整个堆的最大层数)的堆,转换为若干次生成k-m(m为多层生成的层数)层的堆的过程,有效的减少了生成整个堆所花费的时间,从而提高了枚举算法的效率。

参考文献:

[1]潘金贵、顾铁成等,现代计算机常用数据结构和算法[M].南京大学出版社,1994.

[2]马建平,关于堆结构的研究[D].西安:西北师范大学,2004.

[3]孙强、沈建华、顾君忠,一种生成所有堆的枚举实用算法[J].计算机工程,2002,28:80-82.