合同业务律师基础实务:一个有关二叉树的问题

来源:百度文库 编辑:神马品牌网 时间:2024/03/29 19:07:45
已知一棵具有n个结点(每个结点的数据域为一个字符串,长度不超过5)的完全二叉树被顺序地存储于一维数组A中,试编写一个算法(程序),打印出编号为m的结点的双亲和所有孩子。
输入:文件名t3.in,格式如下:
n
A[1] ~ A[n] { 每个字符串之间用1个空格隔开 }
m
输出:文件名t3.out,格式如下:
m的父结点(数据域)
m的所有孩子结点(数据域),按照编号从小到大的顺序,每个之间用1个空格隔开。
样例输入:5
Ok Yes No Hello Thank
2
样例输出:Ok
Hello Thank
注:Pascal语言
请给源程序
写出对二叉树进行中序遍历的非递归算法(程序)。
输入:文件名t4.in,格式如下:
n {结点数,每个结点的编号分别为1 ~ n}
data[1] ~ data[n] {数据域,data[i]均为一个大写字母}
lchild[1] ~ lchild[n] {n个结点的左孩子编号,没有则为0}
rchild[1] ~ rchild[n] {n个结点的右孩子编号,没有则为0}
输出:文件名t4.out,格式如下:
这棵二叉树的中序遍历结果。
样例输入:3
A B C
2 0 0
3 0 0
样例输出:B A C
如给出这二题的源程序,则为最佳答案。(Pascal语言)

在完全二叉树中,第m个结点的父结点为m/2取下整。
第k个结点的左孩子是2k,右孩子是2k+1,因此可以用一个队列来保存结点m的左右孩子,然后依次对队列中的每个结点进行以下操作,直到结点编号超过n:
队列头结点出队列,对该结点得到其两个孩子,将两个孩子进队列。