维普资讯 http://www.cqvip.com ２００８年第６期 福建电脑 １０３ 线性时间复杂度的二叉树绘制算法 李新燕 （广州航海高等专科学校计算机与信息工程系广东广州５１０７２５） 【摘要】：二又树一种非常重要的数据结构，本文论述了绘制二又树算法的基本思想，建立二又树与满二又树结点间 的映射关系，并给出可行的对应算法，且其时间复杂度是线性的。 【关键字】：二叉树；满二又树；结点 １．概述 在计算机科学领域中．树形结构是一种非常重要的非线性 结构。在解决各种问题，如文件管理、数据库、编译系统等的算 法．树形结构有广泛的应用。而二叉树是树形结构的另一种重要 类型．许多算法问题用二叉树形式来解决非常简单方便，并且任 何树形结构都可以通过一个简单的转换得到与之对应的二叉 树 因此．研究有关二叉树的算法显得十分必要。同时有关二叉 树的各种算法也是数据结构这门课程的重要内容和学习的难 点。 通常，在机上验证算法或自己编写有关算法时，想了解最终 的二叉树的结构一般是通过对二叉树进行前序或中序、后序遍 历的序列来分析．从而确定结果是否正确。但由于输出的结果是 一组序列，这给分析结果带来难度。因此，绘制一棵二叉树，使结 果能以一目了然的树状输出．就显得很有现实意义。本文主要讨 论如何借用满二叉树来绘制一般二叉树．所论述的方法可用 Ｔｕｒｂｏ Ｃ。Ｖｉｓｕａｌ Ｃ＋＋等系统来实现。 ２．基本思想 绘制二叉树时应考虑的问题是如何使绘制出来的结点不产 生交叉。且每一层的结点均匀分布。同时能反映出是其双亲结点 的左孩子或右孩子。为了实现以上思想，可借助满二叉树，它的 特点是每一层的结点数都是最大结点数．即一棵深度为ｋ的满 二叉树有２ —１个结点。如图１所示是一棵深度为４的满二叉 树。 满二叉树有以下性质：如果对一棵有ｎ个结点的满二叉树 （其深度为ｌｏｇａ（ｎ＋１））的结点按层次依次编号（从第一层到第ｌｏ （ｎ＋１）层，每层从左到右编号），则对任一结点ｉ（１≤ｉ≤ｎ），有：（１） 如果ｉ＿１，则结点ｉ是二叉树的根，无双亲；如果ｉ＞ｌ。则其双亲是 结点 ２Ｊ。（２）如果２ｉ＞ｎ，则结点ｉ无左孩子。且结点ｉ为叶子 结点；否则其左孩子是结点２ｉ。 （３）如果２ｉ＋１＞ｎ，则结点ｉ无右孩 子：否则其右孩子是结点２ｉ＋１ （其中”Ｌ Ｊ”表示取向下整运 算）。 由图１可见．按照满二叉树 确定其在绘图区中的坐标位置．中各个结点所处的相对位置来 图ｌ满二叉树 那么最终树中的各个结点必定不会交叉且均匀分布．同时各个 非根结点的左右关系十分明确。 然而通常所要画的二叉树并非像满 二叉树那样，各个结点呈现均匀分布．遍 布各层．但可以把一般二叉树的各个结 点给出的位置看成与满二叉树中的结点 位置相对应，如图２所示 因此．可以先 确定满二叉树各个结点的位置．然后画 出与一般二叉树对应的结点．其他不存 在的结点不画。从而达到目的。 图２二叉树 ３．具体处理 为了自动显示一棵如图１所示的满二叉树．在实现时应避 免两个同层相邻不同双亲的结点问的叠 加问题。为有效解决该问题，这里假定：二 叉树是对称显示的：层与层之间的间距都 相等：同层同双亲的两结点的问距都相 等：同层相邻不同双亲的两结点的问距分 别都相等 根据上述规定．可以这样来处 理：先确定下层结点的位置，再确定上层 图３相关参数 结点的位置。如果给定了最底层结点的位置，就可确定整个满二 叉树中所有结点的位置，并且只要最底层结点不叠加，上层结点 也绝不会叠加 因此，可以根据最底层定义以下参数（见图３）： （１）同层同双亲兄弟结点间的中心距离为ｄ： （２）同层相邻不同双亲结点问的中心距离为ａ； （３）结点的半径为ｒ： （４）每层间距为ｈ。 其中ｄ，ａ，ｒ，ｈ满足如下：ｈ＞＞２ｒ，ｄ＞＞２ｒ，ａ＞＞２ｒ。ｈ、ｄ、ａ的 值可根据二叉树的层数适当 调整 然后以最底层的最左结 点的中心为原点．建立如图 ４所示的坐标系 由此可以 确定满二叉树中任一结点的 圆心坐标数为ｋ，结点的序号为ｉ）：（假定满二叉树层 图４满二叉树的坐标系 先求出结点ｉ所在的层数Ｃ＝ｌｏｇ￣ｉ＋１．ｉ的左子树的最左子女序号 为Ｎ＝ｉｘ２￣－ｃ，坐标原点序号为０＝２ｋ一１。ｉ结点的ｘ坐标为ｘ（ｉ）＝ｄ× Ｌ 一０＋１）／２Ｊ＋ａＸ Ｌ－（Ｎ一０）／２Ｊ＋２ｋ—ｃ一２ｘｆｄ＋ａ）一ａ／２（ 中 Ｌ Ｊ 表示取向下整运算）。该ｘ坐标值看起来很复杂．但含义却很简 单．那就是该值为ｉ结点的最左子女的ｘ坐标与ｉ结点的最右子 女的ｘ坐标和的一半。Ｙ坐标值为ｙ（ｉ）＝（ｋ—Ｃ）ｘｈ。根据坐标可以发 现任何两个同层结点都不会相交。 ４．主要算法 ｔｙｐｅｄｅｆ ｓｔ￣ｃｔ ｎｏｄｅ （ｉｎｔ ｄａｔａ； ｓｔ￣ｃｔ ｎｏｄｅ＊ｌｅｈｉｌｄ，＊ｒｅｈｉｌｄ； ｌＢＴＣＨＩＮＡＬＲ； 建立一般－－Ｘ树与满二叉树结点的映射，即初始指针数组＋ｓ［３０］＋， ｓｔ￣ｃｔ ｎｏｄｅ・ｓ［３０］； ＢＴＣＨＩＮＡＬＲ＊ｃｒｅａｔｅｂｔｆＢ１、ｃｍＮＡＬＲ＊ｂｔ１ ＩＢＴＣＨＩＮＡＬＲ ｑ； ｉｎｔｊ，ｉ： ｃｈａｒ ｘ： ｐｒｉｎｆｆ（＇ｉ，ｘ＝’：ｓｅａｎｆ（＇％ｄ．％ ＆ｉ，＆］‘）； ｗｈｉｌｅ（ｉ！＝０＆＆ｘ！＝ ￥ ） Ｉｑ＝（ＢＴＣＨＩＮＡＬＲ ）ｍａｌｌｏｅ（ｓｉｚｅｏｆ（ＢＴＣＨＩＮＡＬＲ））； 生成一个结点 ， ｑ－＞ｄａｔａ＝ｘ： ｑ－Ｍｅｈｉｌｄ＝ＮＵＬＬ：ｑ－＞ｒｃｈｉｌｄ＝ＮＵＬＬ； ｓ［ｉ］＝ｑ： ！＝１） Ｕ＝ｉ，２； ｊ为ｉ的双亲结点 ， ｉ ％２—０） ｓ［ｊ］－＞ｌｅｈｉｌｄ＝ｑ； ｉ为ｊ的左孩子 ， （下转第１０８页） 维普资讯 http://www.cqvip.com １０８ 福 建 电脑 ２００８年第６期 ３．实验结果分析 ・实验数据 ６５．Ｏ￣ｉ我们选取了泉州万维网新闻信息库共２４ｏｏ篇的文档作为 训练库，该文档集共包含娱乐、体育、商业经济等共１２类。实验 所选取的测试集则是我们从网上搜集的中文新闻网页共６Ｏ０ Ｉ 豳 ；ｋ＝１２ ｌ４ １６ １Ｂ ｝ 篇，人工归人该１２个类别。 Ｌ———————．一————————．．＿ｌ＿ ・实验１：基于ｏｎｔｏｌｏｇｙ的文本聚类分析和基于词集的文本 图２二次聚类学习的精确度比较 聚类分析准确度的比较 只是当ｋ＝１２时．文本重心尚未调整到最佳的时候．两种算 我们通过建立ＶＳＭ向量空间模型．形成基于词集的特征集 法聚类效果近似一致。而从整体的聚类质量来看。粗糙集学习后 共７３２７维，这样初始学习的２４００ｘ７３２７的数据空间。通过概念 的向量空间的聚类质量更优．较之概念集未进行调整的聚类．其 映射。概念消歧等一系列策略处理后。形成的初步概念集为 聚类的准确度高了２～３％ ２４００ｘ１４６９。 辫 本文研究说明基于Ｏｎｔｏｌｏｇｙ的中文文本聚类对于提高文本 分别选取聚类数目ｋ＝１２．１６，２０．而衡量聚类质量的标准是 聚类性能上有很大帮助。是一次有意义的尝试。并通过引入粗糙 采用Ｐｒｅｃｉｓｉｏｎ准则。 集属性选取可以部分弥补概念聚类对Ｈｏｗｎｅｔ不完备性有一定 帮助。但这种二次反馈机制肯定不是最好的．因为这种特征之间 的关系在语义上还不够深入准确 怎样进一步强化ｏｎｔｏｌｏｇｙ在 中文文本聚类中的应用。还需要我们深入探索。 参考文献 １．Ｃｈｏｏｎ Ｙａｎｇ Ｑｕｅｋ．Ｃｌａｓｓｉｉｆｃａｔｉｏｎ ｏｆ ｗｏｒｌｄ ｗｉｄｅ ｗｅｂ ｄｏｃｕｍｅｎｔ ＩＳｅｎｉｏｒ 图１基于词集和基于概念集的中文文本聚类算法精确度比较 Ｈｏｎｏｒｓ ｄｉｓｓｅｒｔａｔｉｏｎ】Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃａｍｅｇｉｅ Ｍｅｌｌｏｎ Ｕｍｖｅｍ－ 从图１。我们可以看到．基于ｏｎｔｏｌｏｇｙ的概念空间整体聚类 ｔｙ．１９９７． 质量更好。概念文本聚类得到结果。类簇之间距离较大。类簇内 ２．鲁明羽 李凡，庞淑英．陆玉昌。周立桂．基于权值调整的文本分类方法 文档相似度较接近，因此．受聚类总数影响较大一些。类簇中心 改进．清华大学学报（自然科学版）２ｏｏ５．４３（４）．５１３—５１５． 之间距离较大．同时表明了该算法得到的文本重心更适于文本 ３Ｊｉｎｇ Ｌ．Ｚｈｏｕ Ｌ，Ｎｇ Ｍ Ｋ．Ｏｎｔｏｌｏｇｙ—ｂｍｅｄ ｄｉｓｔａｎｃｅ ｍｃａｓｕｒｃ ｆｏｒ ｔｅｘｔ ｃｌｕｓ－ 分类器的构造 ｔｅｒｉｎｇ．Ｉｎ：Ｐｒｏｃ ｏｆ ｔｈｅ ４ｔｈ Ｗｏｒｋｓｈｏｐ ｏｎ Ｔｅｘｔ Ｍｉｎｉｎｇ。６ｔｈ ＳＩＡＭ Ｉｎｔｅｒｎａ— ｉｔｏｎ￣Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ。２００６ ・实验２：引入粗糙集进行概念集的二次学习的效果。 ４．董振东．知网．ｈｔｔｐ：／／ｗｗｗ．ｋｅｅｎａｇｅ．ｃｏｒｎ． 本实验设定域值悉数Ｋ－－０．６．经过过滤得到概念集中的６３５ ５．史忠植．知识发现．清华大学出版杜．２ｏｏ２年． 个义原作为粗糙集二次学习的核。引入依赖度进行决策表约简 ６．Ａ．Ｈｏｔｈｏ，Ｓ．Ｓｔａａｂ，Ａ．Ｍａｅｄｃｈｅ．Ｏｎｔｏｌｏｇｙ—ｂａｓｅｄ Ｔｅｘｔ Ｃｌｕｓｔｅｒｉｎｇ．ＫＩ １６， 后．算法在未登陆词集中选取了３１２个词集作为特征属性。最 ２ｏｏ２． 终。二次学习后形成的决策表规模为２４００ｘ（６３５＋３１２）。 －—＋一－＋－－４－—＋ （上接第１０３页） ｓＣｊ］一＞ｒｅｈｉｌｄ＝ｑ： ／．ｉ为ｊ的右孩子’， ｌ￣ｔｅｏｌｏｒ（１５）； ｌ ｃｉｒｅｌｅ（ｘ（２＊ｉ）．ｙ（２’ｉ），ｒａｄｉｕ）； ｐｒｉｎ ｉ，ｘ＝ ｓｃ】ｌｒｌ ％ｄ．％ ＆ｉ．＆ｘ】； ｌｉｎｅ（ｘ（ｉ），ｙ ），ｘ（２’ｉ）＇ｙ（２’ｉ））； ｌ ｓｅｔｃｏｈｒ（４）； ｒｅｌｕｍ ４１】 ｉｔｏａ ２’ｉ］－＞ｄａｔａ，ｓｔｒ，１ ｌ ｏｕｔｔｅｘｔｘｙ（ｘ（２’ｉ）＇ｙ（２’ｉ）， ； ，．求二叉树的深度’， ｄｉＩ２’ｉ］－ｌ； ｉｎｔ ｕｔｅｈｉｇｈｆＢＴＣｍＮａｔ￣’ｂｔ） ｌ ｌｉｎｔｌｌＩ，ｒｈ．ｈ； ｉｆ（ｓ［ｉｌ－＞ｒｃｈｉｌｄ！＝ＮＵＬＬ） ｉｆｒｂｔ＿－－ｍ＿ＮＵＥＬ） ｌｓｅｔｃｏｌｏｒ（１５）； ｈ＝ｍ ｃｉｒｅｌｅ（ｘ（２＊ｉ＋１）．ｙ（２’ １），ｎｄｉｕ）； ｅｌｓｅ ｈｎｅ（ｘ（ｉ）．ｙＧ），ｘ（２’－＋１），ｙ（２’ｉ＋１））； ｌｌｈ＝ｔｍｅｈｉｇｈ（ｂｔ－＞ｌｃｈｉｌｄ）； ｓｅｔｃｏｌｏｒ（４）； ｒｈ＝ｔｒ￣ｈｉｇｈ（ｂｔ－＞ｒｅｈｉｌｄ）； ｉｔｏａ（ｓ［２＊ｉ＋Ｉ］－：Ｍａｔａ，ｓｔｒ，１ ｏ）： ｈ＝ｏＩｌ＞ｒｈ？ｌｈ：ｒｈ）＋ｌ；ｌ ｏｕｔｔｅｘｔｘｙ（ｘ（２’Ｉ＋１），ｒ（２’｜＋１），ｓ哪； ｒｅｔｕｒｎ ｈ： ｄｉＩ２’ｉ＋ｌ】＝ｌ； Ｊ ，．绘制二叉树．， ｝ ｖｏｉｄ ｄｒａｗｔｒｅｅ（ＢＴＣＨＩＮＡＬＲ＊ｂｔ，ｌｎｔ ｋ１ ／．ｋ二叉树的深度’， ｌ ｌｃｈａｔ ｓ‘啦】； 以上的相关分析和算法的描述，给出了画二叉树一般方法。 ｉｎｔ ｄ ０１； ｉｎｔ ｒａｄｉｕ： ／．所画的每个结点的半径．按图３要求输人恰当的值’， 该算法的时间复杂度是０（ｒＩ／２），ｎ为深度为中ｋ的满二叉树的结 ｇｃａ ％ｄ ，＆ｒ丑ｄｉｕ）； 点数。该程序是用Ｔｕｒｂｏｃ ２．０编写，在机上调试通过。但画树时， ｓｅｔｅｏｌｏｒ（１５）； 树韵大小受到屏幕大小的影响．然而这不是问题之所在，若把它 ｆｏｒ（ｉ＝１；ｉ＜＝Ｏ）ｏｗ（２．ｋ卜１）／２；ｉ＋＋） 搬入到ｗｉｎｄｏｗｓ下的编程环境．再适当地加上滚动条，那么画树 ｉｑ４ｉ］！＝ＮＵⅢ ｌ ！ｄ Ｄ ／．ｄ ｉ】＝＝ｏ，表示第ｉ号结点没画过’， 时就不再会有影响 ｛ｓｅｔｅｏｌ￣ｌ５）； ｃｉｒｅｌｅ（ｘ（ｉ），ｙ（ｉ），ｒａｄｉｕ）； 参考文献： ｓｅｔｅｏｌｏｒ（４）； ｉｔｏａ（ｓ［ｉｌ－＞ｄａｔａ，ｓｔｒ，１０】； １．严蔚敏、昊伟民，数据结构．北京：清华大学出版社．１９９８ ｏｕｔｔｅｘｔｘｙ（ｘ∞．ｙ（ ，ｓ哪； ２、周志华．二叉树的绘制算法．计算机应用研究．１９９７，第４期：Ｂ７ ８８ ｄｔ［ｉｌ＝ｌ； ３、苏光大．吕映芝．用可视化法建立二叉树实例吕振洪、计算机应用研究 ｌ ２００１．第９期：５６－５８ ｉｆ（ｓ［ｉｌ－＞ｌｃｈｉｌｄ！＝ＮＵＩ ｔ）
