tree_sum.c

树的算法

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

const int  INVALID = -999999;

struct Node{
  struct Node* l;
  struct Node* r;
  struct Node* p;
  int   data;
};

int sum_of_tree(struct Node* n)
{
  int   sum =0;
  struct Node* n1=n;

  if (n->r==0)
  {
    n->r = malloc(sizeof(struct Node));
    n->p = n;
    n->l=0;
    n->r=0;
    n->data=0;
  }
  while(!(n1->p == n && n->r==n1 && 
        ( (n1->l==0||n1->l->data==INVALID ) && (n1->r==0 || n1->r->data==INVALID))))
  {
    while(n1->data!= INVALID &&(n1->l!=0 || n1->r!=0 ))
    {
      if (n1->r!=0 )
      {
        if(n1->r->data == INVALID) 
        {
          break;
        }
      }
      else if (n1->l!=0 && n1->l->data==INVALID)
      {
        break;
      }
      
      while (n1->l!=0) 
      {
        n1=n1->l;
      }

      if (n1->r!=0)
      {
        n1=n1->r;
      }

    }
    sum+= n1->data;
    n1->data=INVALID;
    if (n1->p!=0)
      if (n1->p->r !=0 && n1->p->r!=n1)
        n1=n1->p->r;
      else
        n1=n1->p;
    else
      return sum;
  }
  if (n1->p==n && n->r==n1)
  {
    sum += n1->data;
    sum += n->data;
  }

  return sum;
}

int sum_of_tree_r(struct Node* n)
{
  if (n==0)
    return 0;
  return n->data+sum_of_tree_r(n->l)+sum_of_tree_r(n->r);
}

int main()
{
  struct Node* n=malloc(sizeof( struct Node));
  n->data = 18;
  n->p = 0;
  n->l=malloc(sizeof( struct Node));
  n->l->data= 22;
  n->l->p = n;
  n->r=malloc(sizeof( struct Node));
  n->r->data=48;
  n->r->p = n;
  n->r->l = malloc(sizeof( struct Node));
  n->r->r=malloc(sizeof( struct Node));
  n->r->l->data  = 89;
  n->r->l->p = n->r;
  n->r->r->data = 77;
  n->r->r->p = n->r;
  n->l->l = malloc(sizeof( struct Node));
  n->l->l->data = 23;
  n->l->l->p  = n->l;
  n->l->l->r = malloc(sizeof(struct Node));
  n->l->l->r->data = 76;
  n->l->l->r->p = n->l->l;
  n->l->l->r->r = malloc( sizeof(struct Node));
  n->l->l->r->r->data = 224;
  n->l->l->r->r->p = n->l->l->r;
  n->l->l->r->r->l  = malloc(sizeof( struct Node));
  n->l->l->r->r->l->data = 78;
  n->l->l->r->r->l->p = n->l->l->r->r;
  

  printf("%d\n", sum_of_tree_r(n));
  printf("%d\n", sum_of_tree(n));

}