Дърветата са една от относително сложните структури от данни, с които ще трябва да се справите като програмист. В началото може да изглеждат трудни, но след като разберете тънкостите им, ще стане много по-лесно. Едно дърво не е нищо друго освен куп възли, йерархично свързани заедно.

Нека видим как да извършим обхождане по ред на дърво. Но защо да пресичате дърво, може да попитате. Човек може да прекоси едно дърво, за да търси нещо между другото. Но да научите как да преминете през дърво също е чудесен начин да се запознаете със структурата на данните на дървото.

Нека сега научим как работи In Order traversal. В Order traversal означава, че посещаваме възлите на дърво отляво надясно. Първият възел, който посещаваме, е най-левият възел на дървото и след това неговият корен или родителски възел и десният дъщерен възел.

Например, ако нашето дърво изглежда така:

       1
     /   \
    6     4
   /
  8

Първият възел, който ще посетим в нашето обхождане, е 8, след това 6, след това 1 и след това 4.

Нека вземем за пример по-голямо дърво, за да разберем по-добре как работи обхождането по ред.

       1
     /   \
    6     4
   /  \
  8    5
      / \
     3   9

В този случай нашите пресичани възли ще изглеждат нещо като: 8,6,3,5,9,1,4

Ще използваме стекове, за да ни помогнат да прекосим дървото.

Програмата

Номерът е да отидете до възела най-отляво и да се върнете обратно към основния възел, отпечатвайки десния и родителския възел на всички възли.

Първо ще поставим всички леви възли в стека. След като достигнем дъното, т.е. след като няма повече леви възли, започваме да отпечатваме възлите един по един и да проверяваме дали възелът има десен възел. Ако стане, тогава отново започваме да съхраняваме всички леви възли на десния възел, който току-що срещнахме, и процесът продължава, докато стекът се изпразни.

Стъпка 1: Създаване на стека и превключвателя

def inOrder(root):
    stack=[]
    switch=1

Ще използваме превключвател, за да прекратим цикъла, след като стекът е празен и не ни останат повече възли за преминаване.

Стъпка 2: Примката

while(switch==1):
        if (root is not None):
            stack.insert(0,root)    
            root=root.left

Тук преминаваме през дървото и подреждаме левите възли, докато минаваме през тях, докато стигнем дъното, т.е. Няма.

Стъпка 3: Извадете възела | Отпечатайте | Отидете до десния възел

while(switch==1):
        if (root is not None):
            stack.insert(0,root)    
            root=root.left
        else:    
            if (len(stack)<=0):
                switch=0 
            else:
                root=stack.pop(0)
                print(root.info)
                root=root.right

Ако правилният възел не съществува, текущият възел ще стане нулев, което ще доведе до изваждане на друг възел от стека.

Програмата

def inOrder(root):
    stack=[]
    switch=1
    while(switch==1):
        if (root is not None):
            stack.insert(0,root)    
            root=root.left
        else:    
            if (len(stack)<=0):
                switch=0 
            else:
                root=stack.pop(0)
                print(root.info)
                root=root.right

И това е всичко. Сега знаете как работи In Order traversal.