ЛЕВОСТОРОННИЙ ОБХОД

Для того, чтобы просмотреть информационные поля всех вершин построенного дерева, необходимо совершить его обход (посетить каждую его вершину).

ЛЕВОСТОРОННИЙ ОБХОД

В случае, когда бинарное дерево пусто, оно обходится без выполнения каких- либо действий. В противном случае существует несколько алгоритмов обхода. На этом шаге мы приведем алгоритм левостороннего обхода дерева:

посетите корень дерева;
обойдите левое поддерево;
обойдите правое поддерево.

Применяя алгоритм левостороннего обхода к бинарным деревьям I и II:

Рис.1. Примеры бинарных деревьев

посетим вершины в следующем порядке:

A B D M N E C

B D C E R

Запишем алгоритм в виде рекурсивной функции:

void ObhodLeft (node **w)// Левосторонний обход дерева.// *w - указатель на корень дерева.{ if (*w!=NULL) { cout<<(**w).Key<<" "; ObhodLeft (&((**w).Left)); ObhodLeft (&((**w).Right)); }}

КОНЦЕВОЙ ОБХОД

Существует алгоритм концевого обхода дерева, который заключается в следующем:

обойдите левое поддерево;
обойдите правое поддерево;
посетите корень дерева.

При таком алгоритме обход вершин бинарных деревьев I, II

Рис.1. Примеры бинарных деревьев

происходит в следующем порядке:

M N D E B C A

D E R C B

Запишем алгоритм в виде рекурсивной функции:

void ObhodEnd (node **w)// Концевой обход дерева.// *w - указатель на корень дерева.{ if (*w!=NULL) { ObhodEnd (&((**w).Left)); ObhodEnd (&((**w).Right)); cout<<(**w).Key<<" ";}}

12 Следующая ⇒