Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
1

Бинарные деревья

12.09.2019, 21:19. Просмотров 1312. Ответов 11
Метки нет (Все метки)

Выведите номера вершин, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search(TREE *tree, int value)
{
    static int sum = 0;
    if (tree != NULL)
    {
        search(tree->l,value);// обходим левое под дерево
        search(tree->r,value);// обходим правое под дерево
        if (tree->value == value)
            sum++;
    }
    return sum;
}
int main()
{
...
int k=search(tree, tree->value)-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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <fstream>
using namespace std;
 
struct TreeNode{
    int key;
    int depth;
    TreeNode *Left,*Right,*Parent;
};
void show(ostream & out ,TreeNode *tmp)
{
    if(!tmp)return;
    out<<tmp->key<<endl;
    if(tmp->Left)
    show(out,tmp->Left);
    if(tmp->Right)
    show(out,tmp->Right);
}
void AddNode(TreeNode *&pTree, int Key,TreeNode *Parent)
{
    if (pTree)
    {
        if (Key < pTree->key)
        {pTree->depth--;
        AddNode(pTree->Left, Key,pTree);}
        else if (Key > pTree->key)
        {pTree->depth++;
        AddNode(pTree->Right, Key,pTree);}
    }
    else{
        pTree = new TreeNode();
        pTree->key = Key;
        pTree->depth=0;
        pTree->Parent=Parent;
    }
}
TreeNode*  findRightMini(TreeNode *pTree){
    if(pTree->Left)
            return findRightMini(pTree->Left);
    else{
        return pTree;
    }
}
void findForDelet(TreeNode *tree,int *mass,int  &i)
{
    if(tree->Left!=NULL)
    {findForDelet(tree->Left,mass,i); }
    if(tree->depth){
        mass[++i]=tree->key;cout<<mass[i]<<" ";
    }
    if(tree->Right)
        findForDelet(tree->Right,mass,i);
    
}
void* NoNULL(void *a,void *b){
    if(a==NULL)return b;
    return a;
}
TreeNode * searchNode(TreeNode * ptmp, double key){
    if(!ptmp)return NULL;
    if (ptmp->key==key) return ptmp;
    return (TreeNode*)NoNULL(searchNode(ptmp->Left,key),searchNode(ptmp->Right,key));
}
void delet(TreeNode *pTree){    
    if(pTree==NULL)return;
    int *mass= new int[200];
    int n=0; 
    findForDelet(pTree,mass,n);
    
    if(n%2==0)return;
    TreeNode *tree1, *tree2;
        tree1=searchNode(pTree,mass[n/2+1]);
    
        
    if(tree1->Right){
        tree2=findRightMini(tree1->Right);
        if(tree1->Right->Left!=NULL)
               tree2->Parent->Left=tree2->Right;
        else   tree2->Parent->Right=tree2->Right;
        tree1->key=tree2->key;
    }
    else if(tree1->Left){
        tree1->key=tree1->Left->key;
        tree1->Right=tree1->Left->Right;
        tree1->Left=tree1->Left->Left;
    }
    }
int main(){
    ifstream in("in.txt");
    int key;
    TreeNode *tree = NULL; 
    
    while(in>>key){
        AddNode(tree, key, NULL);
    }
    if(tree!=NULL){
        delet(tree);
        ofstream out("out.txt");
        show(out,tree);
    }cin>>key;
    return 0;
}



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 <iostream>
 
using namespace std;
 
struct node
{
    int value;                           //значение вершины
    node *L, *R;                        //Левая и Правая часть дерева
};
 
 
void add(node **n, int aData) 
{
    if (*n == NULL)
    {
        *n = new node;                //Выделяем память, создаем новую ветку
        (*n)->value = aData;          //Кладем в выделенное место аргумент 
        (*n)->L = NULL;
        (*n)->R = NULL;              //Очищаем память для следующего роста
        return;
    }
    if (aData > (*n)->value )
    {
        add( &(*n)->R, aData );
    }
    if (aData <= (*n)->value)
    {
        add( &(*n)->L, aData);
    }
};
 
int  TreeCalc(node **n, int  allChild) {
    int ChLeft, ChRigth;
    if (*n == NULL) //дойдя до дна(низа древа).
    {   
        return allChild = 0;//потомков нет.
    }
    else                 //Если узел существует.
        
//Подсчёт количества потомков для текущего узла.
 ChLeft  = TreeCalc( &(*n)->L, allChild);  //Для левой ветви.
 ChRigth = TreeCalc( &(*n)->R, allChild); //Для правой ветви.
 
if ( (ChLeft-ChRigth==1 )||(ChRigth-ChLeft == 1) )
{
    cout<<"("<< (**n).value<<"): Потомков слева = "<< ChLeft<<" потомков справа = "<< ChRigth<<endl;
} 
 
//потомки текущей вершины = 1 + потомки слева + потомки справа
return allChild = 1 + ChLeft + ChRigth;
};
void freeMem(node **n)
{
    if (*n == NULL) {
        return;
    }
    freeMem(&(*n)->L);
    freeMem(&(*n)->R);
    free(*n);
    *n = NULL;
};
 
int main()
{
    setlocale(LC_ALL, "rus");
    node *tree = NULL;                  //Создаем пустое дерево 
    cout << "hello" << endl;
    int s;                              //Число, передаваемое в дерево
    cout << "Для окончание ввода введите любой символ" << endl;
    do
    {
        cout << "ведите число  ";
        cin >> s;                       //Считываем элемент за элементом
        if (cin) {
            add(&tree, s);
        }
        else {
            cout<<"ввод окончен"<<endl;
        }
    } while (cin);
    cout << "бинарное дерево построенно" << endl;
    TreeCalc(&tree, 0);
    //сюда добавить вывод сообщение если условие не выполнялось 
    freeMem(&tree);
    system("pause");
    return 0;
}
Что изменить или добавить?
C++
1
2
3
4
if ( (ChLeft-ChRigth==1 )||(ChRigth-ChLeft == 1) )
{
    cout<<"("<< (**n).value<<"): Потомков слева = "<< ChLeft<<" потомков справа = "<< ChRigth<<endl;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.09.2019, 21:19
Ответы с готовыми решениями:

Бинарные деревья С++
Добрый день! Дали такое задание на лабораторную работу. кое-что получилось, а в остальном прошу...

Бинарные деревья
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для каждой вершины...

Бинарные деревья
1)Написать программу подсчета числа вершин в бинарном дереве 2)Написать программу копирования...

Бинарные деревья
Имею три файла: Скажите пожалуйста почему я не могу создать э-т m?(Класс tree) Он мне пишет - ...

11
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
13.09.2019, 22:09  [ТС] 2
Что соединять, что убрать?
0
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
14.09.2019, 22:42  [ТС] 3
Извините пожалуйста, можете помочь.

Добавлено через 2 часа 53 минуты
Какой вариант лучше, что изменить, что добавить?

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
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXWORD 100
struct tnode {                // узел дерева
  char *word;                  // указатель на строку (слово)
  int count;                   // число вхождений
  struct tnode *left;          // левый потомок
  struct tnode *right;         // правый потомок
};
// Функция добавления узла к дереву
struct tnode *addtree(struct tnode *p, char *w) {
  int cond;
  if(p == NULL) {
    p = (struct tnode *)malloc(sizeof(struct tnode));
    p->word = strdup(w);
    p->count = 1;
    p->left = p->right = NULL;
  } else if((cond = strcmp(w, p->word)) == 0)
      p->count++;
  else if(cond < 0)
      p->left = addtree(p->left, w);
  else
     p->right = addtree(p->right, w);
  return p;
}
// Функция удаления поддерева
void freemem(tnode *tree) {
  if(tree!=NULL) {
      freemem(tree->left);
      freemem(tree->right);
      free(tree);
    }
}
// Функция вывода дерева
void treeprint(struct tnode *p) {
  if(p != NULL) {
    treeprint(p->left);
    printf(«%d %s\n», p->count, p->word);
    treeprint(p->right);
  }
}
int main() {
  struct tnode *root;
  char word[MAXWORD];
  root = NULL;
  do {
    scanf(«%s»,word);
    if(isalpha(word[0]))
      root = addtree(root, word);
  }while(word[0]!=0);    // условие выхода – ввод символа ‘0’
  treeprint(root);
  freemem(root);
  getchar();
  getchar();
  return 0;
}
Добавлено через 5 минут
Как вы думаете?

Добавлено через 1 час 30 минут
Поднять тему.

Добавлено через 5 часов 33 минуты
Исправьте пожалуйста.
0
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
15.09.2019, 07:31  [ТС] 4
Ну кто-нибудь помогите пожалуйста.
0
486 / 284 / 127
Регистрация: 30.10.2018
Сообщений: 1,309
15.09.2019, 08:06 5
Like_society, ты скинул четыри разных куска кода, которы между собой не клеяться, с каким именно помочь?
0
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
15.09.2019, 09:48  [ТС] 6
kitsoRik, Выведите номера вершин, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.

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 <iostream>
 
using namespace std;
 
struct node
{
    int value;                           //значение вершины
    node *L, *R;                        //Левая и Правая часть дерева
};
 
 
void add(node **n, int aData) 
{
    if (*n == NULL)
    {
        *n = new node;                //Выделяем память, создаем новую ветку
        (*n)->value = aData;          //Кладем в выделенное место аргумент 
        (*n)->L = NULL;
        (*n)->R = NULL;              //Очищаем память для следующего роста
        return;
    }
    if (aData > (*n)->value )
    {
        add( &(*n)->R, aData );
    }
    if (aData <= (*n)->value)
    {
        add( &(*n)->L, aData);
    }
};
 
int  TreeCalc(node **n, int  allChild) {
    int ChLeft, ChRigth;
    if (*n == NULL) //дойдя до дна(низа древа).
    {   
        return allChild = 0;//потомков нет.
    }
    else                 //Если узел существует.
        
//Подсчёт количества потомков для текущего узла.
 ChLeft  = TreeCalc( &(*n)->L, allChild);  //Для левой ветви.
 ChRigth = TreeCalc( &(*n)->R, allChild); //Для правой ветви.
 
if ( (ChLeft-ChRigth==1 )||(ChRigth-ChLeft == 1) )
{
    cout<<"("<< (**n).value<<"): Потомков слева = "<< ChLeft<<" потомков справа = "<< ChRigth<<endl;
} 
 
//потомки текущей вершины = 1 + потомки слева + потомки справа
return allChild = 1 + ChLeft + ChRigth;
};
void freeMem(node **n)
{
    if (*n == NULL) {
        return;
    }
    freeMem(&(*n)->L);
    freeMem(&(*n)->R);
    free(*n);
    *n = NULL;
};
 
int main()
{
    setlocale(LC_ALL, "rus");
    node *tree = NULL;                  //Создаем пустое дерево 
    cout << "hello" << endl;
    int s;                              //Число, передаваемое в дерево
    cout << "Для окончание ввода введите любой символ" << endl;
    do
    {
        cout << "ведите число  ";
        cin >> s;                       //Считываем элемент за элементом
        if (cin) {
            add(&tree, s);
        }
        else {
            cout<<"ввод окончен"<<endl;
        }
    } while (cin);
    cout << "бинарное дерево построенно" << endl;
    TreeCalc(&tree, 0);
    //сюда добавить вывод сообщение если условие не выполнялось 
    freeMem(&tree);
    system("pause");
    return 0;
}
Добавлено через 1 час 37 минут
Поднять тему.
0
486 / 284 / 127
Регистрация: 30.10.2018
Сообщений: 1,309
15.09.2019, 10:47 7
Like_society, да что не так? Скажи в чем проблема, не суй все всякие коды с интернета, скажи в чем проблема да и все.
0
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
15.09.2019, 10:50  [ТС] 8
kitsoRik, я не могу разобраться какой код подходит к моему заданию, или может быть исправить какой-то из этих кодов.
0
486 / 284 / 127
Регистрация: 30.10.2018
Сообщений: 1,309
15.09.2019, 10:56 9
Цитата Сообщение от Like_society Посмотреть сообщение
не могу разобраться какой код подходит к моему заданию
так не нужно смотреть какой подходит. Нужно самому писать. И условия задачи странное. Если в корневой ветке какая-то далекая ветка не имеет одного направления, то все рекурсивно не будут иметь, что выводит тогда?
0
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
15.09.2019, 11:06  [ТС] 10
kitsoRik, задание какое было, можете помочь, пожалуйста.
0
486 / 284 / 127
Регистрация: 30.10.2018
Сообщений: 1,309
15.09.2019, 11:09 11
Лучший ответ Сообщение было отмечено Like_society как решение

Решение

Like_society, какое есть, условия размытое, ведь может так случиться что 500 веток имеет две ветки, а 501 одну, и все 500 будут выводиться
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
#include <iostream>
#include <ctime>
 
int NUMBER = 0;
class Branch
{
public:
    int value;
    Branch* left;
    Branch* right;
 
    Branch() : value(NUMBER++), left(0), right(0)
    { }
};
 
void fillBranch(Branch* branch)
{
    if (rand() % 2 == 1)
    {
        branch->left = new Branch;
        fillBranch(branch->left);
    }
    if (rand() % 2 == 1)
    {
        branch->right = new Branch;
        fillBranch(branch->right);
    }
}
 
int calcBranchsCount(Branch* branch)
{
    int n = 0;
    if (branch->left)
    {
        n++;
        n += calcBranchsCount(branch->left);
    }
    if (branch->right)
    {
        n++;
        n += calcBranchsCount(branch->right);
    }
    return n;
}
 
void recursiveViewBranchs(Branch* root)
{
    int l = 0, r = 0;
    if (root->left)
    {
        recursiveViewBranchs(root->left);
        l = calcBranchsCount(root->left);
        l++;
    }
    if (root->right)
    {
        recursiveViewBranchs(root->right);
        r = calcBranchsCount(root->right);
        r++;
    }
 
    if(l != r)
    std::cout << "В " << root->value << " ветке разное кол-во веток[" << l << ',' << r << "];" << std::endl;
}
 
int main()
{
    srand(time(0));
    setlocale(0, "");
    Branch b;
    fillBranch(&b);
 
    recursiveViewBranchs(&b);
 
    return 0;
}
1
3 / 3 / 4
Регистрация: 19.01.2017
Сообщений: 416
15.09.2019, 11:12  [ТС] 12
kitsoRik, главное чтобы работало, и как видите это задание. Не важно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.09.2019, 11:12

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Бинарные деревья
Доброго времени суток, нужна помощь, дали задание...Вершина бинарного дерева содержит ключ, строку...

Бинарные деревья
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит указатель на строку и N...

бинарные деревья
Здравствуйте! Помогите пожалуйста доделать задачу на бинарные деревья. Язык только начали...

Бинарные деревья
Ребят, кто может помочь с написанием алгоритма программы? Сам код есть


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

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

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