Рубрики

Бинарное дерево с резьбой

Обход по порядку бинарного дерева может быть выполнен с помощью рекурсии или с использованием вспомогательного стека . Идея потоковых двоичных деревьев состоит в том, чтобы ускорить прохождение по порядку и сделать это без стека и без рекурсии. Бинарное дерево создается с помощью потоков, создавая все правильные дочерние указатели, которые обычно равны NULL, указывают на преемник-префикс узла (если он существует).

Существует два типа потоковых двоичных деревьев.
Однопотоковый: где указатели NULL вправо указывают на преемника inorder (если преемник существует)

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

Потоки также полезны для быстрого доступа к предкам узла.

Следующая диаграмма показывает пример однопоточного двоичного дерева. Пунктирные линии представляют потоки.

C представление резьбового узла
Ниже приведено C-представление однопоточного узла.

struct Node 

{

    int data;

    Node *left, *right;

    bool rightThread;  

}

Поскольку правый указатель используется для двух целей, логическая переменная rightThread используется для указания того, указывает ли правый указатель на правый дочерний элемент или преемник inorder. Точно так же мы можем добавить leftThread для двоичного дерева с двумя нитями.

Inorder Taversal с использованием потоков
Ниже приведен код C для обхода порядка в двоичном дереве с резьбой.

// Сервисная функция для поиска самого левого узла в дереве с корнем n

struct Node* leftMost(struct Node *n)

{

    if (n == NULL)

       return NULL;

  

    while (n->left != NULL)

        n = n->left;

  

    return n;

}

  
// C-код для выполнения обхода в поточном двоичном дереве

void inOrder(struct Node *root)

{

    struct Node *cur = leftmost(root);

    while (cur != NULL)

    {

        printf("%d ", cur->data);

  

        // Если этот узел является узлом потока, тогда перейдите к

        // преемник

        if (cur->rightThread)

            cur = cur->right;

        else // Остальное перейдем к самому левому потомку в правом поддереве

            cur = leftmost(cur->right);

    }

}

Следующая диаграмма демонстрирует обход порядка в порядке с использованием потоков.

Мы скоро обсудим вставку и удаление в двоичных деревьях с резьбой.

Источники:
http://en.wikipedia.org/wiki/Threaded_binary_tree
www.cs.berkeley.edu/~kamil/teaching/su02/080802.ppt

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Бинарное дерево с резьбой

0.00 (0%) 0 votes