2. 考研
  3. 设二叉排序树用二叉链表表示，结点结构为(1child，data，rchild)，其中，data为整形，指针1child和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列)，根指针为root，试写出算法：将该二叉排序树转

设二叉排序树用二叉链表表示，结点结构为(1child，data，rchild)，其中，data为整形，指针1child和rchild分别指向左右孩子。 给定一棵递增有序的二叉排序树(前序遍历得递增有序序列)，根指针为root，试写出算法：将该二叉排序树转

admin2017-11-20  104
问题 设二叉排序树用二叉链表表示，结点结构为(1child，data，rchild)，其中，data为整形，指针1child和rchild分别指向左右孩子。
给定一棵递增有序的二叉排序树(前序遍历得递增有序序列)，根指针为root，试写出算法：将该二叉排序树转变为递减有序的二叉排序树(前序遍历得递减有序序列)，返回根指针。
选项
答案对于如图3-16a所示的子树，假设根节点P的左子树和右子树都已经经过调整而达到题目的要求，rm结点为右子树前序遍历的最后一个结点，由于P的左子树1tree的元素都小于右子树nree的任意元素，所以图3-16a右边所示的树是满足题目要求的。类似地，在没有左子树(右子树)的情况下，按方案图3-16b(或图3-16c)调整该树得到的结果是满足要求的。我们可以按递归的方式，对于不同的情况，用图3-16a、b、c所示三种规则对树进行调整。 [*] 代码如下： Node* reverseTree(Node *p，Node *m) { Node *，*r，*1m，*rm； if(p-＞rchild!=NULL)r=reverseTree(p-＞rchild，rm)； ／／递归处理右子树 if(p-＞ichild!=NULL)1=reverseTree(p-＞ichild，im); ／／递归处理左子树 Node *q=(Node *)malloc(sizeof (Node))； ／／申请并初始化新结点q q-＞data=p-＞data； q-＞ichild=q-＞xchild=NULL； m=q； if(r!=NULL) ／／若递归返回之后右子树不空 { if(1!=NULL)rm-＞ichild=1； ／／若递归返回之后左子树不空 rm-＞rchild=q； ／／结点q作为右孩子 return r； ／／返回调整后的树 } if(1!=NULL) ／／若递归返回之后左子树不空 { 1m-＞1child=q； ／／结点q作为左孩子 return 1； ／／返回调整后的树 } return q； }
解析
转载请注明原文地址:https://kaotiyun.com/show/QARi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)