Добавление дополнительных элементов в двоичное дерево без изменения высоты дерева

Question

У меня проблема с пониманием, поэтому я попрошу здесь, у меня есть только хорошие ответы.

Задача: Необходимо написать новую функцию, которая (и вычисляет) показывает, сколько элементов можно ввести в дерево, не увеличивая его высоту. Функция выводит только и явно численное значение ex. 17/н.

Может ли кто-нибудь уточнить?

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 

#define MAX_TREE_STRING 100 
#define MAX_NODES 100 

// width and height of 2D array used for function print_tree 
#define WIDTH 80 
#define HEIGHT 10 

typedef struct node { 
    int key; 
    struct node *left; 
    struct node *right; 
}Node; 

int print_tree(Node *tree, int is_left, int offset, int depth, char s[HEIGHT][WIDTH]) { 
    char b[HEIGHT]; 
    int i, left, right, width = 3; 

    if (!tree) return 0; 
    sprintf(b,"(%c)",tree->key); 
    left = print_tree(tree->left,1,offset,depth+1,s); 
    right = print_tree(tree->right,0,offset+left+width,depth+1,s); 
    for (i=0; i<width; i++) 
     s[depth][offset+left+i] = b[i]; 
    if (depth) { 
     if (is_left) { 
      for (i=0; i<width+right; i++) 
       s[depth-1][offset+left+width/2+i] = '-'; 
     } else { 
      for (i=0; i<left+width; i++) 
       s[depth-1][offset-width/2+i] = '-'; 
     } 
     s[depth-1][offset+left+width/2] = '.'; 
    } 
    return left+width+right; 
} 

Node *create_tree(char *tree_string) { 
    Node *queue[MAX_NODES]; 
    Node *trenutni, *parent; 
    int tail, head, i; 

    tail = head = -1; 
    trenutni = parent = NULL; 

    for(i=0; i<strlen(tree_string); i++) { 
     if (tree_string[i]!=';') { 
      if (tree_string[i]=='-') continue; 
      trenutni = (Node *)malloc(sizeof(Node)); 
      trenutni->key = tree_string[i]; 
      trenutni->left = trenutni->right = NULL; 

      queue[++tail] = trenutni; 
      if (parent && tree_string[i-1]==';') { 
       parent->left = trenutni; 
      } else if (i>0) { 
       parent->right = trenutni; 
      } 
     } else { 
      parent = queue[++head]; 
     } 
    } 
    return queue[0]; 
} 

/* 
void function_name(arguments) { 
} 
*/ 

int main() { 
    Node *root=NULL; 
    int i, menu_choice; 
    char c, tree_string[MAX_TREE_STRING]; 
    char print_format[6], empty_line[WIDTH], s[HEIGHT][WIDTH]; 

    setbuf(stdout, NULL); 
    do { 
     menu_choice = 0; 
     //printf("\n1 Description of a function (function_name)"); 
     printf("\n2 Create tree \n3 Print \n4 Exit\n"); 
     scanf("%d", &menu_choice); 
     switch (menu_choice) { 
      case 1: 
       //function_name(arguments); 
       break; 
      case 2: 
       printf("Create a tree as queue of alphanumeric entries separated with ;\n"); 
       scanf(" %s", tree_string); 
       root = create_tree(tree_string); 
       break; 
      case 3: 
       sprintf(print_format, "%%%ds", WIDTH-1); 
       for (i=0; i<HEIGHT; i++) 
        sprintf(s[i], print_format, " "); 

       print_tree(root,0,0,0,s); 

       sprintf(empty_line, print_format, " "); 
       for (i=0; i<HEIGHT; i++) { 
        if (strcmp(s[i],empty_line)) 
         printf("%s\n", s[i]); 
       } 
       break; 
      case 4: 
       break; 
      default: 
       while((c = getchar()) != '\n' && c != EOF); 
     } 
    } while(menu_choice!=4); 
    return 0; 
} 

Разъяснения: после того, как вы вставили элементы в дерево, вы должны найти, который является самой большой высотой дерева и сколько элементов вы можете вставить в другие узлы дерева, на высоту самого большой и не пересекая его.

Answer 1

Полное двоичное дерево содержит 2^h -1 Узлы. Таким образом, вы можете вставить 2^h-1 - n больше узлов без изменения высоты дерева. (где n - текущее количество узлов в дереве).