Рубрики

Проверьте, является ли данное Двоичное Дерево SumTree

Напишите функцию, которая возвращает true, если заданное двоичное дерево равно SumTree, иначе false. SumTree — это двоичное дерево, в котором значение узла равно сумме узлов, присутствующих в его левом поддереве и правом поддереве. Пустое дерево — это SumTree, а сумма пустого дерева может рассматриваться как 0. Листовой узел также рассматривается как SumTree.

Ниже приведен пример SumTree.

          26
        /   \
      10     3
    /    \     \
  4      6      3

Способ 1 (простой)
Получить сумму узлов в левом поддереве и правом поддереве. Проверьте, равна ли вычисленная сумма данным root. Кроме того, рекурсивно проверьте, являются ли левое и правое поддеревья SumTrees.

С

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

  
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

  как root * /

int sum(struct node *root)

{

   if(root == NULL)

     return 0;

   return sum(root->left) + root->data + sum(root->right);

}

  
/ * возвращает 1, если свойство суммы верно для данного

    узел и оба его потомка * /

int isSumTree(struct node* node)

{

    int ls, rs;

  

    / * Если узел NULL или это листовой узел, то

       вернуть истину * /

    if(node == NULL ||

            (node->left == NULL && node->right == NULL))

        return 1;

  

   / * Получить сумму узлов в левом и правом поддеревьях * /

   ls = sum(node->left);

   rs = sum(node->right);

  

   / * если узел и оба его потомка удовлетворяют

       возвращение свойства 1 еще 0 * /

    if((node->data == ls + rs)&&

            isSumTree(node->left) &&

            isSumTree(node->right))

        return 1;

  

   return 0;

}

  
/ *

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

 с данными данными и 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);

}

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

int main()

{

    struct node *root  = newNode(26);

    root->left         = newNode(10);

    root->right        = newNode(3);

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

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

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

    if(isSumTree(root))

        printf("The given tree is a SumTree ");

    else

        printf("The given tree is not a SumTree ");

  

    getchar();

    return 0;

}

Джава

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

   
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

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

     как root * /

    int sum(Node node) 

    {

        if (node == null)

            return 0;

        return sum(node.left) + node.data + sum(node.right);

    }

   

    / * возвращает 1, если свойство суммы верно для данного

       узел и оба его потомка * /

    int isSumTree(Node node) 

    {

        int ls, rs;

   

        / * Если узел NULL или это листовой узел, то

           вернуть истину * /

        if ((node == null) || (node.left == null && node.right == null))

            return 1;

   

        / * Получить сумму узлов в левом и правом поддеревьях * /

        ls = sum(node.left);

        rs = sum(node.right);

   

        / * если узел и оба его потомка удовлетворяют

           возвращение свойства 1 еще 0 * /

        if ((node.data == ls + rs) && (isSumTree(node.left) != 0)

                && (isSumTree(node.right)) != 0)

            return 1;

   

        return 0;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(26);

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

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

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

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

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

   

        if (tree.isSumTree(tree.root) != 0)

            System.out.println("The given tree is a sum tree");

        else

            System.out.println("The given tree is not a sum tree");

    }

}

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


Выход:

The given tree is a SumTree 

Сложность времени: O (n ^ 2) в худшем случае. В худшем случае происходит перекос дерева.

Метод 2 (хитрый)
Метод 1 использует sum () для получения суммы узлов в левом и правом поддеревьях. Метод 2 использует следующие правила, чтобы получить сумму напрямую.
1) Если узел является листовым узлом, то сумма поддерева, укорененного в этом узле, равна значению этого узла.
2) Если узел не является листовым узлом, то сумма поддерева, укорененного с этим узлом, в два раза превышает значение этого узла (при условии, что у дерева с корнем из этого узла SumTree).

С

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

  
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

int isLeaf(struct node *node)

{

    if(node == NULL)

        return 0;

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

        return 1;

    return 0;

}

  
/ * возвращает 1, если свойство SumTree выполняется для заданного

    дерево * /

int isSumTree(struct node* node)

{

    int ls; // для суммы узлов в левом поддереве

    int rs; // для суммы узлов в правом поддереве

  

    / * Если узел NULL или это листовой узел, то

       вернуть истину * /

    if(node == NULL || isLeaf(node))

        return 1;

  

    if( isSumTree(node->left) && isSumTree(node->right))

    {

        // Получить сумму узлов в левом поддереве

        if(node->left == NULL)

            ls = 0;

        else if(isLeaf(node->left))

            ls = node->left->data;

        else

            ls = 2*(node->left->data);

  

        // Получить сумму узлов в правом поддереве

        if(node->right == NULL)

            rs = 0;

        else if(isLeaf(node->right))

            rs = node->right->data;

        else

            rs = 2*(node->right->data);

  

        / * Если данные root равны сумме узлов слева

           и правые поддеревья затем возвращают 1, иначе возвращают 0 * /

        return(node->data == ls + rs);

    }

  

    return 0;

}

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

 с данными данными и 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);

}

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

int main()

{

    struct node *root  = newNode(26);

    root->left         = newNode(10);

    root->right        = newNode(3);

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

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

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

    if(isSumTree(root))

        printf("The given tree is a SumTree ");

    else

        printf("The given tree is not a SumTree ");

  

    getchar();

    return 0;

}

Джава

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

   

  
/ * Узел двоичного дерева имеет данные, левый и правый дочерние элементы * /

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

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

    int isLeaf(Node node) 

    {

        if (node == null)

            return 0;

        if (node.left == null && node.right == null)

            return 1;

        return 0;

    }

   

    / * возвращает 1, если свойство SumTree выполняется для заданного

       дерево * /

    int isSumTree(Node node) 

    {

        int ls; // для суммы узлов в левом поддереве

        int rs; // для суммы узлов в правом поддереве

   

        / * Если узел NULL или это листовой узел, то

         вернуть истину * /

        if (node == null || isLeaf(node) == 1)

            return 1;

   

        if (isSumTree(node.left) != 0 && isSumTree(node.right) != 0

        {

            // Получить сумму узлов в левом поддереве

            if (node.left == null)

                ls = 0;

            else if (isLeaf(node.left) != 0)

                ls = node.left.data;

            else

                ls = 2 * (node.left.data);

   

            // Получить сумму узлов в правом поддереве

            if (node.right == null)

                rs = 0;

            else if (isLeaf(node.right) != 0)

                rs = node.right.data;

            else

                rs = 2 * (node.right.data);

               

            / * Если данные root равны сумме узлов слева

               и правые поддеревья затем возвращают 1, иначе возвращают 0 * /

            if ((node.data == rs + ls))

                return 1;

            else

                return 0;

        }

   

        return 0;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(26);

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

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

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

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

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

   

        if (tree.isSumTree(tree.root) != 0)

            System.out.println("The given tree is a sum tree");

        else

            System.out.println("The given tree is not a sum tree");

    }

}

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


Выход:

The given tree is a sum tree

Сложность времени: O (n)

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

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

Проверьте, является ли данное Двоичное Дерево SumTree

0.00 (0%) 0 votes