Обход двоичного дерева в вертикальном порядке - PullRequest
Новая
       65

Обход двоичного дерева в вертикальном порядке

0 голосов
/ 07 августа 2020

Я пытаюсь выполнить вертикальный обход порядка в двоичном дереве, например: 

       1
     /   \
   2       3
 /  \    /   \
4    6   7    8
 \           / \
   5        9   10

Прежде всего, я использую обход предварительного заказа, а затем создаю карту ha sh для хранения горизонтального расстояния узлов из root.

Расстояние по горизонтали означает, что левая часть из root будет считаться -1, -2 и так далее. Подобно отрицательной оси X, где root - начало координат и начинается с 0. Таким образом, узлу 2 будет присвоено значение -1, 4 - значение -2. Однако 1,6,7 будет дано 0, поскольку они находятся не далеко от узла root, а l ie в той же позиции. и вправо, расстояние станет положительным, так что 3 будет иметь расстояние 1, 8 получит 2 и т. д.

Я ожидаю получить отношение расстояние: узел как: {0: [1,6,7] , -1: [2,5], -2: 4, 1: [3,9], 2: 8, 3:10}, но я получаю такой вывод: 

Node : Distance
1 0
2 -1
4 -2
5 -1
6 1
3 3
7 2
8 4
9 3
10 5

Мой код следующим образом: 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def vertical_traversal(root):
    current = root
    stack = []
    hd = {}   // map
    k = 0

    while True:
        if current is not None:            
            stack.append(current)         
            hd.setdefault(k, [])
            hd[k].append(current.data)           
            current = current.left
            k += -1

        elif stack:
            k += 1
            current = stack.pop()       
            current = current.right

            if current:
                k += 1

        else:
            break
    return hd

Я, конечно, думаю, что проблема в 'k', но я не знаю, как ее обойти.

1 Ответ

1 голос
/ 07 августа 2020

При просмотре вашего кода возникла проблема в logi c, поэтому, пожалуйста, обратитесь к обновленному коду ниже: 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
class St:
    def __init__(self, root,  v):
        self.root = root
        self.v = v

def vertical_traversal(root):
    current = root
    stack = []
    hd = {}
    k = 0

    while True:
        if current is not None:
            stack.append(St(current, k))
            hd.setdefault(k, [])
            hd[k].append(current.data)
            current = current.left
            k += -1

        elif stack:
            ct = stack.pop()
            current = ct.root
            current = current.right
            if(current != None):
                k  = ct.v+1

        else:
            break
    return hd

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(6)
root.left.left.right = Node(5)
root.right.left = Node(7)
root.right.right = Node(8)
root.right.right.left = Node(9)
root.right.right.right = Node(10)
print ("Vertical order traversal is")
d = vertical_traversal(root)
print(d)

Для получения дополнительных разъяснений, пожалуйста, дайте мне знать

...