печать общих элементов в двоичном дереве - PullRequest
Новая
       9

печать общих элементов в двоичном дереве

0 голосов
/ 30 сентября 2018

Я новичок в c ++ и пытаюсь реализовать структуру данных бинарного дерева поиска с использованием c ++. Следующий код предназначен для печати общих элементов в заданных двух бинарных деревьях поиска. Мой подход к этой проблеме заключается в том, что я создаю два массиваэлементов дерева двоичного поиска 1 и дерева двоичного поиска 2, т.е. .. arr1 [], arr2 []. В методе create_Array () я сохраняю значения обоих двоичных деревьев в отсортированном порядке,поэтому, когда я печатаю значения там, он печатает в отсортированном порядке, но когда я пытаюсь напечатать значения arr1 & arr2 в методе printcommon () , он печатает не в отсортированном порядке, а в том порядке, в котором он находится вДерево.

Пример ввода: -

6

5 6 4 1 2 3

8

6 94 10 2 3 5 9

Пример вывода

Дерево 1 = 1 2 3 4 5 6

Дерево 2 = 2 3 4 5 69 10

Общие узлы = 2 3 4 5 6

Фактический выход:

TREE 1 = 1 2 3 4 5 6

ДЕРЕВО2 = 2 3 4 5 6 9 10

Общие узлы =

для большей ясности строка, которую я прокомментировал в методе printcommon (), печатает arr1 [0] как 5, но этодолжен вывести 1, но в функции create_Array () закомментированная строка печатает идеально в отсортированном порядке, т.е. .. 1,2,3,4,5,6,2,3,4,5,6,9,10.Таким образом, если значение arr1 [0] равно 1 в методе create_Array (), то как оно стало равным 5 из arr1 [0] = 1. 

    #include <iostream>
    using namespace std;
    struct BstNode
    {
        int data;
        BstNode *left;
        BstNode *right;
    };
    int n1, n2;
    BstNode* getNewNode(int element)
    {
        BstNode* newNode = new BstNode;
        newNode->data = element;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    BstNode* create_Tree(BstNode* root, int element)
    {
        if (root == NULL)
        {
            root = getNewNode(element);
        }
        else if (element < root->data)
        {
            root->left = create_Tree(root->left, element);
        }
        else if (element > root->data)
        {
            root->right = create_Tree(root->right, element);
        }
        return root;
    }
    void InOrder_Traversal(BstNode * root)
    {
        if (root == NULL) return;
        else
            InOrder_Traversal(root->left);
        cout << root->data << " ";
        InOrder_Traversal(root->right);
    }
    void create_Array(BstNode * root, int arr[], int k)
    {
        if (root == NULL) return;
        create_Array(root->left, arr, k);
        arr[k] = root->data;
        /*cout << arr[k] << endl;*             /*please focus on this line
                                                prints in sorted order*/
        k++;
        create_Array(root->right, arr, k);
    }
    void printCommon(BstNode *root1, BstNode *root2)
    {
        int *arr1 = new int[n1];
        int i = 0;
        create_Array(root1, arr1, i);
        int *arr2 = new int[n2];
        int j = 0;
        create_Array(root2, arr2, j);
        cout << "Common Nodes=";
        /*cout << arr1[0];*/  /* this dosent print in sorted order*/                           
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                if (arr1[i] == arr2[j])
                {
                    cout << arr2[j] << " ";
                }
            }
        }
    }
    int main()
    {
        BstNode* root1 = NULL;
        BstNode* root2 = NULL;
        int n1, n2, ele;
        cin >> n1;
        for (int i = 0; i < n1; i++)
        {
            cin >> ele;
            root1 = create_Tree(root1, ele);
        }
        cin >> n2;
        for (int i = 0; i < n2; i++)
        {
            cin >> ele;
            root2 = create_Tree(root2, ele);
        }
        cout << "TREE 1=";
        InOrder_Traversal(root1);
        cout << endl;
        cout << "TREE 2=";
        InOrder_Traversal(root2);
        cout << endl;
        printCommon(root1, root2);
        return 0;
    }

1 Ответ

0 голосов
/ 30 сентября 2018

Не уверен, что это покрывает все ваши проблемы, но это ошибка, которая приводит к сбою кода.

Здесь: 

int n1, n2;  <<<<<<<< NOTICE
BstNode* getNewNode(int element)

вы делаете глобальные переменные n1 и n2, которые вы хотите использовать в некоторых функциях, таких как printCommon

Но здесь: 

int main()
{
    BstNode* root1 = NULL;
    BstNode* root2 = NULL;
    int n1, n2, ele;    <<<<<<<<<<<<< NOTICE
    cin >> n1;

вы создаете локальные переменные с тем же именем и принимаете входные данные в локальные переменные.

Поэтому, когда вызывается функция printcommon, она не использует входные значения, а использует глобальные переменные, которые имеют нулевое значение.

Это можно увидеть, выполнив cout << "n1 is " << n1 << endl; внутри функции и внутри main (сразу после чтения ввода).

РЕДАКТИРОВАТЬ

Вышесказанное не решило все проблемы.Другая проблема - это функция create_array, где индекс (он же k) неверен, то есть он не записывает в 0, 1, 2, 3, 4, ..., но возвращает ноль, перезаписывая предыдущие элементы.

Чтобы решить эту проблему, используйте указатель для индекса.Что-то вроде: 

void create_Array(BstNode * root, int arr[], int * k)
{
    if (root == NULL) return;
    create_Array(root->left, arr, k);
    arr[*k] = root->data;
    (*k)++;
    create_Array(root->right, arr, k);
}

и назовите это как 

create_Array(root1, arr1, &i);
                          ^ notice
...