西南交通大学-zhy-数据结构第3次作业-2020版.docx

西南交大;西南交通大学;数据结构;赵宏宇;1. 写算法 (1) 已知二叉树（二叉链表）根结点指针为bt，求该二叉树中的叶子数目。 (2) 已知某二叉树（三叉链表）的根结点地址root，该树中各结点的左、右儿子指针域已正确填充，写一个算法将所有结点的双亲指针域正确填充。 (3) 已知某二叉树（二叉链表）的根结点指针bt。编写算法，将该二叉树中所有结点的左右子树互换。 (4) 已知n个结点的完全二叉树结点数据域值按结点编号次序顺序存于一维数组（元素下标范围0..n-1）。编写算法，由该数组首地址以及数组长度n建立对应的二叉链表存储结构。 2. 上机题 (1) 编写完整程序，用先序遍历法建立二叉树的二叉链表存储结构，要求结点data域值类型为int。输入的先序遍历整数序列用0表示NULL指针域，其它有效结点的data域值均不等0。定义三个算法函数，分别计算并输出二叉树中结点data域值的最大值、结点data域值之和以及data域值小于0的结点数。 (2) 从键盘输入n个数据建立n元完全二叉树顺序存储结构。实现该完全二叉树的先、中、后序遍历。