|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.06.2011, 18:22 | #1 |
Новичок
Джуниор
Регистрация: 24.05.2011
Сообщений: 1
|
Расчет уровней в бинарном дереве
Всем, доброго вечера!
При написании программы построения, вывода на экран и подсчета числа уровней в бинарном дереве возникли проблемы с подсчетом уровней, причем подсчет уровней реализован не для структурированного дерева, а следующего типа (Вид слева, корень дерева = 5): ____7 __6 5 __4 ____3 Листинг: файл "1a.h" #ifndef TEST2_H_INCLUDED #define TEST2_H_INCLUDED typedef struct _node *TreeNode; typedef struct _root Tree; struct _root { TreeNode root; }; struct _node { double data; TreeNode left; TreeNode right; }; void CreateTree(Tree*); void Insert(Tree*, double); void Print(Tree*); int Depth(Tree*); #endif // TEST2_H_INCLUDED файл "2a.c" #include <stdio.h> #include "3a.c" int main(){ int n; double x; Tree t; CreateTree(&t); printf("|------------------------|\n"); printf("| Main menu: |\n"); printf("| 1. Insert element |\n"); printf("| 2. Print Tree |\n"); printf("| 3. Depth |\n"); printf("| 0. Exit |\n"); printf("|------------------------|\n"); while(~n && ~scanf("%d", &n)){ switch(n){ case 1: printf("Enter element to add: "); scanf("%lf", &x); Insert(&t, x); break; case 2: Print(&t); break; case 3: printf ("Depth of tree is: %d\n", Depth(&t)); printf("%d\n",h2); printf("%d\n",h1); h3=h2=h1=0; break; case 0: n = -1; break; default: printf("Nothing\n"); break; } } return 0; } файл "3a.c" #include <stdio.h> #include <stdlib.h> typedef struct _node *TreeNode; typedef struct _root Tree; struct _root { TreeNode root; }; struct _node { double data; TreeNode left; TreeNode right; }; TreeNode malloc_node(){ TreeNode n = (TreeNode)malloc(sizeof(struct _node)); n->left = n->right = NULL; // -> обращение к указателю return n; } void CreateTree(Tree *t){ t->root = NULL; } void ins(TreeNode *t, double k){ if(k < (*t)->data){ if((*t)->left){ ins(&((*t)->left), k); }else{ (*t)->left = malloc_node(); (*t)->left->data = k; } }else if(k > (*t)->data){ if((*t)->right){ ins(&((*t)->right), k); }else{ (*t)->right = malloc_node(); (*t)->right->data = k; } } } void Insert(Tree *t, double k){ if(!t->root){ t->root = malloc_node(); t->root->data = k; }else{ ins(&(t->root), k); } } void _print(TreeNode t, int tab){ if(t){ _print(t->right, tab + 2); int i; for(i = 0; i < tab; i++){ putchar(' '); } i = 0; printf("%.0f\n", t->data); _print(t->left, tab + 2); } } void Print(Tree *t){ _print(t->root, 0); } int h1=0, h2=0, h3=0; int Depth1(TreeNode *t) { if (t==NULL) h3=0; if ((*t)->left != NULL) { h1++; Depth1(&(*t)->left); } if ((*t)->right != NULL) { h2++; Depth1(&(*t)->right); } } int Depth(Tree *t) { if(t->root){ Depth1(&(t->root)); if (h1>h2) h3=h1; else h3=h2; return h3; } else return 0; } Красным выделена часть реализации подсчета числа уровней в бинарном дереве. Подробнее о работе программы и о проблеме: меню: по значению "1" - построение дерева по значению "2" - распечатать дерево по значению "3" - подсчет уровней дерева, начиная с "0" уровня Если построить дерево: ______8 ____7 __6 5 __4 то, подсчет числа узлов будет равен: 3 уровня (right) 1 уровень (left), что будет правильным , но если добавить 2 и 3, то получился след. дерево: ______8 ____7 __6 5 __4 _____3 ____2 и число уровней будет: 4 2 т.е. при оптимизации дерева, новое значение добавляется к right. Сталкивался кто-нибудь с такой проблемой или реализовывал похожий метод? Нужна помощь, ребят! |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Посчитать количество вершин в бинарном дереве | goo | Фриланс | 2 | 26.02.2011 20:01 |
Посчитать количество вершин в бинарном дереве (процедура) | goo | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 26.02.2011 14:35 |
Поиск в бинарном дереве не по ключу | lebrosha | Помощь студентам | 2 | 26.05.2009 15:32 |
Удаление вершины в бинарном дереве | lebrosha | Помощь студентам | 2 | 24.05.2009 13:51 |