6-33 从下往上打印指定元素的所有祖先 (6分)

6-33 从下往上打印指定元素的所有祖先 (6分)

本题要求实现按从下往上打印二叉树中指定元素的祖先。 函数接口定义：

int PrintAncestors(BiTree T,char ch);

T是二叉树树根指针，ch为指定的元素值，PrintAncestors函数按从下到上输出二叉树的ch的所有祖先结点序列，格式为一个字符后面跟着一个空格。 其中BinTree结构定义如下：

typedef char ElemType; typedef struct BiTNode { ElementType data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode, *BiTree;

裁判测试程序样例：

#include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct BiTNode { ElementType data; struct BiTNode *lchild; struct BiTNode *rchild; int level; }BiTNode, *BiTree; BiTree Create();/*细节在此不表*/ int PrintAncestors(BiTree T,char ch); int main() { BiTree T = Create(); char ch; scanf("\n%c", &ch); PrintAncestors(T,ch); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */

输出样例： 对于图中给出的二叉树， 当输入的ch为’F’时，输出为：

D B A

实现代码

int PrintAncestors(BiTree T,char ch) { int c1,c2; if(T==NULL)return 0;//空树 else if(T->data==ch) return 1;//找到ch的祖先，返回1 else { c1=PrintAncestors(T->lchild,ch);//递归查找子孙为ch的节点 c2=PrintAncestors(T->rchild,ch); if(c1||c2)//返回1时 printf("%c ",T->data);//打印 } }