Рубрики

Двойное дерево

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

Итак, дерево …

    2
   / \
  1   3

изменяется на…

       2
      / \
     2   3
    /   /
   1   3
  /
 1

И дерево

            1
          /   \
        2      3
      /  \
    4     5

изменено на

               1
             /   \
           1      3
          /      /
        2       3
      /  \
     2    5
    /    /
   4   5
  /   
 4    

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

Реализация:

C ++

// C ++ программа для преобразования двоичного дерева в двойное дерево
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

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

node* newNode(int data); 

  
/ * Функция для преобразования дерева в двойное дерево * /

void doubleTree(node* Node) 

    node* oldLeft; 

      

    if (Node == NULL) return

      

    / * сделать поддеревья * /

    doubleTree(Node->left); 

    doubleTree(Node->right); 

      

    / * продублируем этот узел слева * /

    oldLeft = Node->left; 

    Node->left = newNode(Node->data); 

    Node->left->left = oldLeft; 

      

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ ФУНКЦИИ doubleTree () * /
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

      

    return(Node); 

  
/ * Учитывая двоичное дерево, вывести его узлы в порядке * /

void printInorder(node* node) 

    if (node == NULL) 

        return

    printInorder(node->left); 

    cout << node->data << " "

    printInorder(node->right); 

  

  
/ * Код водителя * /

int main() 

      

    / * Построенное двоичное дерево

                1

            / /

            2 3

        / /

        4 5

    * /

    node *root = newNode(1); 

    root->left = newNode(2); 

    root->right = newNode(3); 

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

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

      

    cout << "Inorder traversal of the original tree is \n"

    printInorder(root); 

      

    doubleTree(root); 

          

    cout << "\nInorder traversal of the double tree is \n"

    printInorder(root); 

      

    return 0; 

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

С

#include <stdio.h>
#include <stdlib.h>

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

   
/ * функция для создания нового узла дерева и возврата указателя * /

struct node* newNode(int data);

   

/ * Функция для преобразования дерева в двойное дерево * / 

void doubleTree(struct node* node) 

{

  struct node* oldLeft;

  

  if (node==NULL) return;

  

  / * сделать поддеревья * /

  doubleTree(node->left);

  doubleTree(node->right);

  

  / * продублируем этот узел слева * /

  oldLeft = node->left;

  node->left = newNode(node->data);

  node->left->left = oldLeft;

}

    

  

   
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ ФУНКЦИИ doubleTree () * /

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

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

   

  return(node);

}

  
/ * Учитывая двоичное дерево, вывести его узлы в порядке * /

void printInorder(struct node* node)

{

  if (node == NULL)

    return;

  printInorder(node->left); 

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

  printInorder(node->right);

}

   

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

int main()

{

   

  / * Построенное двоичное дерево

            1

          / /

        2 3

      / /

    4 5

  * /

  struct node *root = newNode(1);

  root->left        = newNode(2);

  root->right       = newNode(3);

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

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

   

  printf("Inorder traversal of the original tree is \n");

  printInorder(root);

  

  doubleTree(root);

    

  printf("\n Inorder traversal of the double tree is \n");  

  printInorder(root);

     

  getchar();

  return 0;

}

Джава

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

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Функция для преобразования дерева в двойное дерево * /

    void doubleTree(Node node) 

    {

        Node oldleft;

   

        if (node == null)

            return;

   

        / * сделать поддеревья * /

        doubleTree(node.left);

        doubleTree(node.right);

   

        / * продублируем этот узел слева * /

        oldleft = node.left;

        node.left = new Node(node.data);

        node.left.left = oldleft;

    }

   

    / * Учитывая двоичное дерево, вывести его узлы в порядке * /

    void printInorder(Node node) 

    {

        if (node == null)

            return;

        printInorder(node.left);

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

        printInorder(node.right);

    }

   

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

    public static void main(String args[]) 

    {

        / * Построенное двоичное дерево

              1

            / /

           2 3

         / /

        4 5

        * /

        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);

   

        System.out.println("Original tree is : ");

        tree.printInorder(tree.root);

        tree.doubleTree(tree.root);

        System.out.println("");

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

        tree.printInorder(tree.root);

    }

}

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

C #

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

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

using System;

  

class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree 

{

    Node root;

  

    / * Функция для преобразования дерева в двойное дерево * /

    void doubleTree(Node node) 

    {

        Node oldleft;

  

        if (node == null)

            return;

  

        / * сделать поддеревья * /

        doubleTree(node.left);

        doubleTree(node.right);

  

        / * продублируем этот узел слева * /

        oldleft = node.left;

        node.left = new Node(node.data);

        node.left.left = oldleft;

    }

  

    / * Учитывая двоичное дерево, вывести его узлы в порядке * /

    void printInorder(Node node) 

    {

        if (node == null)

            return;

        printInorder(node.left);

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

        printInorder(node.right);

    }

  

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

    public static void Main(String []args) 

    {

        / * Построенное двоичное дерево

            1

            / /

        2 3

        / /

        4 5

        * /

        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);

  

        Console.WriteLine("Original tree is : ");

        tree.printInorder(tree.root);

        tree.doubleTree(tree.root);

        Console.WriteLine("");

        Console.WriteLine("Inorder traversal of "

                              "double tree is : ");

        tree.printInorder(tree.root);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Original tree is : 
4 2 5 1 3 
Inorder traversal of double tree is : 
4 4 2 2 5 5 1 1 3 3 

Сложность времени: O (n) где n — количество узлов в дереве.

Ссылки:
http://cslibrary.stanford.edu/110/BinaryTrees.html

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы

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

Двойное дерево

0.00 (0%) 0 votes