西南交大·数据结构第四次作业

简介：
一、二叉树（二） 1. 算法设计与实现 (1) 根节点到任意叶子节点的最长路径长度即为二叉树的直径。请设计并实现一个算法，用于计算基于二叉链表表示的一棵二叉树的直径。 (2) 已知一棵二叉链表结构中的根结点bt和其中两个指定结点p、q，请编写程序找出这两个结点最近的共同祖先节点地址。 (3) 请设计一个算法，将一颗基于二叉链表表示的完全二叉树的所有叶子节点按照从左到右的方向链接成一个单向链表，并返回该链表头结点指针。 2. 编程实践题 (1) 用户通过键盘输入一个不含重复字符的字符串，假设此字符串中的每个字符均代表一棵完全二叉树的顺序存储结构，请完成对该完全二叉树模型的建立（需以二叉链表形式表示），并输出其先序、中序和后序遍历序列。 (2) 请依据先序遍历算法设计程序，建立一颗基于二叉链表表示的二叉树，并对其中序线索化过程进行编码。要求使用非递归方法实现该线索化的全过程，并输出其正向和逆向的中序遍历结果序列。 二、图 1. 请根据下图所示无向图，画出其对应的多重邻接表存储结构示意图。并依据此存储结构，写出从顶点v0出发分别进行深度优先搜索和广度优先搜索时所访问节点的顺序。