二叉树结构的输出

二叉树结构的输出 第 19 卷 第 6 期 1999 年 11 月 天津商学院学报 JOU RN A L O F T IA N J IN U N IV ER S IT Y O F COM M ER C E V o l. 19 N o. 6 N o v α 二叉树结构的输出 肖利敏 () 天津商学院计算机信息与管理系, 天津 300400 摘 要 二叉树是一种重要的数据结构, 广泛运用于计算机软件技术中。本文主要研究了二 叉树结构的输出, 并提出了 3 种输出方法。前两种方法均在标准 中实现, 未使用标 PA SCA L 准库函数; 第三种方法调用了标准 、单元, 运用清屏、光标定位、延迟等函数, 使输出 CR TDO S 不受行宽和换行限制, 可直接访问节点定位输出。 对深度超过 6, 需超行输出的, 动画输出其 结构。 关键词 数据结构; 二叉树; 前序遍历; 广度优先搜索; 队列 分类号16301T P O utput of the B inary Tree Struc ture X iao L im in (, D ep a r tm en t o f Com p u te r Info rm a t io n and E ng inee r ing M anagem en tT ian jin U n ive r sity o f ), 300400Comm e rceT ian jin A bstrac t B ina ry t ree is an im po r tan t typ e o f da ta stu rc tu re. It is ex ten sive ly app lie s in th e . , tech no lo gy o f com p u te r so f tw a reT h is p ap e r d iscu sse s o u tp u t o f th e b ina ry t ree st ruc tu re . and p u t s fo rw a rd th ree a lgo r ithm sT h e f ir st tw o a lgo r ithm s a re execu ted in standa rd p a sca l . , language w ith no u t iliza t io n o f func t io n sIn th e th ird a lgo r ithm w ith th e u t iliza t io n o f func2 ()() t io n s: C lr sc r、Go to 、D e lay , th e o u tp u t o f th e b ina ry t ree st ruc tu re becom e s f ree. ; ; ; ; Key words da ta st ruc tu reb ina ry t reep reo rde r sea rchb rea th f ir st sea rchqueue 数据结构中有一种重要的类型——二叉树, 其结二叉树: 有限个节点的集合, 它或者为空集, 构层次性强, 应用灵活, 采用指针等动态存储方式, 节 是由一个根节点以及两棵互不相交且分别称为左 省了空间, 所以被广泛运用于计算机软件技术中。由于 和右子树的二叉树组成的。 1k 二叉树是一种抽象的存储结构, 不能直观地看到各数 满二叉树: 深度为 且有 2- k 1 个节点的 据在二叉树中的存储位置, 本文提出了二叉树结构的 树。 输出, 可以直观地看到二叉树是怎样存储数据的。 完全二叉树: 对满二叉树的节点进行连续编 定编号从根节点起, 自上而下, 自左至右, 当一个 为 , 有 个节点的二叉树, 当且仅当其每一个节 1 k n 二叉树的相关知识 与深度为 的满二叉树中编号从 1 至 的节点一 k n 1. 1 定义应时称为完全二叉树。[ 2 ]1 1. 2 二叉树的性质 数据结构: 数据元素之间抽象化的相互关系和 这种关系在计算机中的存储表示, 并对每种结构定义 性质 1: 具有 个节点的完全二叉树的深 n 各自的运算, 设计出相应的算法, 经过运算后所得的新 [ + 1 。 lo g2 n 结构一般仍然是原来的结构类型。 性质 2: 如果对一棵有 个节点的完全二叉 n ( 节点按层序编号 从第一层到第[ + 每层从左1 lo g2 n ) () 至右, 则对任一节点 1??有:i in () 1如果 = 1, 则节点 是二叉树的根, 无双亲, 如 ii ( ) 果 > 1, 则其双亲 是节点[ 2 ;ƒiP a ren t ii () (2如果 2 > , 则节点 无左子树 节点 为叶子 in i i ) ( ) 节点, 否则其左子树是节点 2 ;L ch ild ii ( ) 3如果 2 + 1> , 则节点 无右子树, 否则其右 i n i ( ) 子树 是节点 2 + 1。R ch ild ii 图 1 二叉树的转换 2. 2 方法 2 2 二叉树的结构输出方法2 第 2 种方法是采用广度优先搜索法, 本方法用 () 前序遍历输入过程 , , 进行输入并 C rea t a f loord ep th 2. 1 方法 1(计算返回深度 , 所以输出只有一个过程 ,d ep th B f s a 第 1 种方法包括 4 个过程。 第一个过程是将标准 )。 本过程采用广度优先搜索法, 运用队列 , 将 d ep th v 二叉树拷贝入有左子树、右子树、数据信息和节点在完 访问节点入队, 队存储节点 . ^ . 和节点在完全vf d a 全二叉树中的顺序号这四个域的专用二叉树中。 在前 二叉树中顺序数 . ^ . 。 队不为空时, 头元素出 vf n um () 序遍历输入过程 , , , , 其中: 为 的 C rea t a bcf d ep th b a () 队, 先访问左子树, 由过程 , , , , L is t bd ep th n f loorp n 父节点, 标志 是 的左子树还是右子树, 为cf a b d ep th 输出节点信息, 其中 为要访问的节点, 为该节点在 b n 深度。 由性质 2 对下述情况分别进行处理: 对左子树完全二叉树中的顺序数, 由顺序数的特征有 = ^ . ba () = 0, 其在完全二叉树中的顺序数为父节点的两倍cf 时即 为 的左子树时, 的顺序数为其父节点 lch ild b a b (() a ^ . n um = 2×b^ . n um + cf , cf = 0; 对右子树 cf =的 2 倍, 即 = 2×. ^ . 。, 分别为上一n vf n um f loorp n ) ( 1, 顺序数为父节点的两倍加 1 ^ . = 2 ×^ .a n um b f loor -2, 当 > 1 时转行, 节访问节点的层数和顺序数n ) n um + cf , cf = 1。节点数据信息则直接输入专用二叉d ep th - f loor 1点为本行第一个节点, 计算出其横坐标 = 2× x () 树 的数据信息域中; 过程 则对所有节点a F ores t a f loor ) ) ( ( 2 - 2+1- 1; 否则计算其对上一输出节点的n ( ) 进行以下处理: 1左右子树均不为空的, 将右子树移d ep th - f loor+ 1 )(。最后, 节点 入队 = 2×- 相对坐标 p n b x n ( ) 到左子树的右子树上, 置原右子树为空; 2左子树为 返回, 再访问右子树, 循环进行。空, 右子树不为空的, 将右子树移到左子树上, 置右子 本方法采用广度优先的遍历方式, 直接实现了按 () 树为空; 过程 , , 通过前序遍历二叉 C h a n g e a bd ep th 完全二叉树顺序对节点的逐个访问, 时 间 复 杂 度 为 树, 对有左子树的节点, 将其左子树移到从本节点出 ()。O n 发, 第一个没有右子树的节点的右子树上, 置原左子树 2. 3 方法 3() () 为空。经过以上两个过程 , 便将原二 F ores t C h a n g e 第 3 种方法调用了标准 单元, 运用了 , CR T DO S ( ) 叉树按各节点在完全二叉树中的顺序转化成一条链, 光标定位函数 , 输出不受换行和行宽限制, 对 G oT o 节点的访问顺序也不受限制。 由于清屏函数 的 C l rsc r 仍用专用二叉树存储, 其中所有左节点均为空, 右节点 运用, 对深度超过 6 的二叉树采用动画显示。对字符间 ( )存储数据信息和顺序数 如图 1。 最后通过过程L is t ( ) , 直接遍历二叉树的右子树链式顺序输出各 a d ep th 隔与行间隔不同所造成的视觉上的不直观, 本方法也 节点信息, 由其在完全二叉树中的顺序数确定其横坐 进行了控制。 标。由完全二叉树的定义可知, 对第 层节点的顺f loor () 本方法输出各过程为, :L is t a d ep th f loor- 1 f loor () ( 1当深度 ?6 时, 直接调用输出过程,d ep th L i a ^ . 在 2和 2-1 之间时, 当其为本序数 a n um d ep th - f loor+ 1 ) , , , , , , 置起始d ep th if loorn um p j , 前序遍历二叉树 a ( (层第一个节点时, 横坐标 = 2× 2× ^ . x a f loor- 1 ) ) 2+ - 1- 1, 对非本层第一个输出的节点,n um d ep th - f loor ( 横坐标 = 0, 直接计算其横坐标 = 2× 2× 用 标 志 其 上 一 个 输 出 节 点, 则 其 横 坐 标 = ix np a x d ep th - f loor ) - 1- + 1, 其中 表示节点在本层左起顺序数。由二 )(in ^ . 。 2×^ . - p a n um a n um 叉树性质: 左子树顺序数为其父节点的 2 倍减 1, 右子本方法经过两次变换将原二叉树按顺序数变成一 ()条链, 时间复杂度为。O n 树顺序数为其父节点的 2 倍。本过程中, 为父节点 n um ?63? 1999 年 第 19 卷 第 6 期天津商学院学报 ( )( ) 顺序数, 0、1分别标志本节点为父节点的右子 右平移, 至 = 2= 0, 这时 = 0 又递增右平移。 p p iA iA 树、左子树, 此时 = 2×- 。 为解决纵坐标中由 来回动画显示, 在每次显示结束时使用了延迟n n um p () 于字符间隔与行间隔造成显示上的不直观, 假设=, 控制动画速度。最后使用 函 M D e lay K ey p ressed 2- 1, 则从第 2 行到第+ 1 行, 分别多了止输出。d ep th d iv M ()本方法时间复杂度为。O n , 2, 1 行, 从第 2 行到+ 1 行的纵坐标为 1, ,- M M M (), + + - 1。在程 + , + + 1, f loorM M f loorM f loorM 序中引入参数 , 初始值为 1, 对第一行 = 1, 则纵 j f loor3 结束语 坐标 y = f loor; 从第二行开始纵坐标 y = f loor + M + , 当 < - 1 时, = + 1, 这样对 = 2, 3, 对二叉树的结构输出有许多种方法, 本文仅, M j j M j j f loor + 1, 与相应的 = 0, 1, - 1, 则计算出纵坐标 = 了三种典型的。 对二叉树的结构输出可以推广到,j M y () , + + - 1; 对 + , + +f loor M M j 1, f loor M f loor M 和森林结构的输出, 不仅可以让初学者、程序员直 > = - 1 时, 不再递增, 同时纵坐标也不再多空行, 看到二叉树存储的信息, 也可以使用户了解数据M j () = + 2×- 1。储方式, 或直观地看到树型结构表现的信息间的y f loorM () 2当深度 > 6 时, 由于行超出, 只截取横坐 关系, 如企业、公司的行政结构、权力结构等。d ep th ()标 0< < 80 的节点输出, 引入起始横坐标 , , 横坐标 源程序略x i d ep th 等于绝对横坐标减 。设= 2- 81, 则 在 0,x iA C T i 参 考 文 献 1, , 81 递增时, 二叉树就在屏幕坐标系中向右平移; 袁蒲佳, 龙玉国, 杨薇薇 1 数据结构 1 武汉: 华中理 1 当 在 81, 80, , 0 递减时向左平移。控制左右移动引i 出版社, 199114, 70, 90 入了0= 0, 1= 。当 = 0, 设增减方向标识 A A A C T iA p p严蔚敏, 吴伟民 1 数 据 结 构 1 北 京: 清 华 大 学 出 2 = 1 递增, 终止循环点A 2= A 1, 这时 i?A 2, i = i + p p19921123, 168 递增输出, 二叉树左平移, 至 = 2 = ; 当 = 1i A A C T i A = 时, 置增减方向标识 = 1, 终止循环点2 - A C T p p A ( 责任编辑 朱= 1= 0; 当 〈〉2 时, = + 递减输出, 二叉树向 A i A iip p () 上接第 55 页 李 由, 向守方 1 国有资产管理体制改革实务 1 北京 2 高, 才是防止国有资产流失的根本方法。盘活国有企业 管理出版社, 1997的存量资产, 就是对企业的资产进行优化组合或资产 邹亚生 1 企业兼并操作指导 1 北京: 经济管理出版社, 3 重组, 提高国有企业存量资产的运营效益。 4 常修泽 1 产权交易 1 北京: 经济日报出版社, 1995 参 考 文 献 ( 责任编辑 赵1 吴永建, 刘 莎 1 产权流动和产权市场现状及主要问题 1 () 国有资产管理, 1995 4: 16, 18