设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。 设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数X。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。

admin2019-08-15  34

问题 设排序二叉树中结点的结构由三个域构成:数据域data,指向左儿子结点的指针域left,指向右儿子结点的指针域right。
设data域为正整数,该二叉树树根结点地址为T。现给出一个正整数X。请编写非递归程序,实现将data域的值小于等于x的结点全部删除。

选项

答案 利用二叉排序树的性质,从根结点开始查找,若根结点的值小于等于x,则根结点及其左子树均应删除,然后以右子树的根结点为树根,重新开始查找。若根结点的值大于x,则顺左子树向下查找,直到某结点的值小于等于x,则该结点及其左子树均应删除。下面设计一查找算法,确定被删除子树的根结点,再设计一删除算法,删除以被删结点为根的子树。 typedef struct node{ int data; struct node *left, *right; }BiTNode, *BSTree; void DelTree(BSTree r){ //非递归删除以r为根的二叉排序树 BSTree S[]; //栈,容量足够大,栈中元素是二叉排序树结点的指针 BSTree p; int top=0: while(r !=null ∣∣ top>0){ while(r!=null){S[++top]=r;r=r一>left;} //沿左分支向下 if(top>0) //退栈,沿栈顶结点的右子树向下删除,释放被删除结点空间 {p=S[top——];r=p一>right;free(P);} } }//DelTree void DeleteAllx(BSTree T,int x){ //在二叉排序树T中,删除所有小于等于x的结点 BSTree P=T,q; while(T&&T->data<=x){ //根结点的值小于等于x P=T;T=T一>right;p一>right=null; DelTree(P); } //删除二叉树P,删除持续到”根”结点值大于x或T为空树为止 if(T){ q=T;P=T一>left; while(P&&P一>data>x){ //沿根结点左分支向下,查小于等于x的结点 while(P&&p一>data>x){q=P;P=p一>left;} //q记P的双亲 if(P) //p结点的值小于等于X { q->left=P一>right;p一>right=null;DelTree(P); } p=q->left: //再查原p的右子树中小于等于x的结点 } } }

解析
转载请注明原文地址:https://jikaoti.com/ti/ZoGjFFFM
0

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