Aby zrozumieć, jaka jest ta sama pionowa linia, musimy najpierw określić odległości poziome. Jeśli dwa węzły mają tę samą odległość poziomą (HD), są one na tej samej linii pionowej. Idea HD jest prosta. HD dla roota to 0, prawa krawędź (krawędź łącząca z prawym poddrzewem) jest traktowana jako +1 pozioma odległość, a lewa krawędź jest traktowana jako -1 pozioma odległość. Na przykład w poniższym drzewie HD dla węzła 4 ma wartość -2, HD dla węzła 2 to -1, HD dla 5 i 6 to 0, a HD dla węzła 7 to +2.

Przykłady:

      1
    /   \

   2     3

  / \   / \
  4  5  6  7

Drzewo ma 5 pionowych linii

Vertical-Line-1 ma tylko jeden węzeł 4

Vertical-Line-2: ma tylko jeden węzeł 2

Vertical-Line-3: ma trzy węzły: 1,5,6

Vertical-Line-4: ma tylko jeden węzeł 3

Vertical-Line-5: ma tylko jeden węzeł 7

Teraz dla drzewa

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

Dla powyższego drzewa powinniśmy uzyskać wyjście każdego poziomu pionowego od góry do dołu i od lewej do prawej horixontalnie

8

4

2 9

1 5 6 lub 1 6 5 (ponieważ 6 i 5 są na tym samym poziomie pionowym, a ten sam HD, kolejność nie ma znaczenia)

3 10

7

11

Jednym ze sposobów jest po prostu utworzenie multimapy HD i przejście przez poziom, a następnie przeniesienie wartości do odpowiedniego indeksu HD. Wykonując to w kolejności poziomowej, zagwarantujemy, że odwiedzimy pionowo od góry do dołu. Następnie wydrukuj Węzły tworzą najniższe HD do najwyższych HD, spełniając nas od lewej do prawej.

Przeczytałem gdzieś, że możemy to zrobić w lepszy sposób, używając metody listy Doubly-Link lub czegoś podobnego.