Бинарное дерево , Обход в ширину через один.

[ben1992]

Добрый день!

Реализую стандартный алгоритм обхода бинарного дерева в ширину используя очередь. Алгоритм обхода в псевдокоде.

void startTreeWidth()
{
   core = Tree.core;  //получили корневой элемент дерева
  
   Query.add(core); // добавили элемент в очередь
 
   while(!Query.empty()) //крутим цикл пока в очереди есть элементы
   {
     current = Query.get();//берем из очереди
 
     print(current->value);//выводим на экран текущий элемент дерева
 
    //если есть левая ветвь
    if(currect->left != NULL){
        Query.add(current->left);  //добавляем в очередь левый элемент
    //если есть правая ветвь
    if(current->right != NULL){
        Query.add(current->right); // добавляем в очередь правый элемент
   }
}

Данный алгоритм работает и обходит дерево, как на верхней части картинки, сверху вниз по уровням и слева на право.

Вопрос, можно ли модифицировать данный алгоритм так, чтобы при обходе по уровням, мы сначала заполняли все левые элементы, а потом все правые(или наоборот, сначала правые, а потом левые), как на нижней части картинки?

[MBo]

Две очереди - для левых и для правых - использовать?

[ben1992]

Цитата MBo @ 06.07.16, 08:26

Две очереди - для левых и для правых - использовать?

А как согласовать их? Получается нужен будет двойной проход внутри уровня сделать.

Сообщение отредактировано: ben1992 - 06.07.16, 08:52

[MBo]

Достоверно не придумал, а поэкспериментировать не на чем пока. (я тут стратегией занимаюсь)

Есть ещё идея про использовании min-очереди по приоритетам, где приоритет формируется из текущего счетчика и для правых добавляется 2 в степени уровня.

[Akina]

Цитата ben1992 @ 06.07.16, 06:41

можно ли модифицировать данный алгоритм так, чтобы при обходе по уровням, мы сначала заполняли все левые элементы, а потом все правые(или наоборот, сначала правые, а потом левые), как на нижней части картинки?

Обход в ширину основывается на том, что обработка очередного узла продолжается до тех пор, пока у него есть дети, и только потом осуществляется переход к следующему узлу. При этом, что главное, возврата к ранее обработанному узлу не требуется.
Требуемая тебе схема обхода в корне отличается - именно тем, что требуется возврат к ранее обработанному узлу. Более того, твоя схема обхода, в отличие от обхода в ширину, ещё требует и хранения текущего уровня каждого узла - потому как возврат должен выполняться тогда, когда выполнен первый проход по всем узлам текущего уровня.
Возможная модификация - это обработка только левой ветви и помещение обрабатываемых узлов, имеющих, кроме того, правую ветвь, в FIFO-очередь. Если для очередного узла зарегистрировано увеличение текущего уровня - то перед его обработкой вызывается процедура, которая обрабатывает и очищает очередь, а текущий уровень инкрементируется. Правда, как реализовать учёт и хранение уровня узла, не очень понятно...

[Pavia]

ben1992
На картинке у вас изображён обход в глубину.

[Akina]

Цитата Pavia @ 06.07.16, 09:49

На картинке у вас изображён обход в глубину.

Нет, обход в глубину - это

Прикреплённая картинка

[ben1992]

Цитата Pavia @ 06.07.16, 09:49

ben1992
На картинке у вас изображён обход в глубину.

Википедия говорит, что это не так.

Цитата Akina @ 06.07.16, 09:46

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

Уровень каждого узла уже храниться в структуре, и его можно получить в любой момент.

[Akina]

Цитата ben1992 @ 06.07.16, 10:01

Уровень каждого узла уже храниться в структуре, и его можно получить в любой момент.

А тогда какие сложности? создавай вторую очередь и модифицируй код.

[ben1992]

Цитата Akina @ 06.07.16, 10:11

Цитата ben1992 @ 06.07.16, 10:01

Уровень каждого узла уже храниться в структуре, и его можно получить в любой момент.

А тогда какие сложности? создавай вторую очередь и модифицируй код.

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

[Akina]

Цитата ben1992 @ 06.07.16, 11:24

сложность в том, что я с ходу не могу представить, как его модифицировать

Ну я в сях и псевдокодах не силён, но счас по аналогии попробую нарисовать. Косяки потом сам поправишь.

[Akina]

core = Tree.core; // получили корневой элемент дерева
Query.add(core); // добавили элемент в очередь
do // понеслася
{
    if Query.empty() // если текущая очередь пуста, весь уровень обработан
    {
        while(!QueryLeft.empty())
        {
            Query.Add(QueryLeft.Get()); // переместить в основную очередь все левые элементы следующего уровня
        }
        while(!QueryRight.empty())
        {
            Query.Add(QueryRight.Get()); // а затем все правые
        }
        if Query.empty() // если и после этого основная очередь пуста
        {
            break; // то завершаем работу
        }
    }
    current = Query.get(); // берём очередной элемент
    print(current->value); // выводим его
    if(currect->left != NULL) // если есть левый элемент
    {
        QueryLeft.Add(current->left); // кладём его в левую очередь
    }
    if(current->right != NULL) // а если есть правый элемент
    {
        QueryRight.Add(current->right); // то его, соответственно, в очередь правую
    }
}

[ben1992]

Akina Заработал обход! Сейчас буду разбираться более подробно. Есть еще небольшой вопрос.

Если я заполняю дерево с нуля, по изначальному алгоритму, то просто ввожу дополнительную проверку, на наличие потомков у узла.

void startTreeWidth()
{
   core = Tree.core;  //получили корневой элемент дерева
 
   Query.add(core); // добавили элемент в очередь
 
   while(!Query.empty()) //крутим цикл пока в очереди есть элементы
   {
     current = Query.get();//берем из очереди
 
     print(current->value);//выводим на экран текущий элемент дерева
 
    //если есть левая ветвь
    if(currect->left != NULL){
        Query.add(current->left);  //добавляем в очередь левый элемент
    //если ветви нет,
    else {
        Tree.Add(current->left); //добавляем в левую ветвь
        break;
    }
    //если есть правая ветвь
    if(current->right != NULL){
        Query.add(current->right); // добавляем в очередь правый элемент
    //если ветви нет,
    else {
        Tree.Add(current->right); //добавляем в правую ветвь
        break;
    }
   }
}

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

[Akina]

ЯНХНП

[ben1992]

Перед тем, как обходить дерево, его необходимо заполнить. Заполняется дерево по тому же алгоритму, что и обходится. Отличие обхода от добавления, в первоначальном алгоритме, лишь в том, что если у текущего узла нет левого(или правого) потомков, то запихиваем туда новый элемент и принудительно выходим из цикла.

Я попробовал добавить аналогичное условие к вашему алгоритму:

core = Tree.core; // получили корневой элемент дерева
Query.add(core); // добавили элемент в очередь
do // понеслася
{
    if Query.empty() // если текущая очередь пуста, весь уровень обработан
    {
        while(!QueryLeft.empty())
        {
            Query.Add(QueryLeft.Get()); // переместить в основную очередь все левые элементы следующего уровня
        }
        while(!QueryRight.empty())
        {
            Query.Add(QueryRight.Get()); // а затем все правые
        }
        if Query.empty() // если и после этого основная очередь пуста
        {
            break; // то завершаем работу
        }
    }
    current = Query.get(); // берём очередной элемент
    print(current->value); // выводим его
    if(currect->left != NULL) // если есть левый элемент
    {
        QueryLeft.Add(current->left); // кладём его в левую очередь
    }
    else{
        //Здесь вставка левого элемента
        break;
    }
    if(current->right != NULL) // а если есть правый элемент
    {
        QueryRight.Add(current->right); // то его, соответственно, в очередь правую
    }
    else{
        //Здесь вставка правого элемента
        break;
    }
}

Однако, элементы в дерево добавляются, как при первоначальном алгоритме. Хотя, если "скормить" уже построенное дерево, до элементы перебираются через один, как надо.