Найти длину пути от корня до ближайшей вершины с заданным количеством появлений слова в тексте - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте, можете разъяснить, как правильно работать с бинарным деревом, как его можно применить на практике, у меня получилось написать функция ввода и вывода дерева, как можно реализовать именно задание
#include "stdafx.h"
#include<stdio.h> 
#include<stdlib.h> 

//структура, описывающая узел бинарного дерева 
struct node
{   
    int key;
    struct node*left,*right;
}proot; 
 
//вводим новый тип - указатель на узел дерева 
typedef struct node* tree; 

void add(tree*proot,int x); 
void print(tree root); 
 
int main() 
{ 
        int i, k, n; 
        tree root = NULL; 
        char name[]="tree.txt"; 
        printf("n = ");
        scanf("%d", &n); 
        for(i=0;i<n;i++) 
        { 
            printf("k = ");
            scanf("%d",&k); 
        }
        print(root); 
        printf("\n\n");
}

void add(tree*proot,int x) 
{ 
 
    if (*proot==NULL) 
    { 
         //если дерево пустое - создаем узел 
        *proot=(tree)malloc(sizeof(struct node)); 
        (*proot)->key=x; 
        (*proot)->left=(*proot)->right=NULL; 
    } 
    else 
        if (x<(*proot)->key) 
        //если x меньше корня, то добавляем рекурсивно 
        //в левое поддерево 
        add(&(*proot)->left,x); 
        else 
        //если x не меньше корня, то добавляем рекурсивно 
        //в правое поддерево 
        add(&(*proot)->right,x);

}
 
void print(tree root) 
{ 
 
    if (root!=NULL) //если дерево не пусто 
    {  
        print(root->left);//рекурсивно печатаем левое поддерево
        printf("%d\t",root->key);//сам ключ корня
        print(root->right);//рекурсивно печатаем правое поддерево 
    } 
}

Решение задачи: «Найти длину пути от корня до ближайшей вершины с заданным количеством появлений слова в тексте»

textual
Листинг программы
int get_way(tree root, int key)
{
    int count = 0;
    tree tmp = root;
    while(tmp)
    {
        count++;
        if(tmp->key > key)
            tmp = tmp->left;
        else if(tmp->key < key)
            tmp = tmp->right;
        else return count;
    }
   return 0;
}

Объяснение кода листинга программы

В данном коде функция get_way принимает два аргумента: root (корень дерева) и key (ключ, значение которого мы хотим найти в дереве).

  1. Создается переменная count и инициализируется нулем. Она будет использоваться для подсчета количества элементов на пути от корня до листьев.
  2. Создается временная переменная tmp, которая будет использоваться для хранения текущего элемента на пути.
  3. Запускается цикл while, который будет выполняться до тех пор, пока tmp не станет равным NULL (т.е. пока мы не достигнем листа).
  4. Внутри цикла увеличивается значение переменной count на единицу.
  5. Сравнивается значение ключа текущего элемента tmp с ключом, который мы ищем (key). Если ключ текущего элемента больше ключа, то tmp перемещается на левое поддерево. Если ключ текущего элемента меньше ключа, то tmp перемещается на правое поддерево. Если ключи равны, то функция возвращает значение count (количество элементов на пути до этого узла).
  6. Если после выполнения цикла while tmp все еще не равно NULL, значит мы не нашли узел с ключом равным key. В этом случае возвращается ноль. Таким образом, функция get_way возвращает длину пути от корня до ближайшей вершины с заданным ключом.

Оцени полезность:

9   голосов , оценка 3.556 из 5
Похожие ответы