Нахождение пути 2 узлов в двоичном дереве поиска - PullRequest
Новая
       15

Нахождение пути 2 узлов в двоичном дереве поиска

0 голосов
/ 19 октября 2018

У меня есть этот код, который должен найти путь между 2 узлами.Проблема в том, что если узел 2 больше, чем узел 1, он не может различить, является ли он родительским или правым дочерним, и теперь я делаю, как исправить эту проблему.Я подумал, что, возможно, смена элементов 2 и 1 сработает, но это просто делает неправильный порядок. 

def _find_path(self, element_1, element_2, nature):

    if element_1 !=None and element_2 != None:
        if element_1.key == element_2.key:
            self.list_path.append(element_1)
        else:
            if(element_1.key == self.root.key or element_2.key == self.root.key):
                if(element_2.key > element_1.key):
                    self.list_path.append(element_1)
                    self._find_path(element_1.rightChild, element_2, nature)
                if (element_2.key < element_1.key):
                    self.list_path.append(element_1)
                    self._find_path(element_1.leftChild, element_2, nature)
            else:
                    if(element_1.key < self.root.key and element_2.key < self.root.key or element_1.key > self.root.key and element_2.key > self.root.key):
                        if element_2.key > element_1.key:
                            self.list_path.append(element_1)
                            self._find_path(element_1.parent, element_2, nature)
                        if element_2.key < element_1.key:
                            self.list_path.append(element_1)
                            self._find_path(element_1.leftChild, element_2, nature)
                        else:
                            if element_1.key == element_2.key:
                               return [element_1]
                            res = self._find_path(element_1.leftChild, element_2,nature)
                            if res:
                                self.steps += 1
                                return [element_1] + res
                            res = self._find_path(element_1.rightChild, element_2,nature)
                            if res:
                                self.steps += 1
                                return [element_1] + res
                    else:
                        if(element_1.key < self.root.key and element_2.key > self.root.key):
                            self.list_path.append(element_1)
                            self._find_path(element_1.parent, element_2, nature)
                        else:
                            self.list_path.append(element_1)
                            self._find_path(element_1.parent, element_2, nature)
    return self.list_path
...