Дерево общего вида#include <stdio.h>
#include <stdlib.h>
int big_deep;
typedef struct Tree
{
int key;
int length_sons;
struct Tree* parent;
struct Tree* *sons;
}node;
void create_tree(node **tree, int key)
{
node *tmp_tree = malloc(sizeof(node));
tmp_tree->key = key;
tmp_tree->length_sons = 0;
tmp_tree->parent = NULL;
tmp_tree->sons = NULL;
*tree = tmp_tree;
}
node* find_leaf(node **tree, int leaf) {
node *work_tree = *tree;
if(work_tree == NULL) return NULL;
if(work_tree->key == leaf) return work_tree;
node *where = NULL;
if(work_tree->sons) {
int length = work_tree->length_sons;
for(int i=0; i<length; i++) {
where = find_leaf(&work_tree->sons[i], leaf);
if( (where) && (where->key == leaf) ) return where;
}
}
return work_tree;
}
void add_node(node **tree, int key, int father)
{
node *work_tree = find_leaf(tree, father);
node *tmp_node = malloc(sizeof(node));
tmp_node->key = key;
tmp_node->length_sons = 0;
tmp_node->parent = work_tree;
tmp_node->sons = NULL;
if(work_tree->sons){
int length = work_tree->length_sons;
work_tree->sons[length] = tmp_node;
work_tree->length_sons+=1;
}
else {
work_tree->sons = malloc(sizeof(node));
work_tree->sons[0] = tmp_node;
work_tree->length_sons+=1;
}
}
void delete_node(node **tree, int key)
{
node *work_tree = find_leaf(tree, key);
if(work_tree->length_sons > 0) {
int length = work_tree->length_sons;
for(int i = (length-1); i>=0 ; i-- ) delete_node(&work_tree->sons[i], work_tree->sons[i]->key);
length--;
}
node *parent_tree = work_tree->parent;
if(parent_tree != NULL) {
int length = parent_tree->length_sons;
int position = -1;
for(int i=0; i<length; i++) {
if(parent_tree->sons[i]->key == key) position = i;
}
if(position < (length-1) ) {
for(int i = (position+1) ; i < length ; i++ ){
parent_tree->sons[i-1] = parent_tree->sons[i];
}
}
parent_tree->sons[length-1] = NULL;
parent_tree->length_sons = length-1;
}
free(work_tree);
work_tree = NULL;
}
void print_tree(node *tree, int space)
{
if(tree != NULL) {
for(int i=0;i<space;i++) printf(" ");
printf("%d\n", tree->key);
if(tree->sons != NULL) {
int length = tree->length_sons;
for(int i=0;i<length;i++) {
print_tree(tree->sons[i], (space+1));
}
}
}
}
void find_deep(node *tree, int current_deep)
{
if(tree != NULL) {
if(current_deep > big_deep) big_deep = current_deep;
if(tree->sons != NULL) {
int length = tree->length_sons;
for(int i=0;i<length;i++) {
find_deep(tree->sons[i], (current_deep+1));
}
}
}
}
void print_menu()
{
printf("_^_^_^_^_^_^_\n");
printf("Menu:\n1. Add node;\n2. Print tree;\n3. Delete node;\n4. Deep tree.\nChoose one action: \n");
}
int main(void) {
node* tree = NULL;
int inp, key, key_start, father;
print_menu();
while(scanf("%d", &inp)!=EOF) {
switch(inp) {
case 1:
printf("Input node: ");
scanf("%d", &key);
if(tree == NULL) {
key_start = key;
create_tree(&tree, key);
}
else {
printf("\nInput father: ");
scanf("%d", &father);
add_node(&tree, key, father);
}
break;
case 2:
if(tree == NULL) printf("\nTree is empty.\n");
else {
printf("_\n");
print_tree(tree, 0);
printf("_\n");
}
break;
case 3:
if(tree == NULL) printf("\nNo tree, no delete.\n");
else {
printf("Input node: ");
scanf("%d", &key);
delete_node(&tree, key);
if(key == key_start) tree = NULL;
}
break;
case 4:
if(tree == NULL) printf("\nNo tree, no deep.\n");
else {
big_deep = 0;
find_deep(tree, big_deep);
printf("Tree deep is %d\n", big_deep);
}
break;
}
print_menu();
}
return 0;
}