Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > C/C++/С#


Ответ
 
Опции темы Опции просмотра
Старый 07.05.2013, 21:58   #1 (permalink)
Татьяна20
Новичок
 
Регистрация: 07.05.2013
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Удалить поддерево

Здравствуйте, подскажите, пожалуйста, как можно обойти дерево и посчитать минимальное отношение число листьев/число не листьев, а затем еще и удалить поддерево с этим отношением.
Мой код для построения дерева:
#include <stdlib.h>
#ifndef tree_h
#define tree_h
static long count_nodes=0;
class Tree{

public:
Tree():count(1){};
int value, key, count;
Tree *brother, *children;

Tree* CreateRoot(int);
void Add(Tree *, int, int);
Tree* FindKey(Tree*, int);
void Print(Tree*);
Tree* DeleteKey(Tree*, int);
void DeleteTree(Tree*);
void Delete(Tree*, int);
};

#endif

#include <iostream>
#include "tree.h"
#include <algorithm>
using namespace std;

Tree* Tree::CreateRoot(int value){
Tree* root = new Tree;
root->value = value;
root->brother = NULL;
root->children = NULL;
root->key = 1;
return root;
}

Tree * Tree::FindKey(Tree* root, int k){
Tree* temp = root;
Tree* found = NULL;
if(temp != NULL){
while((found == NULL) && (temp != NULL)){
if(temp->key == k){

found = temp;

}
else{

found = FindKey(temp->children, k);
}
temp = temp->brother;
}
}
return found;
}

void Tree::Add(Tree* root, int key, int value){
Tree* node = new Tree;
Tree* child = new Tree;
Tree* parent = FindKey(root, key);
node->brother = NULL;
node->children = NULL;
node->key = ++count;
node->value = value;
if(parent != NULL){
child = parent->children;
if(child == NULL){
parent->children = node;

}
else{
while(child->brother != NULL){

child = child->brother;


}

child->brother = node;

}
}
}

Tree* Tree:eleteKey(Tree* root, int k){
Tree * temp = new Tree;
Tree * found = new Tree;
found = NULL;
if(root != NULL){
if((root->brother != NULL) && (root->brother->key == k)){
found = root->brother;
root->brother = found->brother;
found->brother = NULL;
return found;
}
if((root->children != NULL) && (root->children->key == k)){
found = root->children;
root->children = found->brother;
found->brother = NULL;
return found;
}
temp = root->children;
while(temp != NULL){
found = DeleteKey(temp, k);
if(found != NULL) break;
temp = temp->brother;
}
}
return found;
}

void Tree:eleteTree(Tree* root){
Tree* temp = new Tree;
Tree* tree = new Tree;
temp = root;
while(temp != NULL){
DeleteTree(temp->children);
tree = temp;
temp = temp->brother;
delete tree;
}
root = NULL;
}

void Tree:elete(Tree* root, int k){
Tree * deleting = new Tree;
if(root->key == k){
DeleteTree(root);
}
else{
deleting = DeleteKey(root, k);
DeleteTree(deleting);
}
}

void Tree::Print(Tree* root){
Tree* temp = new Tree;
temp = root;
while(temp != 0){
cout <<temp->value<<endl;
Print(temp->children);
temp = temp->brother;
}
}

#include <iostream>
#include "tree.h"
using namespace std;

int main(){

Tree * root = new Tree;
root = root->CreateRoot(1);
Tree t;
t.Add(root, 1, 2); t.Add(root, 1, 3); t.Add(root, 1, 4);
t.Add(root, 2, 5); t.Add(root, 2, 6);
t.Add(root, 3, 7);
t.Add(root, 4, 8); t.Add(root, 4, 9); t.Add(root, 4, 10);
t.Add(root, 5, 11); t.Add(root, 5, 12);
t.Add(root, 7, 13); t.Add(root, 7, 14); t.Add(root, 7, 15);
t.Add(root, 8, 16);
t.Add(root, 10, 17); t.Add(root, 10, 18);

t.Print(root);
t.Print(root);
t.Delete(root, 1);
return 0;
}
Татьяна20 вне форума   Ответить с цитированием

Старый 07.05.2013, 21:58
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

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

Как удалить?
Как удалить свою учетную запись, удалить себя с форума?
Удалить PXE
Как удалить Indesign?
Как удалить баннер?
Как удалить ОС?

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 20:02.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.