课程设计（论文）-线索二叉树的应用

hild=child->lchild; while(child->rchild&&child->rtag==0)//找到左子树下,最右结点 child=child->rchild; p1->rchild=child->rchild;//后继化 p1->rtag=1; child->rtag=0; child->rchild=p1;//连接 p1->lchild=child;//前驱化 p1->ltag=1;?}?else//当孩子结点没有左孩子的时候?{ p1->lchild=child->lchild;//前驱化 child->ltag=0; p1->ltag=1; child->lchild=p1; p1->rchild=child; p1->rtag=1;?}?printf("\n\t插入结点操作已经完成,并同时完成了线索化的恢复\n");}4.线索二叉树的删除删除的情况有以下三种(1)删除的节点p是叶子节点,直接删除,修改其父亲的线索(2)删除的节点p有一个儿子,p有一个左儿子,以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继,中序前驱不变;p有一个右儿子,以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱,中序后继不变(3)除的节点p有二个儿子,转化为叶子节点或只有一个儿子节点的删除Bithptr*DeleteNode(Bithptr*t){?Bithptr*child,*pre,*s,*q;?charch;?printf("输入查找的结点信息:");ch=getchar();?ch=getchar();?child=SearchChild(t,ch);//查找该结点的孩子结点?printf("发现结点:%c\n",child->data);?printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag);