Рубрики

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

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

Input : 
       1
    /    \
   2      3
Output
       2            2
    /    \   OR   /   \
   1      3      3     1 
  

Input : 
       1
     /    \
    5       8
  /  \     /  \
 2    4   9    10
Output :
    2                 4
  /    \            /    \     
 4       8    OR   2      8    OR .. (any tree with 
/  \    /  \      /  \   / \          same keys and 
5   1  9   10    5    1 9   10        no odd is parent
                                      of even)

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

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

Ниже приведена реализация идеи.

C ++

// Программа для погружения нечетных узлов в конец
// двоичное дерево
#include<bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    Node* left, *right;

};

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

Node* newnode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return node;

}

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

bool isLeaf(Node *root)

{

    return (root->left == NULL && root->right == NULL);

}

  
// Рекурсивный метод для поглощения дерева с нечетным корнем
// Этот метод предполагает, что поддеревья уже
// утонул. Этот метод похож на Heapify of
// Сортировка кучи

void sink(Node *&root)

{

    // Если NULL или лист, ничего не делать

    if (root == NULL || isLeaf(root))

        return;

  

    // если левое поддерево существует и левый потомок четный

    if (root->left && !(root->left->data & 1))

    {

        // меняем данные пользователя root на левого потомка и

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

        swap(root->data, root->left->data);

        sink(root->left);

    }

  

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

    else if(root->right && !(root->right->data & 1))

    {

        // меняем данные root с правым потомком и

        // исправить правильное поддерево

        swap(root->data, root->right->data);

        sink(root->right);

    }

}

  
// Функция для погружения всех нечетных узлов в конец двоичного файла
// дерево. Это делает прохождение заказа и вызывает раковину ()
// если найден какой-то нечетный узел

void sinkOddNodes(Node* &root)

{

    // Если NULL или лист, ничего не делать

    if (root == NULL || isLeaf(root))

        return;

  

    // Обрабатываем левое и правое поддеревья перед этим узлом

    sinkOddNodes(root->left);

    sinkOddNodes(root->right);

  

    // Если root нечетный, потопить его

    if (root->data & 1)

        sink(root);

}

  
// Вспомогательная функция для прохождения уровня порядка
// Уровень двоичного дерева по уровню. Эта функция используется
// здесь только для отображения модифицированного дерева.

void printLevelOrder(Node* root)

{

    queue<Node*> q;

    q.push(root);

  

    // Делаем прохождение ордера уровня

    while (!q.empty())

    {

        int nodeCount = q.size();

  

        // Печать по одному уровню за раз

        while (nodeCount)

        {

            Node *node = q.front();

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

            q.pop();

            if (node->left != NULL)

                q.push(node->left);

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;

        }

  

        // Разделитель строк для уровней

        printf("\n");

    }

}

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

int main()

{

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

            1

          / /

         5 8

        / / / /

       2 4 9 10 * /

  

    Node *root = newnode(1);

    root->left = newnode(5);

    root->right    = newnode(8);

    root->left->left = newnode(2);

    root->left->right = newnode(4);

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

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

  

    sinkOddNodes(root);

  

    printf("Level order traversal of modified tree\n");

    printLevelOrder(root);

  

    return 0;

}

python3

# Python3 программа для приема нечетных узлов
# в конец двоичного дерева

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

class newnode: 

  

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

    def __init__(self, key): 

        self.data = key 

        self.left = None

        self.right = None

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

def isLeaf(root):

    return (root.left == None and 

            root.right == None

  
# Рекурсивный метод, чтобы потопить дерево с нечетным корнем
# Этот метод предполагает, что поддеревья
# уже утонул. Этот метод похож на
# Heapify of Heap-Sort

def sink(root):

      

    # Если нет или это лист, ничего не делать

    if (root == None or isLeaf(root)):

        return

      

    # если существует левое поддерево и

    # левый ребенок чётный

    if (root.left and not(root.left.data & 1)):

          

        # поменять местами данные root с левым потомком

        # и исправить левое поддерево

        root.data, \

        root.left.data = root.left.data, \

                         root.data

        sink(root.left) 

          

    # если существует правильное поддерево и

    # Правильный ребенок ещё

    elif(root.right and not(root.right.data & 1)):

          

        # поменяйте местами данные root с нужным ребенком

        # и исправить правильное поддерево

        root.data, \

        root.right.data = root.right.data, \

                          root.data

        sink(root.right) 

  
# Функция для приема всех нечетных узлов в
# низ двоичного дерева. Оно делает
# обход почтового заказа и приемник вызовов ()
# если найден какой-то нечетный узел

def sinkOddNodes(root):

      

    # Если нет или это лист, ничего не делать

    if (root == None or isLeaf(root)):

        return

          

    # Обработка левого и правого поддеревьев

    # перед этим узлом

    sinkOddNodes(root.left) 

    sinkOddNodes(root.right) 

      

    # Если корень нечетный, опустите его

    if (root.data & 1):

        sink(root) 

  
# Вспомогательная функция для выполнения Level Order Traversal
Количество бинарных деревьев уровня за уровнем. Эта функция
# используется здесь только для отображения измененного дерева.

def printLevelOrder(root):

    q = []

    q.append(root) 

      

    # Сделать уровень прохождения заказа

    while (len(q)):

          

        nodeCount = len(q)

          

        # Печать по одному уровню за раз

        while (nodeCount):

            node = q[0

            print(node.data, end = " ")

            q.pop(0)

            if (node.left != None):

                q.append(node.left) 

            if (node.right != None):

                q.append(node.right) 

            nodeCount -= 1

          

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

        print()

  
Код водителя
"" "Построенное двоичное дерево

            1

        / /

        5 8

        / / / /

    2 4 9 10 "" "

root = newnode(1

root.left = newnode(5

root.right = newnode(8

root.left.left = newnode(2

root.left.right = newnode(4

root.right.left = newnode(9

root.right.right = newnode(10

  
sinkOddNodes(root) 

  

print("Level order traversal of modified tree"

printLevelOrder(root)

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


Выход :

Level order traversal of modified tree
2 
4 8 
5 1 9 10 

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

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

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

0.00 (0%) 0 votes