Рубрики

Извлечь листья бинарного дерева в двусвязный список

Учитывая бинарное дерево, извлечь все листья этого в D oubly L чернилами Спи (DLL). Обратите внимание, что DLL должна быть создана на месте. Предположим, что структура узлов DLL и Binary Tree одинакова, только значения левого и правого указателей различны. В DLL левый означает предыдущий указатель, а правый означает следующий указатель.

Let the following be input binary tree
        1
     /     \
    2       3
   / \       \
  4   5       6
 / \         / \
7   8       9   10


Output:
Doubly Linked List
785910

Modified Tree:
        1
     /     \
    2       3
   /         \
  4           6

Нам нужно пройти через все листья и соединить их, изменив их левый и правый указатели. Нам также нужно удалить их из двоичного дерева, изменив левый или правый указатели в родительских узлах. Там может быть много способов решить эту проблему. В следующей реализации мы добавляем листья в начало текущего связанного списка и обновляем заголовок списка, используя указатель на указатель заголовка. Поскольку мы вставляем в начале, нам нужно обрабатывать листья в обратном порядке. Для обратного порядка мы сначала пересекаем правое поддерево, а затем левое поддерево. Мы используем возвращаемые значения для обновления левого или правого указателя в родительских узлах.

C ++

// C ++ программа для извлечения листьев
// двоичное дерево в двусвязном списке
#include <bits/stdc++.h>

using namespace std;

  
// Структура для дерева и связанного списка

class Node 

    public:

    int data; 

    Node *left, *right; 

}; 

  
// Основная функция, которая извлекает все
// листья из заданного бинарного дерева.
// Функция возвращает новый корень
// Двоичное дерево (обратите внимание, что корень может измениться
// если бинарное дерево имеет только один узел)
// Функция также устанавливает * head_ref как
// глава двусвязного списка. левый указатель
// дерева используется как пред в DLL
// и правый указатель используется как следующий
Node* extractLeafList(Node *root, Node **head_ref) 

// Базовые случаи

if (root == NULL) return NULL; 

  

if (root->left == NULL && root->right == NULL) 

    // Этот узел будет добавлен

    // к двусвязному списку листьев,

    // установить правильный указатель этого узла

    // как предыдущий глава DLL. Мы

    // не нужно устанавливать левый указатель

    // как слева уже NULL

    root->right = *head_ref; 

  

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

    if (*head_ref != NULL) (*head_ref)->left = root; 

  

    // Изменить заголовок связанного списка

    *head_ref = root; 

  

    return NULL; // Возвращаем новый корень

  
// Повторение для правого и левого поддеревьев
root->right = extractLeafList(root->right, head_ref); 
root->left = extractLeafList(root->left, head_ref); 

  

return root; 

  
// Сервисная функция для выделения узла для двоичного дерева.

Node* newNode(int data) 

    Node* node = new Node();

    node->data = data; 

    node->left = node->right = NULL; 

    return node; 

  
// Сервисная функция для печати дерева в In-Order.

void print(Node *root) 

    if (root != NULL) 

    

        print(root->left); 

        cout<<root->data<<" "

        print(root->right); 

    

  
// Утилита для печати двойного связанного списка.

void printList(Node *head) 

    while (head) 

    

        cout<<head->data<<" "

        head = head->right; 

    

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

int main() 

    Node *head = NULL; 

    Node *root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

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

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

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

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

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

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

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

  

    cout << "Inorder Trvaersal of given Tree is:\n"

    print(root); 

  

    root = extractLeafList(root, &head); 

  

    cout << "\nExtracted Double Linked list is:\n"

    printList(head); 

  

    cout << "\nInorder traversal of modified tree is:\n"

    print(root); 

    return 0; 

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

С

// C программа для извлечения листьев двоичного дерева в двусвязный список
#include <stdio.h>
#include <stdlib.h>

  
// Структура для дерева и связанного списка

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Основная функция, которая извлекает все листья из данного двоичного дерева.
// Функция возвращает новый корень двоичного дерева (обратите внимание, что корень может измениться
// если бинарное дерево имеет только один узел) Функция также устанавливает * head_ref как
// глава двусвязного списка. левый указатель дерева используется как предыдущий в DLL
// и правый указатель используется как следующий

struct Node* extractLeafList(struct Node *root, struct Node **head_ref)

{

   // Базовые случаи

   if (root == NULL)  return NULL;

  

   if (root->left == NULL && root->right == NULL)

   {

       // Этот узел будет добавлен в двусвязный список

       // из листьев, установить правый указатель этого узла как предыдущий

       // глава DLL. Нам не нужно устанавливать левый указатель как левый

       // уже NULL

       root->right = *head_ref;

  

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

       if (*head_ref != NULL) (*head_ref)->left = root;

  

       // Изменить заголовок связанного списка

       *head_ref = root;

  

       return NULL;  // Возвращаем новый корень

   }

  

   // Повторение для правого и левого поддеревьев

   root->right = extractLeafList(root->right, head_ref);

   root->left  = extractLeafList(root->left, head_ref);

  

   return root;

}

  
// Сервисная функция для выделения узла для двоичного дерева.

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*)malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Сервисная функция для печати дерева в In-Order.

void print(struct Node *root)

{

    if (root != NULL)

    {

         print(root->left);

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

         print(root->right);

    }

}

  
// Утилита для печати двойного связанного списка.

void printList(struct Node *head)

{

     while (head)

     {

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

         head = head->right;

     }

}

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

int main()

{

     struct Node *head = NULL;

     struct Node *root = newNode(1);

     root->left = newNode(2);

     root->right = newNode(3);

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

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

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

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

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

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

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

  

     printf("Inorder Trvaersal of given Tree is:\n");

     print(root);

  

     root = extractLeafList(root, &head);

  

     printf("\nExtracted Double Linked list is:\n");

     printList(head);

  

     printf("\nInorder traversal of modified tree is:\n");

     print(root);

     return 0;

}

Джава

// Java-программа для извлечения листовых узлов из двоичного дерева
// используя двойной связанный список

   
// Узел бинарного дерева

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        right = left = null;

    }

}

   

public class BinaryTree 

{

    Node root;

    Node head; // будет указывать на голову DLL

    Node prev; // временный указатель

   

    // Основная функция, которая связывает список списка, который нужно просмотреть

    public Node extractLeafList(Node root) 

    {

        if (root == null)

            return null;

        if (root.left == null && root.right == null

        {

            if (head == null

            {

                head = root;

                prev = root;

            

            else 

            {

                prev.right = root;

                root.left = prev;

                prev = root;

            }

            return null;

        }

        root.left = extractLeafList(root.left);

        root.right = extractLeafList(root.right);

        return root;

    }

   

    // Печатает DLL в прямом и обратном направлениях.

    public void printDLL(Node head) 

    {

        Node last = null;

        while (head != null

        {

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

            last = head;

            head = head.right;

        }

    }

   

    void inorder(Node node) 

    {

        if (node == null)

            return;

        inorder(node.left);

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

        inorder(node.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.right = new Node(6);

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

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

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

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

   

        System.out.println("Inorder traversal of given tree is : ");

        tree.inorder(tree.root);

        tree.extractLeafList(tree.root);

        System.out.println("");

        System.out.println("Extracted double link list is : ");

        tree.printDLL(tree.head);

        System.out.println("");

        System.out.println("Inorder traversal of modified tree is : ");

        tree.inorder(tree.root);

    }

}

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

питон

# Программа Python для извлечения листовых узлов из двоичного дерева
# используя двойной связанный список

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Основная функция, которая извлекает все листья из данного двоичного дерева.
# Функция возвращает новый корень двоичного дерева (обратите внимание, что
# root может измениться, если Binary Tree имеет только один узел).
# Функция также устанавливает * head_ref в качестве заголовка двусвязного списка.
# левый указатель дерева используется как предыдущий в DLL
# и правый указатель используется как следующий

def extractLeafList(root):

      

    # Базовый вариант

    if root is None:

        return None

  

    if root.left is None and root.right is None:

        # Этот узел будет добавлен в дважды связанный

        # список листьев, установить указатель этого узла как

        # предыдущая глава DLL. Нам не нужно устанавливать налево

        # указатель как слева уже Нет

        root.right = extractLeafList.head

          

        # Изменить левый указатель предыдущей головы

        if extractLeafList.head is not None:

            extractLeafList.head.left = root

  

        # Изменить заголовок связанного списка

        extractLeafList.head = root

          

        return None # Возврат нового рута

  

    # Повторить для правого и левого поддерева

    root.right = extractLeafList(root.right)

    root.left = extractLeafList(root.left)

      

    return root 

  
# Утилита для печати дерева в InOrder

def printInorder(root):

    if root is not None:

        printInorder(root.left)

        print root.data,

        printInorder(root.right)

  

  

def printList(head):

    while(head):

        if head.data is not None:

            print head.data,

        head = head.right

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

extractLeafList.head = Node(None)

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(6)

root.left.left.left = Node(7)

root.left.left.right = Node(8)

root.right.right.left = Node(9)

root.right.right.right = Node(10)

  

print "Inorder traversal of given tree is:"

printInorder(root)

  

root = extractLeafList(root)

  

print "\nExtract Double Linked List is:"

printList(extractLeafList.head)

  

print "\nInorder traversal of modified tree is:"

printInorder(root)

C #

// C # программа для извлечения листа
// узлы из двоичного дерева
// используя двойной связанный список

using System;

  
// Узел бинарного дерева

public class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        right = left = null;

    }

}

  

public class BinaryTree 

{

    Node root;

    Node head; // будет указывать на голову DLL

    Node prev; // временный указатель

  

    // Основная функция, которая связывает

    // список списка для прохождения

    public Node extractLeafList(Node root) 

    {

        if (root == null)

            return null;

        if (root.left == null && root.right == null

        {

            if (head == null

            {

                head = root;

                prev = root;

            

            else

            {

                prev.right = root;

                root.left = prev;

                prev = root;

            }

            return null;

        }

        root.left = extractLeafList(root.left);

        root.right = extractLeafList(root.right);

        return root;

    }

  

    // Печатает DLL в обоих вперед

    // и обратные направления.

    public void printDLL(Node head) 

    {

        Node last = null;

        while (head != null

        {

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

            last = head;

            head = head.right;

        }

    }

  

    void inorder(Node node) 

    {

        if (node == null)

            return;

        inorder(node.left);

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

        inorder(node.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.right = new Node(6);

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

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

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

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

  

        Console.WriteLine("Inorder traversal of given tree is : ");

        tree.inorder(tree.root);

        tree.extractLeafList(tree.root);

        Console.WriteLine("");

        Console.WriteLine("Extracted double link list is : ");

        tree.printDLL(tree.head);

        Console.WriteLine("");

        Console.WriteLine("Inorder traversal of modified tree is : ");

        tree.inorder(tree.root);

    }

}

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


Выход:

Inorder Trvaersal of given Tree is:
7 4 8 2 5 1 3 9 6 10
Extracted Double Linked list is:
7 8 5 9 10
Inorder traversal of modified tree is:
4 2 1 3 6

Сложность времени: O (n), решение выполняет один обход заданного двоичного дерева.

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

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

Извлечь листья бинарного дерева в двусвязный список

0.00 (0%) 0 votes