数据�l�构�W�六章算法设计题[11]_跨考网

1�Q�在二叉�?w��i)中查找��gؓ(f��)x的结点，试编写算法（�?/span>C语言�Q�打印��gؓ(f��)x的结点的所有祖先，假设��gؓ(f��)x的结点不多于一个，最后试分析该算法的旉���复杂度（若不加分析，直接写出�l�果�Q�按零分���）(j��)�?/span> �?a target="_blank">上�v交通大�?/a> 1998 五�?/span>

　　【参考答案�?/span>

　　[题目分析]后序遍历最后访问根�l�点�Q�当讉K��到��gؓ(f��)x的结�Ҏ(gu��)���Q�栈中所有元素均������l�点的祖先�?/span>

　　void Search(BiTree bt,ElemType x) //在二叉树(w��i)bt中，查找��gؓ(f��)x的结点，�q�打印其所有祖�?/span>

　　{typedef struct

　　{BiTree t; int tag; }stack;//tag=0表示左子奌���讉K���Q?/span>tag=1表示叛_��奌���讉K��

　　stack s[]; //栈容量��够大

　　top=0;

　　while(bt!=null||top>0)

　　{while(bt!=null && bt->data!=x) //�l�点入栈

　　{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

　　if(bt->data==x){ printf(“所查结点的所有祖先结点的��gؓ(f��):\n�?/span>); //扑ֈ�x

　　for(i=1;i<=top;i++) printf(s[i].t->data); return; } //输出���先值后�l�束

　　while(top!=0 && s[top].tag==1) top--; //退栈（�I�遍历）(j��)

　　if(top!=0) {s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历

　　}// while(bt!=null||top>0)

　　}�l�束search

　　因�ؓ(f��)查找的过�E�就是后序遍历的�q�程�Q���用的栈的深度不超�q�树(w��i)的深度，���法复杂度�ؓ(f��)O(logn)�?/span>