Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
coldheart
0 / 0 / 0
Регистрация: 17.10.2016
Сообщений: 5
1

Поиск вершин в бинарном дереве по условию

22.10.2016, 20:33. Просмотров 526. Ответов 3
Метки нет (Все метки)

Задание:
Дана последовательность чисел. Написать программу формирования и вывода бинарного дерева на экран.
Найти в построенном бинарном дереве все вершины, для которых выполняется условие: количество потомков
в левом поддереве отличается от количества потомков в правом поддереве на 1. После выполнения программы
очистить память, занятую древовидной структурой.

Дерево строится, выводится, прямым обходом обходится. Как искать такие вершины понять не могу - пожалуйста помогите.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <Windows.h>
 
typedef struct binarytree {
    int Data; 
    binarytree * Left; 
    binarytree * Right; 
} BinaryTree;
 
void Create(BinaryTree** p, int x) {
if(!(*p)) {
    BinaryTree* pnew = (BinaryTree*)
    malloc(sizeof(BinaryTree));
    pnew->Data = x;
    pnew->Left = pnew->Right = NULL;
    *p = pnew;
} else {
    if((*p)->Data> x)
        Create(&((*p)->Left), x);
    else
        Create(&((*p)->Right), x);
    }
}
 
void Vyvod (BinaryTree **p,int l) {
int i;
if (*p!=NULL) {
    Vyvod (&((*p)->Right),l+1);
    for (i=0; i<l; i++)
        printf(" ");
    printf("%d\n",(*p)->Data);
    Vyvod (&((*p)->Left),l+1);
    }
}
 
 empty_tree(BinaryTree * Node) {
    if(Node==NULL) 
        return true;
    else 
        return false;
}
 
void PreOrder_BinaryTree(BinaryTree* Node) {
    if (Node != NULL) {
        printf ("%3ld",Node->Data);
        PreOrder_BinaryTree(Node->Left);
        PreOrder_BinaryTree(Node->Right);
    }
}
 
BinaryTree* Delete_BinaryTree(BinaryTree* Node) {
if (Node != NULL) {
    Delete_BinaryTree(Node->Left);
    Delete_BinaryTree(Node->Right);
    free(Node);
    }
    return NULL;
}
 
int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int i,n,temp;
    BinaryTree * Root;
    Root=NULL;
    printf("Число элементов дерева\t"); scanf("%d",&n);
    for(i=0;i<n;i++) {
        scanf("%d",&temp);
        Create(&Root,temp);
    }
    Vyvod(&Root,0);
    printf("\nПрямой обход бинарного дерева\n");
    PreOrder_BinaryTree(Root);
    if(empty_tree(Root)) {
        printf("\nДерево пусто!\n");
        getch();
        return 0;
    }
    Root=Delete_BinaryTree(Root);
    if(empty_tree(Root))
    printf("\nПамять очищена!\n");
    getch();
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2016, 20:33
Ответы с готовыми решениями:

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

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

Найти максимальный элемент в бинарном дереве
тип информационного поля int*, найти маскимальный элемент в дереве. (помогите, пожалуйста, нужен...

Нахождение следующего и предыдущего элемента в бинарном дереве поиска
Нужны 2 ф-ции: нахождение следующего и предыдущего элемента в дереве. Вот мой код. Помогите...

Подсчитать количество узлов с четными ключами в бинарном дереве
Сделала так: struct Item { int key; char* string; Item* left; Item* right; }; __________...

3
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4854 / 2497 / 697
Регистрация: 18.10.2014
Сообщений: 4,333
22.10.2016, 22:09 2
Цитата Сообщение от coldheart Посмотреть сообщение
Дана последовательность чисел. Написать программу формирования и вывода бинарного дерева на экран.
В вашем коде вы формируете упорядоченное бинарное дерево, т.е. дерево сортировки. В задании однако ни слова об этом не сказано ни о какой упорядоченности дерева. Это подразумевается?
0
coldheart
0 / 0 / 0
Регистрация: 17.10.2016
Сообщений: 5
22.10.2016, 22:25  [ТС] 3
Задание приведено дословно. Код написан с учетом примеров по теме бинарных деревьев из учебно-методического пособия, по которому необходимо сделать данное задание. Если в результате формируется дерево сортировки, значит так и должно быть.
0
coldheart
0 / 0 / 0
Регистрация: 17.10.2016
Сообщений: 5
24.10.2016, 08:47  [ТС] 4
Никто не понимает задание? Я тоже не понимаю...
0
24.10.2016, 08:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2016, 08:47

В заданном бинарном дереве найти первое вхождение заданного элемента
в заданном бинарном дереве найти первое вхождение заданного элемента и напечатать пройденные при...

В бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины
В заданном непустом бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины...

Подсчет вершин в бинарном дереве
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru