企源知识库

试编写算法查找二叉链表中数据域值为X的结点(假定各结点的数据域值各不相同)，并打印出X所有祖先的数据域值。
【正确答案】：设置一个栈用于装入查找结点的所有祖先。 栈的元素结构说明如下： typedef struct { BinTree P； int tag； }Snode； int search(BinTree T，DataType X) { top=0； ／／栈S初置为0 while((T!=NULL)＆＆(T一>data!=X)∣∣(top!=0)) {while((T!=NULL)＆＆(T一>data!=X)) {top++； s[top]．p=T；s[top]．tag=o； ／／结点入栈，置访问标志0 T=T一>lchild； ／／找左子树 } if((T!=NULL)＆＆(T一>data==x)) ／／找到 { for(i=1；i<=top；i++) printf("％d＼n"，s[i]．p—>data)； ／／输出 return(1)； } else while((top>0)＆＆(s[top]．tag==1))top——；／／退出左子树已访问过的结点 if(top>0)rchild；)／／置访问标志1，访问右子树 } return(0)； }