青大数据结构【2020】【五算法设计】 |
您所在的位置：网站首页 › princomp函数 › 青大数据结构【2020】【五算法设计】 |
青大数据结构【2020】【五算法设计】
|
关键字： 单链表并集、二叉树后序遍历找父节点
1）基本思想： A、B两个链表的元素均递增有序，所以可以，按顺序，同时从A中和B中各取一个结点的值来对比；如果A中结点的值比较小，则A中的指针右移；如果B中的结点的值比较小，则B中的指针右移；如果相等，则将结点值赋予C链表中，然后A、B中的指针各右移。 2） Linklist Intersection(Linklist A,Linklist B,Linklist &C){ LNode *p,*q,*r; p=A->next; q=B->next; r=C; while(p&&q){ if(p->data==q->data){ r->next=p; r=r->next; p=p->next; q=q->next; } else if(p->datadata) p=p->next; else q=q->next; } r->next=NULL; }
1）基本思想： 利用栈，对二叉树采用后序遍历非递归的方法，当遍历到p结点时，由于是后序遍历方法，栈中所有元素都是p的祖先结点，栈顶就是p的父节点。 2）
void PostOrderTraverse(BiTree Tree,BiTree p) { InitStack(S); BiTree q,r; q=Tree; r=NULL; while(q||!IsEmpty(S)){ //二叉树非空或栈非空 if(q){ //左孩子入栈 push(S,q); //入栈，先根节点 if(q==p){ printf("Find\n"); //查找成功，是当前栈顶取出后的栈顶元素为父结点 return;} q=q->lchild; //q指向左孩子 } else{ GetTop(S,q); //左孩子为空，读栈顶元素 if(q->rchild&&q->rchild!=NULL){ //有右孩子则右孩子入栈 q=q->rchild; push(S,q); if(q==p){ printf("Find\n"); //查找成功，是当前栈顶取出后的栈顶元素为父结点 return;} q=q->lchild;} //q指向左孩子 else{ //没有左孩子也没右孩子出栈 pop(S,q); //栈顶出栈，q指向新栈顶 visit(q->data); r=p; p=NULL; } }//else }//while }
|
【本文地址】
今日新闻 |
推荐新闻 |