PTA-列出所有祖先结点

2023-12-13 08:07:58

题目:

对于给定的二叉树,本题要求你按从上到下顺序输出指定结点的所有祖先结点。

输入格式:

首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N?1 编号。

随后 N 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 "-"。编号间以 1 个空格分隔。

最后一行给出一个结点的编号i(0≤i≤N-1)。

输出格式:

在一行中按规定顺序输出i的所有祖先结点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

7
2 -
- 6
- -
0 5
- -
4 1
- -
4

输出样例:

3 5

分析:

  1. 初始化:首先,创建一个名为BinTree的类,该类有三个属性:leftrightparent,它们都被初始化为-1。这意味着在开始时,每个节点都没有左子节点、右子节点和父节点。
  2. 创建函数create()函数用于创建二叉树。首先,它创建一个名为T的空列表,然后从标准输入读取节点数n。接下来,它通过循环n次在列表T中添加新的BinTree实例。然后,它再次从标准输入读取每个节点的左子节点和右子节点(如果存在),并更新相应的BinTree实例的属性。同时,它还设置每个节点的父节点。
  3. 查找函数find()函数用于找到给定节点的祖先节点。它首先获取要查找祖先的节点的索引root。然后,它通过不断地将当前节点的父节点设置为新的当前节点,将所有祖先节点收集到列表a中。最后,它倒序打印出祖先节点的索引。
  4. 主函数:在主函数中,首先调用create()函数创建二叉树。如果二叉树至少有两个节点,它就调用find()函数来查找并打印一个给定节点的所有祖先节点。

Python版本:

class BinTree:
    def __init__(self):
        self.left = -1
        self.right = -1
        self.parent = -1
        
def create():
    T = []
    n = int(input())
    for _ in range(n):
        node = BinTree()
        T.append(node)
    
    for i in range(n):
        l, r = input().strip().split()
        if l != '-':
            T[i].left = int(l)
            T[T[i].left].parent = i
        if r != '-':
            T[i].right = int(r)
            T[T[i].right].parent = i
            
    return T

def find(T):
    a = []
    root = int(input())
    while T[root].parent != -1:
        a.append(T[root].parent)
        root = T[root].parent
    
    for i in range(len(a)-1, -1, -1):
        print(" " + str(a[i]) if i != len(a)-1 else str(a[i]), end='')
    

if __name__ == '__main__':
    T = create()
    if len(T) > 1:
        find(T)

总结:

?这段代码主要实现了二叉树的创建和遍历。其中,二叉树节点的结构是其主要特点,而遍历则是通过追溯每个节点的父节点实现的。在创建二叉树的过程中,用户可以为其指定节点的左右子节点和父节点。在查找函数中,通过追溯父节点找到所有祖先节点,并以列表形式返回。

文章来源:https://blog.csdn.net/m0_74316503/article/details/134574772
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。