Рубрики

Преобразовать двоичное дерево в двоичное дерево с резьбой | Установите 1 (используя очередь)

Мы обсудили резьбовое двоичное дерево . Идея потоковых двоичных деревьев состоит в том, чтобы ускорить прохождение по порядку и сделать это без стека и без рекурсии. В простом многопоточном двоичном дереве правые указатели NULL используются для хранения преемника. Везде, где указатель вправо равен NULL, он используется для хранения преемника.

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

Ниже приведена структура однопоточного двоичного дерева.

struct Node {

    int key;

    Node *left, *right;

  

    // Используется для указания, является ли правый указатель нормальным правом

    // указатель или указатель на преемника.

    bool isThreaded;

};

Как преобразовать данное двоичное дерево в двоичное дерево с резьбой?
Нам в основном нужно установить правильные указатели NULL для преемника. Сначала мы выполняем обход дерева по порядку и сохраняем его в очереди (мы также можем использовать простой массив), чтобы преемник наследника стал следующим узлом. Мы снова делаем обход по порядку и всякий раз, когда мы находим узел, право которого равно NULL, мы берем передний элемент из очереди и делаем его правым от текущего узла. Мы также устанавливаем для isThreaded значение true, чтобы указать, что правый указатель является многопоточной ссылкой.

Ниже приводится реализация вышеуказанной идеи.

C ++

/ * C ++ программа для преобразования бинарного дерева в потоковое дерево * /
#include <iostream>
#include <queue>

using namespace std;

  
/ * Структура узла в многопоточном двоичном дереве * /

struct Node {

    int key;

    Node *left, *right;

  

    // Используется для указания, является ли правый указатель нормальным

    // правый указатель или указатель на преемника.

    bool isThreaded;

};

  
// Вспомогательная функция для помещения узлов в порядке очереди

void populateQueue(Node* root, std::queue<Node*>* q)

{

    if (root == NULL)

        return;

    if (root->left)

        populateQueue(root->left, q);

    q->push(root);

    if (root->right)

        populateQueue(root->right, q);

}

  
// Функция для обхода очереди и создания дерева с резьбой

void createThreadedUtil(Node* root, std::queue<Node*>* q)

{

    if (root == NULL)

        return;

  

    if (root->left)

        createThreadedUtil(root->left, q);

    q->pop();

  

    if (root->right)

        createThreadedUtil(root->right, q);

  

    // Если правый указатель равен NULL, свяжите его с

    // изменить преемник и установить бит isThreaded.

    else {

        root->right = q->front();

        root->isThreaded = true;

    }

}

  
// Эта функция использует populateQueue () и
// createThreadedUtil () для преобразования заданного двоичного дерева
// на резьбовое дерево.

void createThreaded(Node* root)

{

    // Создать очередь для хранения обхода заказа

    std::queue<Node*> q;

  

    // Сохраняем обход заказа в очереди

    populateQueue(root, &q);

  

    // Ссылка NULL правых указателей на преемника

    createThreadedUtil(root, &q);

}

  
// Полезная функция для поиска самого левого узла в двоичном файле
// дерево с корнем «root». Эта функция используется в inOrder ()
Node* leftMost(Node* root)
{

    while (root != NULL && root->left != NULL)

        root = root->left;

    return root;

}

  
// Функция, выполняющая обход по порядку в двоичном дереве с резьбой

void inOrder(Node* root)

{

    if (root == NULL)

        return;

  

    // Находим самый левый узел в двоичном дереве

    Node* cur = leftMost(root);

  

    while (cur != NULL) {

        cout << cur->key << " ";

  

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

        // преемник

        if (cur->isThreaded)

            cur = cur->right;

  

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

            cur = leftMost(cur->right);

    }

}

  
// Вспомогательная функция для создания нового узла

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->left = temp->right = NULL;

    temp->key = key;

    return temp;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * 1

            / /

           2 3

          / / / /

         4 5 6 7 * /

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

  

    createThreaded(root);

  

    cout << "Inorder traversal of created threaded tree is\n";

    inOrder(root);

    return 0;

}

Джава

// Java-программа для преобразования двоичного дерева в потоковое дерево

import java.util.LinkedList;

import java.util.Queue;

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

class Node {

    int data;

    Node left, right;

  

    // Используется для указания, является ли правый указатель нормальным

    // правый указатель или указатель на преемника.

    boolean isThreaded;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

    Node root;

  

    // Вспомогательная функция для помещения узлов в порядке очереди

    void populateQueue(Node node, Queue<Node> q)

    {

        if (node == null)

            return;

        if (node.left != null)

            populateQueue(node.left, q);

        q.add(node);

        if (node.right != null)

            populateQueue(node.right, q);

    }

  

    // Функция для обхода очереди и создания дерева с резьбой

    void createThreadedUtil(Node node, Queue<Node> q)

    {

        if (node == null)

            return;

  

        if (node.left != null)

            createThreadedUtil(node.left, q);

        q.remove();

  

        if (node.right != null)

            createThreadedUtil(node.right, q);

  

        // Если правый указатель равен NULL, свяжите его с

        // изменить преемник и установить бит isThreaded.

        else {

            node.right = q.peek();

            node.isThreaded = true;

        }

    }

  

    // Эта функция использует populateQueue () и

    // createThreadedUtil () для преобразования заданного двоичного дерева

    // на резьбовое дерево.

    void createThreaded(Node node)

    {

        // Создать очередь для хранения обхода заказа

        Queue<Node> q = new LinkedList<Node>();

  

        // Сохраняем обход заказа в очереди

        populateQueue(node, q);

  

        // Ссылка NULL правых указателей на преемника

        createThreadedUtil(node, q);

    }

  

    // Полезная функция для поиска самого левого узла в двоичном файле

    // дерево с корнем «root». Эта функция используется в inOrder ()

    Node leftMost(Node node)

    {

        while (node != null && node.left != null)

            node = node.left;

        return node;

    }

  

    // Функция, выполняющая обход по порядку в двоичном дереве с резьбой

    void inOrder(Node node)

    {

        if (node == null)

            return;

  

        // Находим самый левый узел в двоичном дереве

        Node cur = leftMost(node);

  

        while (cur != null) {

            System.out.print(" " + cur.data + " ");

  

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

            // преемник

            if (cur.isThreaded == true)

                cur = cur.right;

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

                cur = leftMost(cur.right);

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

  

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

  

        tree.createThreaded(tree.root);

        System.out.println("Inorder traversal of created threaded tree");

        tree.inOrder(tree.root);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для конвертации
# Двоичное дерево с резьбовым деревом

  
# Структура узла в многопоточном двоичном дереве

class Node: 

  

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

          

        # Используется для указания правильности указателя

        # - нормальный правый указатель или указатель на

        # преемник.

        self.isThreaded = False

  
# Вспомогательная функция для размещения узлов
# в порядке очереди

def populateQueue(root, q): 

  

    if root == None: return

    if root.left: 

        populateQueue(root.left, q) 

    q.append(root)

      

    if root.right: 

        populateQueue(root.right, q) 

  
# Функция для прохождения очереди,
# и сделать дерево с резьбой

def createThreadedUtil(root, q): 

  

    if root == None: return

  

    if root.left: 

        createThreadedUtil(root.left, q) 

    q.pop(0

  

    if root.right: 

        createThreadedUtil(root.right, q) 

  

    # Если правый указатель отсутствует, свяжите его с

    # inorder преемник и установите бит isThreaded.

    else:

        if len(q) == 0: root.right = None

        else: root.right = q[0]

        root.isThreaded = True

  
# Эта функция использует populateQueue () и
# createThreadedUtil () для преобразования данного
# двоичное дерево в резьбовое дерево.

def createThreaded(root): 

  

    # Создать очередь для хранения обхода заказа

    q = [] 

  

    # Хранить обход заказа в очереди

    populateQueue(root, q) 

  

    # Ссылка Нет правильных указателей на преемника

    createThreadedUtil(root, q) 

  
# Полезная функция для поиска самого левого узла
# в двоичном дереве с корнем «root».
# Эта функция используется в inOrder ()

def leftMost(root): 

  

    while root != None and root.left != None

        root = root.left 

    return root 

  
# Функция для выполнения обхода заказа
# бинарного дерева с резьбой

def inOrder(root): 

  

    if root == None: return

  

    # Найти самый левый узел в двоичном дереве

    cur = leftMost(root) 

  

    while cur != None:

      

        print(cur.key, end = " "

  

        # Если этот узел является потоковым узлом,

        # затем перейдите к преемнику

        if cur.isThreaded: 

            cur = cur.right 

  

        # Иди к левому ребенку

        # в правом поддереве

        else

            cur = leftMost(cur.right) 

      
Код водителя

if __name__ == "__main__":

  

    root = Node(1

    root.left = Node(2

    root.right = Node(3

    root.left.left = Node(4

    root.left.right = Node(5

    root.right.left = Node(6

    root.right.right = Node(7

  

    createThreaded(root) 

  

    print("Inorder traversal of created"

                      "threaded tree is"

    inOrder(root) 

      
# Этот код предоставлен Rituraj Jain

C #

// C # программа для преобразования двоичного дерева в потоковое дерево

using System;

using System.Collections.Generic;

  
/ * Класс, содержащий левого и правого потомка текущего
значение узла и ключа * /

public class Node {

    public int data;

    public Node left, right;

  

    // Используется для указания, является ли правый указатель нормальным

    // правый указатель или указатель на преемника.

    public bool isThreaded;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree {

    Node root;

  

    // Вспомогательная функция для помещения узлов в порядке очереди

    void populateQueue(Node node, Queue<Node> q)

    {

        if (node == null)

            return;

        if (node.left != null)

            populateQueue(node.left, q);

        q.Enqueue(node);

        if (node.right != null)

            populateQueue(node.right, q);

    }

  

    // Функция для обхода очереди и создания дерева с резьбой

    void createThreadedUtil(Node node, Queue<Node> q)

    {

        if (node == null)

            return;

  

        if (node.left != null)

            createThreadedUtil(node.left, q);

        q.Dequeue();

  

        if (node.right != null)

            createThreadedUtil(node.right, q);

  

        // Если правый указатель равен NULL, свяжите его с

        // изменить преемник и установить бит isThreaded.

        else {

            if (q.Count != 0)

                node.right = q.Peek();

            node.isThreaded = true;

        }

    }

  

    // Эта функция использует populateQueue () и

    // createThreadedUtil () для преобразования заданного двоичного дерева

    // на резьбовое дерево.

    void createThreaded(Node node)

    {

        // Создать очередь для хранения обхода заказа

        Queue<Node> q = new Queue<Node>();

  

        // Сохраняем обход заказа в очереди

        populateQueue(node, q);

  

        // Ссылка NULL правых указателей на преемника

        createThreadedUtil(node, q);

    }

  

    // Полезная функция для поиска самого левого узла в двоичном файле

    // дерево с корнем «root». Эта функция используется в inOrder ()

    Node leftMost(Node node)

    {

        while (node != null && node.left != null)

            node = node.left;

        return node;

    }

  

    // Функция, выполняющая обход по порядку в двоичном дереве с резьбой

    void inOrder(Node node)

    {

        if (node == null)

            return;

  

        // Находим самый левый узел в двоичном дереве

        Node cur = leftMost(node);

  

        while (cur != null) {

            Console.Write(" " + cur.data + " ");

  

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

            // преемник

            if (cur.isThreaded == true)

                cur = cur.right;

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

                cur = leftMost(cur.right);

        }

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

  

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

  

        tree.createThreaded(tree.root);

        Console.WriteLine("Inorder traversal of created threaded tree");

        tree.inOrder(tree.root);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Inorder traversal of created threaded tree is
4 2 5 1 6 3 7

Преобразовать двоичное дерево в двоичное дерево с резьбой | Набор 2 (Эффективный)

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

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

Преобразовать двоичное дерево в двоичное дерево с резьбой | Установите 1 (используя очередь)

0.00 (0%) 0 votes