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

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

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

计算机408

学硕统考专业

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