设二叉排序树用二叉链表表示，结点结构为(lchild，data，rchild)，其中，data为整形，指针lchild和rchild分别指向左右孩子。
问答题
试写出二叉链表的结点类型和指针类型的定义；
【正确答案】正确答案：struct Node { irit data； Node* lchild； Nodek rchild；}；
【答案解析】
问答题
给定一棵递增有序的二叉排序树（前序遍历得递增有序序列），根指针为root，试写出算法：将该二叉排序树转变为递减有序的二叉排序树（前序遍历得递减有序序列），返回根指针；
【正确答案】正确答案：对于如图3—16a所示的子树，假设根节点P的左子树和右子树都已经经过调整而达到题目的要求，rm结点为右子树前序遍历的最后一个结点，由于P的左子树ltree的元素都小于右子树rtree的任意元素，所以图3—16a右边所示的树是满足题目要求的。类似地，在没有左子树（右子树）的情况下，按方案图3—16b（或图3—16c）调整该树得到的结果是满足要求的。我们可以按递归的方式，对于不同的情况，用图3 —16a、b、c所示三种规则对树进行调整。
【答案解析】
问答题
分析你所设计算法的时间复杂度。
【正确答案】正确答案：时间复杂度分析：由于树中的每个结点只被访问一次，所以时间复杂度为O(n)。
【答案解析】