Добавить (self) со стеками в классах Python

Question

Я делаю / изучаю структуры данных и алгоритмы, и я наткнулся на следующий код:

class BinaryTree:

    def __init__(self, root_data):
        self.data = root_data
        self.left_child = None
        self.right_child = None

    def inorder_iterative(self):
        inorder_list = []
        return inorder_list

    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child

    def set_root_val(self, obj):
        self.data = obj

    def get_root_val(self):
        return self.data

    def preorder_iterative(self):
        pre_ordered_list = [] #use this as result
        stack = []
        stack.append(self)

        while len(stack)>0:
            node = stack.pop() #should return a value 
            pre_ordered_list.append(node.get_root_val())
            if node.right_child:
                stack.append(node.get_right_child())
            if node.left_child:
                stack.append(node.get_left_child())
        return pre_ordered_list


    bn = BinaryTree(1)
    bn.left_child = BinaryTree(2)
    bn.right_child = BinaryTree(3)
    print (bn.preorder_iterative())

Я очень растерялся из-за stack.append(self) части. Я не уверен, какой смысл иметь эту строку, и я не совсем понимаю концепцию .append(self). Я узнал, что self представляет экземпляр класса.

Answer 1

Цель стека состоит в том, чтобы моделировать рекурсию.

Начальное значение, помещаемое в стек, - это само дерево (в форме его корневого узла).Его значение извлекается, а затем каждое поддерево помещается в стек.На следующей итерации цикла левый дочерний элемент удаляется, обрабатывается и заменяется на его дочерних элементов, если таковые имеются.Цикл продолжается до тех пор, пока в стеке есть что-то для обработки.Как только все на левой стороне дерева будет обработано, вы, наконец, начнете на правом дочернем элементе (поместите стек в начало цикла).

Сравните с рекурсивной версией:

def preorder_recursive(self):
    result = [self.get_root_val()]
    if node.left_child:
        result.extend(node.left_child.preorder_recursive())
    if node.right_child:
        result.extend(node.right_child.preorder_recursive())
    return result

Каждый рекурсивный вызов по существу помещает self в стек, позволяя обработать левый дочерний элемент (и его потомков), прежде чем в конечном итоге вернуться к корню и перейти к правому дочернему элементу.