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

admin2017-11-20  70

问题 设二叉排序树用二叉链表表示,结点结构为(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://jikaoti.com/ti/6tfjFFFM
0

最新回复(0)