的realloc在树上递归

我试图找到最大的总和叶如下 http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/的realloc在树上递归

1）我无法找到根二叉树路径为何路径没有得到印在main（）这是因为函数中有错误的realloc。

2）也是我的自由正确？

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

/* A tree node structure */ 
struct node 
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}; 

// Returns the maximum sum and prints the nodes on max sum path 
int maxsumtoleaf(struct node *node,int** path,int &height) 
{ 
    // base case 
    if (node == NULL) 
     return 0; 
    printf("\n At node %d,",node->data); 
    if (node->left==NULL && node->left==NULL) { 
     *path=(int*)realloc(*path,sizeof(int)); 
     *path[0]=node->data; 
     height=1; 
     printf("\n value is %d,",*path[0]); 
     return node->data; 
    } 
    // find the target leaf and maximum sum 
    int rightheight=0,leftheight=0; 
    int *path1=NULL,*path2=NULL; 
    int left=maxsumtoleaf (node->left,&path1,leftheight); 
    int right=maxsumtoleaf (node->right,&path2,rightheight); 
    if (left > right) { 
     printf("\nbefore left is"); 
     for(int i=0;i<leftheight;i++) 
      printf("%d,",path1[i]); 
     path1=(int*)realloc(path1,sizeof(int)*(leftheight+1)); 
     if (path1 == NULL) { 
      printf("Out of Memory!\n"); 
      return 0; 
     } 
     path1[leftheight]=node->data; 
     height=leftheight+1; 
     printf("\nafter left %d is ",leftheight); 
     for(int i=0;i<height;i++) 
      printf("%d,",path1[i]); 
     path=&path1; 
     return left+node->data; 
    } else { 
     printf("\nbefore right is"); 
     for(int i=0;i<rightheight;i++) 
      printf("%d,",path2[i]); 
     path2=(int*)realloc(path2,sizeof(int)*(rightheight+1)); 
     if (path2 == NULL) { 
      printf("Out of Memory!\n"); 
      return 0; 
     } 
     path2[rightheight]=node->data; 
     height=rightheight+1; 
     printf("\nafter right is"); 
     for(int i=0;i<height;i++) 
      printf("%d,",path2[i]); 
     path=&path2; 
     return right+node->data; 
    } 
    // return maximum sum 
} 

/* Utility function to create a new Binary Tree node */ 
struct node* newNode (int data) 
{ 
    struct node *temp = new struct node; 
    temp->data = data; 
    temp->left = NULL; 
    temp->right = NULL; 
    return temp; 
} 

/* Driver function to test above functions */ 
int main() 
{ 
    struct node *root = NULL; 

    /* Constructing tree given in the above figure */ 
    /* (8<--2->-4)<-10->7 */ 
    root = newNode(10); 
    root->left = newNode(-2); 
    root->right = newNode(7); 
    root->left->left = newNode(8); 
    root->left->right = newNode(-4); 
    int sum=0; 

    int** path=NULL; 
    int height=0; 
    sum = maxsumtoleaf(root,path,height); 
    printf ("\nSum of the nodes is %d ,len=%d", sum,height); 
    printf ("\nPath is "); 
    for(int i=0;i<height;i++) 
     printf("%d,",*path[i]); 
    free(path); 

    getchar(); 
    return 0; 
}

输出：

At node 10, 
At node -2, 
At node 8, 
value is 8, 
At node -4, 
value is -4, 
before left is8, 
after left 1 is 8,-2, 
At node 7, 
value is 7, 
before right is7, 
after right is7,10, 
Sum of the nodes is 17 ,len=2 
Path is ---> Breaks at this point in main()

来源

2014-09-28 aravind

代码是C++与通过引用传递指定参数和使用new。

为了使C，很多小的修复，包括如何传递C“引用”变量（明确地址）。

你没有正确地做rellloc()应该分配失败，因为你失去了原来的指针。

总是以良好的形式到NULL释放它之后的指针。

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

/* A tree node structure */ 
struct node { 
    int data; 
    struct node *left; 
    struct node *right; 
}; 

// Returns the maximum sum and prints the nodes on max sum path 
int maxsumtoleaf(struct node *node, int** path, int *height) { 
    // base case 
    if (node == NULL) 
    return 0; 
    printf("\n At node %d,", node->data); 
    if (node->left == NULL && node->left == NULL) { 
    *path = (int*) realloc(*path, sizeof(int)); 
    (*path)[0] = node->data; 
    *height = 1; 
    printf("\n value is %d,", *path[0]); 
    return node->data; 
    } 
    // find the target leaf and maximum sum 
    int rightheight = 0, leftheight = 0; 
    int *path1 = NULL, *path2 = NULL; 
    int left = maxsumtoleaf(node->left, &path1, &leftheight); 
    int right = maxsumtoleaf(node->right, &path2, &rightheight); 
    if (left > right) { 
    printf("\nbefore left is"); 
    for (int i = 0; i < leftheight; i++) 
     printf("%d,", path1[i]); 
    path1 = (int*) realloc(path1, sizeof(int) * (leftheight + 1)); 
    if (path1 == NULL) { 
     printf("Out of Memory!\n"); 
     return 0; 
    } 
    path1[leftheight] = node->data; 
    *height = leftheight + 1; 
    printf("\nafter left %d is ", leftheight); 
    for (int i = 0; i < *height; i++) 
     printf("%d,", path1[i]); 
    *path = path1; 
    return left + node->data; 
    } else { 
    printf("\nbefore right is"); 
    for (int i = 0; i < rightheight; i++) 
     printf("%d,", path2[i]); 
    path2 = (int*) realloc(path2, sizeof(int) * (rightheight + 1)); 
    if (path2 == NULL) { 
     printf("Out of Memory!\n"); 
     return 0; 
    } 
    path2[rightheight] = node->data; 
    *height = rightheight + 1; 
    printf("\nafter right is"); 
    for (int i = 0; i < *height; i++) 
     printf("%d,", path2[i]); 
    *path = path2; 
    return right + node->data; 
    } 
    // return maximum sum 
} 

/* Utility function to create a new Binary Tree node */ 
struct node* newNode(int data) { 
    struct node *temp = malloc(sizeof *temp); // new struct node; 
    temp->data = data; 
    temp->left = NULL; 
    temp->right = NULL; 
    return temp; 
} 

/* Driver function to test above functions */ 
int main() { 
    struct node *root = NULL; 

    /* Constructing tree given in the above figure */ 
    /* (8<--2->-4)<-10->7 */ 
    root = newNode(10); 
    root->left = newNode(-2); 
    root->right = newNode(7); 
    root->left->left = newNode(8); 
    root->left->right = newNode(-4); 
    int sum = 0; 

    int* path = NULL; 
    int height = 0; 
    sum = maxsumtoleaf(root, &path, &height); 
    printf("\nSum of the nodes is %d ,len=%d", sum, height); 
    printf("\nPath is %p ", path); 
    // return 0; 
    for (int i = 0; i < height; i++) 
    printf("%d,", path[i]); 
    free(path); 
    path = NULL; 

    // getchar(); 
    return 0; 
}

首选realoc()使用

// Somehow these are to be updated (initial to NULL and 0) 
some_type *current_ptr; 
size_t current_element_count; // best too use type size_t 

size_t new_element_count = some_function(current_size); 
void *new_ptr = realloc(current_ptr, new_element_count * sizeof *current_ptr); 
if (new_ptr == NULL && new_element_count > 0) { 
    Handle_OOM(); // current_ptr is still same & current_element_count elements 
    return; 
} 
current_ptr = new_ptr; 
current_element_count = new_element_count; 
// continue on the happy path

来源

2014-09-28 03:07:17 chux

的realloc在树上递归

回答

相关问题