Нужна помощь в доработке бинарного дерева python код

Question

Вы будете добавлять к классам Node и Tree, которые мы разработали в наших лекциях. Есть несколько коротких методов, которые вам придется написать.

Напишите метод is_s Similar (), который принимает в качестве входных данных два двоичных дерева и возвращает true, если узлы имеют одинаковые значения ключей и расположены в одинаковом порядке, и иначе false.

def is_similar (self, pNode):

Напишите метод print_level (), который принимает в качестве входного уровня и распечатывает все узлы на этом уровне. Если этот уровень не существует для этого двоичного дерева поиска, он ничего не печатает. Используйте соглашение, согласно которому root находится на уровне 1.

def print_level (self, level):

Напишите метод get_height (), который возвращает высоту двоичного дерева. Напомним, что высота дерева - это самая длинная длина пути от root до листа.

def get_height (self):

Напишите метод num_nodes (), который возвращает количество узлов в левое поддерево из root и количество узлов в правом поддереве из root и самого root. Эта функция будет полезна для определения сбалансированности дерева.

def num_nodes (self):

Входные данные: входные данные будут считаны из файла. Файл будет отформатирован следующим образом:

Строка 1: Несколько целых чисел, разделенных пробелами, для вставки в Дерево 1

Строка 2: Несколько целых чисел, разделенных пробелами, для вставки в Дерево 2 Вы будете читать обе строки данных. Создайте два дерева и вставьте целые числа в указанном порядке. Затем вы будете использовать эти два дерева для проверки методов, которые вы написали.

Вывод: Вывод будет отформатирован следующим образом:

Деревья похожи: (True или False)

Уровни дерева 1:

печать каждого уровня на отдельной строке

Уровни дерева 2:

печать каждого уровня на отдельной строке

Высота дерева 1: Узлы в дереве 1: Высота дерева 2: Узлы в дереве 2: Например, с учетом следующего входного файла:

14 17 1 14 17 1 Это будет вывод: Деревья похожи: True

Уровни дерева 1: 14 1 17

Уровни дерева 2: 14 1 17

Высота дерева 1: 1 Узлы в дереве 1: 3 Высота дерева 2: 1 Узлы в дереве 2: 3

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

Ниже приведен код, который мне нужен, чтобы закончить. Не совсем уверен, как запустить вспомогательные функции или основной, так что любая помощь будет оценена.

import os

class Node (object):
    def __init__ (self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class Tree (object):
    def __init__ (self):
        self.root = None

  # insert data into the tree
    def insert (self, data):
        new_node = Node (data)

        if (self.root == None):
            self.root = new_node
            return
        else:
            current = self.root
            parent = self.root

            while (current != None):
                parent = current
                if (data < current.data):
                    current = current.lchild
                else:
                    current = current.rchild

            # found location now insert node
            if (data < parent.data):
                parent.lchild = new_node
            else:
                parent.rchild = new_node

    # Returns true if two binary trees are similar
    def is_similar (self, pNode):
        pass

    # Prints out all nodes at the given level
    def print_level (self, level):
        pass

    # Returns the height of the tree
    def get_height (self): 
        pass

    # Returns the number of nodes in tree which is 
    # equivalent to 1 + number of nodes in the left 
    # subtree + number of nodes in the right subtree
    def num_nodes (self):
        pass

def main():
    # write code here

main()

Answer 1

В качестве подсказки подумайте, как вам нужно пройти через двоичное дерево при реализации каждого вспомогательного метода.

Для num_nodes я не уверен, что "и количество узлов в правом поддереве от root и самого root". средства. Должны ли мы возвращать количество узлов в правом поддереве + 1?

@classmethod
def count_below(node):
    count=0
    if (node == None):
        return 0 # if one of the root's childs was None

    if (node.lchild == None and node.rchild == None): # leaf
        return 1 # base case

    if (node.lchild != None):
        count+=count_below(node.lchild)
    if (node.rchild != None):
        count+=count_below(node.rchild)

    return count


def num_nodes(self):
    if (self.root == None):
        return 0
    return count_below(self.root.lchild), count_below(self.root.rchild) + 1

@classmethod
def depth_below(node): 
    if node is None: 
        return 0 # base case  


    # Compute the depth of each subtree 
    ldepth = depth_below(node.lchild) # recurse left
    rdepth = depth_below(node.rchild) # recurse right

    # once all the recursive calls performed on this node's childs resolve
    # return the depth of the subtree of this node with the greater depth
    if (ldepth > rdepth): 
        return ldepth+1
    else: 
        return rdepth+1

def get_height(self):
    return depth_below(self.root) # depth from root

@classmethod
def explore_childs(node, current_level, target_level):
    if (node.lchild==None and node.rchild==None):
        return # base case

    if (current_level == target_level):
        if (node.lchild!=None):
            print(node.lchild.data)
        if (node.rchild!=None):
            print(node.rchild.data)
        return # base case

    if (node.lchild!=None):
        explore_childs(node.lchild, current_level+1, target_level) # recurse left
    if (node.rchild!=None):
        explore_childs(node.rchild, current_level+1, target_level) # recurse right

def print_level(self, level):
    if (level > self.get_height()):
        pass # throw error

    explore_childs(root, 0, level)