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

@Like_society · Регистрация: 19.01.2017

Студворк — интернет-сервис помощи студентам

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

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;
}

@Like_society · 13.09.2019, 22:09 **[ТС]**

Что соединять, что убрать?

@Like_society · 14.09.2019, 22:42 **[ТС]**

Извините пожалуйста, можете помочь.

Добавлено через 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 минуты
Исправьте пожалуйста.

@Like_society · 15.09.2019, 07:31 **[ТС]**

Ну кто-нибудь помогите пожалуйста.

@kitsoRik · 15.09.2019, 08:06

Like_society, ты скинул четыри разных куска кода, которы между собой не клеяться, с каким именно помочь?

@Like_society · 15.09.2019, 09:48 **[ТС]**

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 минут
Поднять тему.

@kitsoRik · 15.09.2019, 10:47

Like_society, да что не так? Скажи в чем проблема, не суй все всякие коды с интернета, скажи в чем проблема да и все.

@Like_society · 15.09.2019, 10:50 **[ТС]**

kitsoRik, я не могу разобраться какой код подходит к моему заданию, или может быть исправить какой-то из этих кодов.

@kitsoRik · 15.09.2019, 10:56

Сообщение от Like_society

не могу разобраться какой код подходит к моему заданию

так не нужно смотреть какой подходит. Нужно самому писать. И условия задачи странное. Если в корневой ветке какая-то далекая ветка не имеет одного направления, то все рекурсивно не будут иметь, что выводит тогда?

@Like_society · 15.09.2019, 11:06 **[ТС]**

kitsoRik, задание какое было, можете помочь, пожалуйста.

@kitsoRik · 15.09.2019, 11:09

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;
}

@Like_society · 15.09.2019, 11:12 **[ТС]**

kitsoRik, главное чтобы работало, и как видите это задание. Не важно.

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	13.09.2019, 22:09 [ТС]
	Что соединять, что убрать? 0

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	15.09.2019, 07:31 [ТС]
	Ну кто-нибудь помогите пожалуйста. 0

@kitsoRik 490 / 286 / 129 Регистрация: 30.10.2018 Сообщений: 1,309
	15.09.2019, 08:06
	Like_society, ты скинул четыри разных куска кода, которы между собой не клеяться, с каким именно помочь? 0

@kitsoRik 490 / 286 / 129 Регистрация: 30.10.2018 Сообщений: 1,309
	15.09.2019, 10:47
	Like_society, да что не так? Скажи в чем проблема, не суй все всякие коды с интернета, скажи в чем проблема да и все. 0

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	15.09.2019, 10:50 [ТС]
	kitsoRik, я не могу разобраться какой код подходит к моему заданию, или может быть исправить какой-то из этих кодов. 0

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	15.09.2019, 11:06 [ТС]
	kitsoRik, задание какое было, можете помочь, пожалуйста. 0

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	15.09.2019, 11:12 [ТС]
	kitsoRik, главное чтобы работало, и как видите это задание. Не важно. 0

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

Решение