数据结构考研分类复习真题 第六章 树和二叉树 (五)[6]

．设一棵二叉树的结点结构为 (LLINKINFORLINK)ROOT为指向该二叉树根结点的指针p和q分别为指向该二叉树中任意两个结点的指针试编写一算法ANCESTOR(ROOTpqr)该算法找到p和q的最近共同祖先结点r【吉林大学 二 (分)】【中山大学 六(分)】

．已知一棵二叉树按顺序方式存储在数组A[n]中设计算法求出下标分别为i和j的两个结点的最近的公共祖先结点的值【武汉大学 五 】

．设计这样的二叉树用它可以表示父子夫妻和兄弟三种关系并编写一个查找任意父亲结点的所有儿子的过程【燕山大学 四 (分)】

．在二叉树中查找值为x的结点试编写算法(用C语言)打印值为x的结点的所有祖先假设值为x的结点不多于一个最后试分析该算法的时间复杂度(若不加分析直接写出结果按零分算)【上海交通大学 五】

类似本题的另外叙述有

()在二叉树中查找值为x的结点请编写一算法用以打印值为x的结点的所有祖先假设值为x的结点不多于个注采用非递归算法【西安电子科技大学 六(分)】

()设二叉树中结点的数据域的值互不相同试设计一个算法将数据域值为x 的结点的所有祖先结点的数据域打印出来【北方交通大学 八(分)】

()设二叉树根指针为t且树中结点值各不相同写出算法disp_f(tx)查找树中值为t的结点并显示出其所有祖先结点的值【首都经贸大学 三 (分)】

()若一棵二叉树中没有数据域值相同的结点设计算法打印数据域值为x的所有祖先结点的数据域如果根结点的数据域值为x或不存在数据域值为x的结点则什么也不打印例如右图所示的二叉树则打印结点序列为ACE【北京工业大学 五 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []