Двоичное кодирование дерево


Я реализовал решение этой кодирование вызов на код Гольф. У меня есть приличный опыт работы с C/C++, но это было время, так как я ими активно пользовался.

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

// Prototypes
struct BTnode;
struct BTnode * bt_add_left(struct BTnode * node, int data);
struct BTnode * bt_add_right(struct BTnode * node, int data);
int             bt_depth(struct BTnode * tree);
int             bt_encode_preorder(int * list, struct BTnode * tree, int index);
struct BTnode * bt_node_create(int data);
int             bt_node_delete(struct BTnode * node);
void            bt_print_preorder(struct BTnode * tree);
int *           encode(struct BTnode * tree);
struct BTnode * decode(int * list);

// Binary tree node
struct BTnode
{
  int data;
  struct BTnode *left, *right;
};

// Add node to this node's left
struct BTnode * bt_add_left(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->left = newnode;
  return newnode;
}

// Add node to this node's right
struct BTnode * bt_add_right(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->right = newnode;
  return newnode;
}

// Determine depth of the tree
int bt_depth(struct BTnode * tree)
{
  int depth;
  int leftdepth = 0;
  int  rightdepth = 0;
  if( tree == NULL ) return 0;

  if( tree->left != NULL )
    leftdepth = bt_depth(tree->left);
  if( tree->right != NULL )
    rightdepth = bt_depth(tree->right);

  depth = leftdepth;
  if(rightdepth > leftdepth)
    depth = rightdepth;

  return depth + 1;
}

// Recursively add node values to integer list, using 0 as an unfolding sentinel
int bt_encode_preorder(int * list, struct BTnode * tree, int index)
{
  list[ index++ ] = tree->data;

  // This assumes the tree is complete (i.e., if the current node does not have
  // a left child, then it does not have a right child either)
  if( tree->left != NULL )
  {
    index = bt_encode_preorder(list, tree->left, index);
    index = bt_encode_preorder(list, tree->right, index);
  }

  // Add sentinel
  list[ index++ ] = 0;
  return index;
}

// Allocate memory for a node
struct BTnode * bt_node_create(int data)
{
  struct BTnode * newnode = (struct BTnode *) malloc(sizeof(struct BTnode));
  newnode->left = NULL;
  newnode->right = NULL;
  newnode->data = data;
  return newnode;
}

// Free node memory
int bt_node_delete(struct BTnode * node)
{
  int data;
  if(node == NULL)
    return 0;
  data = node->data;

  if(node->left != NULL)
    bt_node_delete(node->left);
  if(node->right != NULL)
    bt_node_delete(node->right);

  free(node);
  return data;
}

// Print all values from the tree in pre-order
void bt_print_preorder(struct BTnode * tree)
{
  printf("%d ", tree->data);
  if(tree->left != NULL)
    bt_print_preorder(tree->left);
  if(tree->right != NULL)
    bt_print_preorder(tree->right);
}

// Decode binary tree structure from a list of integers
struct BTnode * decode(int * list)
{
  struct BTnode * tree;
  struct BTnode * nodestack[ list[0] ];
  int i,j;

  // Handle trivial case
  if( list == NULL ) return NULL;

  tree = bt_node_create( list[1] );
  nodestack[ 1 ] = tree;

  j = 1;
  for(i = 2; i < list[0]; i++)
  {
    if( list[i] == 0 )
    {
      //printf("popping\n");
      j--;
    }
    else
    {
      if( nodestack[j]->left == NULL )
      {
        //printf("Adding %d to left of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_left(nodestack[j], list[i]);
        j++;
      }
      else
      {
        //printf("Adding %d to right of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_right(nodestack[j], list[i]);
        j++;
      }
    }
  }

  return tree;
}

// Encode binary tree structure as a list of integers
int * encode(struct BTnode * tree)
{
  int maxnodes, depth, length;
  int * list;
  int j;

  // Handle trivial case
  if(tree == NULL) return NULL;

  // Calculate maximum number of nodes in the tree from the tree depth
  maxnodes = 1;
  depth = bt_depth(tree);
  for(j = 0; j < depth; j++)
  {
    maxnodes += pow(2, j);
  }

  // Allocate memory for the list; we need two ints for each value plus the
  // first value in the list to indicate length
  list = (int *) malloc( ((maxnodes * 2)+1) * sizeof(int));
  length = bt_encode_preorder(list, tree, 1);
  list[ 0 ] = length;
  return list;
}

int main()
{
  struct BTnode * tree;
  struct BTnode * newtree;
  int * list;
  int i;

  /* Provided example

        5
       / \
      3   2
         / \
        2   1
       / \
      9   9
  */
  tree = bt_node_create(5);
  bt_add_left(tree, 3);
  struct BTnode * temp = bt_add_right(tree, 2);
  bt_add_right(temp, 1);
  temp = bt_add_left(temp, 2);
  bt_add_left(temp, 9);
  bt_add_right(temp, 9);
  printf("T (traversed in pre-order):  ");
  bt_print_preorder(tree);
  printf("\n");

  list = encode(tree);
  printf("T (encoded as integer list): ");
  for(i = 1; i < list[0]; i++)
    printf("%d ", list[i]);
  printf("\n");

  newtree = decode(list);
  printf("T' (decoded from int list):  ");
  bt_print_preorder(newtree);
  printf("\n\n");


  // Free memory
  bt_node_delete(tree);
  bt_node_delete(newtree);
  free(list);
  return 0;
}

Как моя программа может быть улучшена? Я думаю, в основном с точки зрения ясности/читаемость, ремонтопригодность и повторное использование, но я также приветствую любые комментарии по поводу моей реализации структур данных и возможных улучшений в плане производительности и правильности.



2338
12
задан 2 февраля 2011 в 09:02 Источник Поделиться
Комментарии
5 ответов

В инт bt_depth(BTnode структура * дерево)

Слишком много различных проверок на null.
Вам нужно только проверить. Вызов bt_depth() на левый и правый узлы будут выполнять там свои явные проверки не попробовать и заранее оптимизировать.

int bt_depth(struct BTnode * tree)
{
if( tree == NULL ) return 0;
int leftdepth = bt_depth(tree->left);
int rightdepth = bt_depth(tree->right);

return max(leftdepth, rightdepth) + 1;
}

В bt_encode_preorder инт(инт * список, BTnode структура * дерево, тип int индекс)

Вы используете дерево без проверки на null дерево

list[ index++ ] = tree->data;

Вы также делаете рекурсивный вызов без проверки.
В какой-то момент Вы можете в конечном итоге попав в нуль и пытается де-ссылаться на него.

if( tree->left != NULL )
{
index = bt_encode_preorder(list, tree->left, index);
index = bt_encode_preorder(list, tree->right, index); // tree->right may be NULL!!!!
}

В инт bt_node_delete(BTnode структура * узел)

Это примечание узел удалить это удалить дерево.
Она должна быть названа соответствующим образом.

В пустоту bt_print_preorder(BTnode структура * дерево)

Это легче всего проверить, если текущий узел является null.
Всегда печатать левые и правые узлы.

void bt_print_preorder(struct BTnode * tree)
{
if (tree == NULL) return;

printf("%d ", tree->data);
bt_print_preorder(tree->left);
bt_print_preorder(tree->right);
}

В кодирование(BTnode структура * дерево)

  // Calculate maximum number of nodes in the tree from the tree depth
maxnodes = 1;
depth = bt_depth(tree);
for(j = 0; j < depth; j++)
{
maxnodes += pow(2, j);
}

Это единственное применение bt_depth(). Вместо этого почему бы просто не есть функция под названием bt_count_nodes(BTnode* дерево), что фактического количества узлов (bt_depth на самом деле обходит все узлы так или иначе (почему бы не считать их, а не глубина).

В BTnode структура * декодирование(инт * список)

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

17
ответ дан 2 февраля 2011 в 09:02 Источник Поделиться

У меня есть только минута, прежде чем запускать из двери, так вот первое, что я увидел:


  • Его хорошая практика, чтобы установить указатели на нуль после того, как вы освободите их. Просто как вы проверяете, чтобы обеспечить его не установить в нуль, так как вы делаете, что после создания, вы должны сделать, что при удалении.

6
ответ дан 2 февраля 2011 в 09:02 Источник Поделиться

Я рекомендую Три улучшения, одна крупная и две мелкие.

Малой один из первых: не коврик с пробелами, чтобы горизонтально выровнять маркеры. Там нет ничего плохого с делать это, он будет просто в конечном итоге принимая время, чтобы сохранить все выравнивается, или вы в конечном итоге не беспокоит (потому что ваш возможно, в спешке), а не выравнивание.

Во-вторых, определение типа структуры:

typedef struct BTnode_def
{
int data;
struct BTnode_def *left, *right;
} BTnode;

так что вы можете просто использовать BTnode вместо структуры BTnode.

Самый главный: не использовать прототипы, когда вы можете использовать саму функцию/структуру в качестве прототипа. Вы можете избавиться от всей секции прототип в коде. Вам необходимо двигаться bt_node_create немного хотя. Это позволит уменьшить время обслуживания - при изменении параметров функции / возвращаемое значение, вы только должны сделать это один раз.

Ой, а я только заметил, что, как представляется, существует несколько функций C++ в коде, так что это не чистый C код.

Обновление

Я удалил префикс подчеркивания (я на самом деле не сделать это нормально). Я не уверен насчет комментария отметить, что пространство имен в C не имеют имен.

Как для C++ функции (я не в курсе со спецификацией C, поэтому некоторые из них могут быть в последней спецификации):


  • Один коммент строки в C++

  • Деклараций в любой точке в коде на C++, C требует, чтобы заявления были в начале блока, т. е. после {.

ЕЩЕ ОДНО ОБНОВЛЕНИЕ

Это личные предпочтения, но я хотел бы поставить точку * рядом с символом без пробела:

// Instead of this
BTNode * bt_node_create (...);
// I like
BTNode *bt_node_create (...);

которая, для меня, делает это быстрее, чтобы различать умножение и указатель разыменовывает:

a * func ();  // an expression: a times return value of func
a *func (); // a declaration: func returns a pointer to type a

Я знаю, что в контексте выше отличия между двумя, но это требует дополнительного анализа мой мозг прилегающей код, и тем меньше мой мозг должен это сделать, тем лучше (это старый мозг, ведь и не так хорошо, как те, что эти молодые люди здесь есть ;-) ).

4
ответ дан 3 февраля 2011 в 12:02 Источник Поделиться

Хотя не не часто, особенно не в игрушечных программ, это все еще хорошая идея, чтобы проверить, что функции malloc()realloc() и метода calloc() , когда вы используете их) не возвращается нулевой указатель. И, когда вы использовать realloc(), вы не присваивает результат переменной, переданной в качестве первого аргумента. То есть вообще не использовать:

ptr = realloc(ptr, newsize);

Использование:

newptr = realloc(oldptr, newsize);

Альтернатива, которая зачастую достаточным является использование крышка функция (emalloc() и xmalloc() используются для целей), что гарантирует не вернет нулевой указатель.

void *emalloc(size_t nbytes)
{
void *ptr = malloc(nbytes);
if (ptr == 0)
abort();
return(ptr);
}

Вы можете использовать более изящные механизмы, чем прервать() сообщить об ошибке.
Использовать симметричные крышка функции realloc(), памятью() и свободный().

4
ответ дан 3 февраля 2011 в 05:02 Источник Поделиться

Пару вещей в дополнение к предложения уже сделаны:


  • Как @Мартин сказал, bt_node_delete удаляет ветвь дерева. Я думаю, что хороший термин для этого может быть "чернослив".


    1. список = (инт *) Танос( ((maxnodes * 2)+1) * оператор sizeof(тип int));

    2. список = (инт *) Танос( ((maxnodes * 2) + 1) * оператор sizeof(тип int) );

    3. список = (инт *) Танос(((maxnodes * 2) + 1) * оператор sizeof(тип int));
      Я предпочитаю #3, но № 2 больше соответствует интервал в стиль, который вы дали.


  • Место операторам указатель с символом она изменяет:

    1. BTnode структура * декодирование(инт * список)

    2. BTnode *декодирование(инт *список)


Лично мне не нравится конвенции ставить пробелы внутри скобок и квадратных скобок ( заявление ). Я думаю, что это лишнее пустое пространство, которое труднее поддерживать, если вам нужно изменить заявление.

2
ответ дан 3 февраля 2011 в 12:02 Источник Поделиться