Tree

Tree

 

二叉树

和其他树不同的是，二叉树的每个节点最多只有两个孩子节点，分别为左右孩子节点。

 

 

这是一棵二叉树，树的深度为4。

一棵深度为n的二叉树，最多有2的n次方-1个节点。

二叉树的第i层最多有2的i-1次方个节点。

如果度数为2的节点数为n2，则度数为0的节点，也就是叶子节点数为n2 + 1。即n0 = n2 + 1，n0为度数为0的节点数。

 

完全二叉树

 

满二叉树

 

可以简单的通过一个数组来构造一个二叉树

typedef char btree_simple[];

构造一个二叉树

btree_simple btree = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 0, 'h', 0, 'i', 'j', 'k'};

通过这样构造二叉树除了简单之外，还有一个好处就是这种构造二叉树的方式和广度优先遍历的结果一致。

typedef struct 
{
  char *ptr;
  int size;
} btree_simple;

构造二叉树

int btree_simple_from(btree_simple *tree, int n, ...)
{
  int i;
  va_list vl;

  tree->size = n;
  
  tree->ptr = malloc(sizeof(int) * tree->size);
  if (! tree->ptr)
  {
    return -1;
  }
  va_start(vl, n);
  for (i = 0; i < n; i++)
  {
     tree->ptr[i] = (char) va_arg(vl, int);
  }
  va_end(vl);

  return 0;
}

 

销毁也很简单

void btree_simple_free(btree_simple *tree)
{
  if (tree)
  {
    free(tree->ptr);
  }
}

 

遍历二叉树

二叉树遍历策略有深度优先遍历和广度优先遍历。

 

对于二叉树来说，将二叉树看成根，左子树，右子树，这样就有先序、中序、后序3种遍历方式。

 

递归方式

char * btree_simple_itr(btree_simple *tree, int *size, void (*callback) (btree_simple *, int, char **, int *))
{
  char *result = NULL;
  if (! size)
  {
    return NULL;
  }
  
  if (tree && tree->ptr)
  {
    *size = 0;
    callback(tree, 0, &result, size);
  }
  return result;
}

 

先序

void btree_simple_iterate_callback_DLR(btree_simple *tree, int i, char **result, int *size)
{
  int li = btree_simple_left(i);
  int ri = btree_simple_right(i);

  if (i < tree->size && tree->ptr[i])
  {
    *result = realloc(*result, sizeof(int) * ++(*size));
    (*result)[(*size) - 1] = tree->ptr[i];
  }

  if (tree->ptr[li])
  {
    btree_simple_iterate_callback_DLR(tree, li, result, size);    
  }
  if (tree->ptr[ri])
  {
    btree_simple_iterate_callback_DLR(tree, ri, result, size);
  }
}

 

BTREE_SIMPLE_DLR

这是一个函数宏

#define BTREE_SIMPLE_DLR(P_TR, PZ) btree_simple_itr(P_TR, PZ, btree_simple_iterate_callback_DLR)

 

中序

void btree_simple_iterate_callback_LDR(btree_simple *tree, int i, char **result, int *size)
{
  int li = btree_simple_left(i);
  int ri = btree_simple_right(i);

  if (tree->ptr[li])
  {
    btree_simple_iterate_callback_LDR(tree, li, result, size);    
  }

  if (i < tree->size && tree->ptr[i])
  {
    *result = realloc(*result, sizeof(int) * ++(*size));
    (*result)[(*size) - 1] = tree->ptr[i];
  }

  if (tree->ptr[ri])
  {
    btree_simple_iterate_callback_LDR(tree, ri, result, size);
  }
}

BTREE_SIMPLE_LDR

这是一个函数宏

#define BTREE_SIMPLE_LDR(P_TR, PZ) btree_simple_itr(P_TR, PZ, btree_simple_iterate_callback_LDR)

 

后序

void btree_simple_iterate_callback_LRD(btree_simple *tree, int i, char **result, int *size)
{
  int li = btree_simple_left(i);
  int ri = btree_simple_right(i);

  if (tree->ptr[li])
  {
    btree_simple_iterate_callback_LRD(tree, li, result, size);    
  }
  
  if (tree->ptr[ri])
  {
    btree_simple_iterate_callback_LRD(tree, ri, result, size);
  }

  if (i < tree->size && tree->ptr[i])
  {
    *result = realloc(*result, sizeof(int) * ++(*size));
    (*result)[(*size) - 1] = tree->ptr[i];
  }
}

BTREE_SIMPLE_LRD

这是一个函数宏

#define BTREE_SIMPLE_LRD(P_TR, PZ) btree_simple_itr(P_TR, PZ, btree_simple_iterate_callback_LRD)

 

非递归方式

先序

int * btree_simple_list_pre2(btree_simple *tree, int *size)
{
  int *result = NULL;

  int *stack = NULL;
  int top = 0, stack_size = 0;

  if (! size)
  {
    return NULL;
  }
  
  if (tree && tree->ptr)
  {
    *size = 0;

    stack = realloc(stack, sizeof(int) * ++stack_size);
    stack[top] = 0;
    top++;

    while (top > 0)
    {
      while (top > 0 && stack[top - 1] < tree->size && tree->ptr[stack[top - 1]])
      {
        int li = btree_simple_left(stack[top - 1]);

        result = realloc(result, sizeof(int) * ++(*size));
        result[(*size) - 1] = tree->ptr[stack[top - 1]];

        stack = realloc(stack, sizeof(int) * ++stack_size);
        stack[top] = li;
        top++;
      }

      top--;

      if (top > 0)
      {
        int ri = btree_simple_right(stack[top - 1]);
        top--;
        
        stack = realloc(stack, sizeof(int) * ++stack_size);
        stack[top] = ri;
        top++;
      }
    }
    free(stack);
  }
  return result;
}

中序

int * btree_simple_list_mid2(btree_simple *tree, int *size)
{
  int *result = NULL;

  int *stack = NULL;
  int top = 0, stack_size = 0;

  if (! size)
  {
    return NULL;
  }
  
  if (tree && tree->ptr)
  {
    *size = 0;

    stack = realloc(stack, sizeof(int) * ++stack_size);
    stack[top] = 0;
    top++;

    while (top > 0)
    {
      while (top > 0 && stack[top - 1] < tree->size && tree->ptr[stack[top - 1]])
      {
        int li = btree_simple_left(stack[top - 1]);

        stack = realloc(stack, sizeof(int) * ++stack_size);
        stack[top] = li;
        top++;
      }

      top--;

      if (top > 0)
      {
        int ri = btree_simple_right(stack[top - 1]);

        result = realloc(result, sizeof(int) * ++(*size));
        result[(*size) - 1] = tree->ptr[stack[top - 1]];

        top--;

        stack = realloc(stack, sizeof(int) * ++stack_size);
        stack[top] = ri;
        top++;
      }
    }
    free(stack);
  }
  return result;
}

 

 

 

int main()
{
  int i;
  btree_simple btree;

  char *list;
  int size;

  btree_simple_from(&btree, 13, 'a', 'b', 'c', 'd', 'e', 'f', 'g', NULL, 'h', NULL, 'i', 'j', 'k');

  for (i = 0; i < btree.size; i++)
  {
    printf("%c%s", btree.ptr[i], i < btree.size - 1 ? " " : "\n");
  }

  
  list = BTREE_SIMPLE_DLR(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }

  list = btree_simple_list_pre2(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }


  list = BTREE_SIMPLE_LDR(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }


  list = btree_simple_list_mid2(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }

  list = BTREE_SIMPLE_LRD(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }

  btree_simple_free(&btree);

  btree_simple_from(&btree, 13, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'G', 'h', NULL, 'i', 'j', 'k');

  list = btree_simple_list_pre2(&btree, &size);
  printf("size=%d\n", size);
  if (list && size > 0)
  {
    for (i = 0; i < size; i++)
    {
      if (list[i])
      {
        printf("%c%s", list[i], i < size - 1 ? " " : "\n");
      }
    }
  }
  if (list)
  {
    free(list);
  }

  btree_simple_free(&btree);
}

 

 

 

 

另外一种方式就是通过二叉链表来构造二叉树

struct node
{
  char data;

  struct node *left, *right;
};

typedef struct  
{
  struct node *root;
} btree;

 

 

R-Tree