Як обійти дерево масиву n?
Упорядкований обхід N-арного дерева
- Рекурсивно відвідайте першу дитину.
- Рекурсивно відвідайте другу дитину.
- …..
- Рекурсивно відвідати передостаннього дочірнього елемента.
- Роздрукуйте дані у вузлі.
- Рекурсивно відвідати останнього дочірнього елемента.
- Повторюйте описані вище кроки, доки не відвідаєте всі вузли.
Двома класичними методами обходу дерева є пошук у ширину (bfs), коли вузли на тому самому рівні або на відстані від кореня відвідуються перед переходом до наступного рівня; і пошук у глибину, коли відвідуються всі вузли гілки або один заданий шлях від кореня до листка перед переходом до наступного…
Що таке обхід дерева?
- Для Inorder ви переходите від лівого піддерева до кореня, а потім до правого піддерева.
- Для попереднього замовлення ви переходите від кореня до лівого піддерева, а потім до правого піддерева.
- Для пост-замовлення ви переходите від лівого піддерева до правого піддерева, а потім до кореня.
Попередній обхід загального дерева спочатку відвідує корінь дерева, потім виконує попередній обхід кожного піддерева зліва направо. Постпорядковий обхід загального дерева виконує постпорядковий обхід піддерев кореня зліва направо, а потім відвідує корінь.
Програма на C для обходу масиву
- Почніть цикл від 0 до N-1, де N — розмір масиву. for(i = 0; i < N; i++)
- Доступ до кожного елемента масиву за допомогою arr[index]
- Роздрукуйте елементи.