Подсчет равных узлов в двух бинарных деревьях - PullRequest
Новая
       25

Подсчет равных узлов в двух бинарных деревьях

0 голосов
/ 01 июля 2019

У меня следующая проблема, и я не могу ее решить: /

Есть два двоичных дерева, расположенных симметрично. Одно дерево Курс английского и еще одно дерево курса французского. Каждое дерево имеет следующие данные: идентификация и имя студента каждое дерево содержит студентов, зачисленных на эти курсы. Студент может существовать на 2х деревьях зачислены. Требуется сделать функцию, которая возвращает количество студентов, обучающихся на обоих курсах (что есть, они появляются на двух деревьях)

Как мне это решить?

Я сделал следующий код, используя функцию поиска по двум деревьям 

typedef struct Alumno
{
    int matricula;
    char nombre[30];
}Alumno;
typedef struct NodoA* PuntA;
typedef struct NodoA 
{
    Alumno TAlumno;
    PuntA izq;
    PuntA der;
}NodoA;

int buscar(PuntA & aluI, PuntA & aluF)
{
    Alumno datoI, datoF;
    PuntA r=raizI;
    int cont = 0;
    while((r!=NULL) && (r->datoI.matricula != aluF->datoF.matricula))
    {
        if(r->datoI.matricula < aluF->datoF.matricula)
            r=r->izq;
        else
            r=r->der;
    }
    if(r!=NULL)
        cont++;

}

Извините за язык кода.

PS: мне не нужно объединять два двоичных дерева, мне нужно посчитать равные узлы между двумя деревьями.

Edit1: я сделал этот код, переосмыслив упражнение: 

int buscar(PuntA raizFrances, int nro)
{
    PuntA r=raizFrances;
    while(r!=NULL && r->dato!=nro)
    {
        if(nro<r->dato)
            r=r->izq;
        else
            r=r->der;
    }
    if(r==NULL)
        return 0;
    else
        return 1;
}

void contarDobles(PuntA raizI) //MUESTRA PIMERO LA RAIZ Y DESPUES IZQUIERDA Y DESPUES DERECHA
{
    int contador = 0;
    int buscaEnF = 0;
    if(raizI!=NULL)
    {
        listarPre(raizI->izq); //1
        buscaEnF = buscar(raizI->dato, raizI->dato.matricula);
        if(buscaEnF == 1)
            contador++;
        listarPre(raizI->der);  //2
    }
    cout<<"El total de alumnos inscriptos en ambas materias es: "<<contador<<endl;
}

1 Ответ

0 голосов
/ 01 июля 2019

Общий алгоритм для решения этой проблемы:

  • Выберите элемент из Tree-1 и найдите его в Tree-2.
  • Поддержите счетчик для всех равных элементов.

Но у этого вопроса есть 2 аспекта:

Случай 1: Дерево не является деревом двоичного поиска

  • ВремяСложность: O (m * n)
  • Пространство Сложность: O (1)

Случай 2: Дерево является деревом двоичного поиска

  • Сложность времени: O (m * log (n))
  • Сложность пространства: O (1)

Гораздо лучшее решение заключается в следующем (относительноВремя):

  • Пройдите по меньшему дереву, скажем Tree-1 и сохраните его элементы на карте M.
  • Пройдите по большему дереву и найдите элементы, присутствующие на карте M.

  • Соответственно увеличить счетчик.

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

  • Сложность пространства: O (min (m, n))

где, m и n - размеры Tree-1 и Tree-2соответственно.

...