树状显示二叉树:
编写函数displaytree(二叉树的根指针,数据值宽度,屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的,同层的节点在同一行上。
[问题描述]
假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用
(层号,须打印的空格数)来界定。
第0层:根在(0,32)处输出;
第1层:因为根节点缩进了32个空格,所以下一层的偏移量(offset)为32/2=16=screenwidth/22。即第一层的两个节点的位置为(1,32-offset),(1,32+offset)即(1,16),(1,48)。
第二层:第二层的偏移量offset为screenwidth/23。第二层的四个节点的位置 分别是(2,16-offset),(2,16+offset),(2,48-offset),(2,48+offset)即(2,8),(2,24),(2,40),(2,56)。
……
第i层:第i层的偏移量offset为screenwidth/2i+1。第i层的每个节点的位置是访问第i-1层其双亲节点时确定的。假设其双亲的位置为(i-1,parentpos)。若其第i层的节点是其左孩子,那末左孩子的位置是(i,parentpos-offset),右孩子的位置是(i,parentpos+offset)。
[实现提示]
利用二叉树的层次遍历算法实现。利用两个队列Q,QI。队列Q中存放节点信息,队列QI中存相应于队列Q中的节点的位置信息,包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时,相应的打印信息被存到QI中。二叉树本身采用二叉链表存储。