Необходимо вывести глубину залегания элемента в бинарном дереве, не проходит все тесты

Рейтинг: 0Ответов: 1Опубликовано: 15.03.2023

В бинарное дерево поиска добавляются элементы. Выведите глубину для каждого добавленного элемента в том порядке, как они добавлялись. Если элемент уже есть в дереве, то ничего добавлять и выводить не нужно. Глубиной называется расстояние от корня дерева до элемента включительно.

Формат ввода Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. По данной последовательности требуется построить дерево.

Формат вывода Выведите ответ на задачу.

binary=[]

#добавление корня дерева
def root(binary,x):
    binary=[x,[None,None]]
    return binary

#добавление нового элемента дерева
def ad_in_binary(binary,x):
    key=binary[0]
    if x<key:
        if binary[1][0]==None:
            binary[1][0]=[x,[None,None]]
        else:
            ad_in_binary(binary[1][0],x)
    if x>key:
        if binary[1][1]==None:
            binary[1][1]=[x,[None,None]]
        else:
            ad_in_binary(binary[1][1],x)               
    return binary

s=str(input()).split()
s=list(map(lambda x:int(x), s))
binary=root(binary,s[0])
i=1
while s[i]!=0:
    binary=ad_in_binary(binary,s[i])
    i=i+1
def floor(binary,x):
    key=binary[0]
    if x==key:
        return 1
    elif x<key:
        return floor(binary[1][0],x)+1
    elif x>key:
        return floor(binary[1][1],x)+1
i=0
while s[i]!=0:
    print(floor(binary,s[i]), end=' ')
    i=i+1
python
Источник: Stack Overflow на русском

Ответы

▲ 0

Разобрался, забыл, что для повторяющихся элементов выводить ничего не нужно.

binary=[]

#добавление корня дерева
def root(binary,x):
    binary=[x,[None,None]]
    return binary

#добавление нового элемента дерева
def ad_in_binary(binary,x):
    key=binary[0]
    if x<key:
        if binary[1][0]==None:
            binary[1][0]=[x,[None,None]]
        else:
            ad_in_binary(binary[1][0],x)
    if x>key:
        if binary[1][1]==None:
            binary[1][1]=[x,[None,None]]
        else:
            ad_in_binary(binary[1][1],x)               
    return binary

s=str(input()).split()
s=list(map(lambda x:int(x), s))
binary=root(binary,s[0])
i=1
while s[i]!=0:
    binary=ad_in_binary(binary,s[i])
    i=i+1
def floor(binary,x):
    key=binary[0]
    if x==key:
        return 1
    elif x<key:
        return floor(binary[1][0],x)+1
    elif x>key:
        return floor(binary[1][1],x)+1
i=0
sets=set()
while s[i]!=0:
    if s[i] not in sets:
        sets.add(s[i])
        print(floor(binary,s[i]), end=' ')
    i=i+1