访问二叉树的后序为了改变其节点的内容

-1

给定一个二叉树，我应该从树叶开始访问，以便用它的值的总和替换每个节点的值两个孩子节点。我应该如何继续使用后续访问？访问二叉树的后序为了改变其节点的内容

每个节点的结构如下所示。

struct node 
{ 
    int value; 
    struct node *left; // <- pointer to the left sub-tree 
    struct node *right; // <- pointer to the right sub-tree 
};

来源

2014-04-27 enzom83

这是与该节点的后代的值的总和替换每个节点的值？ –

@DavidEisenstat：是的，目标是用每个节点的值替换该节点的子节点值：'parent_value = left_child_value + right_child_value'。 – enzom83

计算左侧子树的值（递归调用）。计算右侧子树的值（递归调用）。将两者相加并用总和替换该值。递归函数是否在赋值后返回值取决于您。 –

这样的事情？

void postorder_visit(struct node* root) { 
    int leftVal = 0; 
    int rightVal = 0; 

    if(root == NULL) 
    return; 

    postorder_visit(root->left); 
    postorder_visit(root->right); 

    //Don't want to change the leaves' values. 
    if(root->left == NULL && root->right == NULL) 
    return; 

    if(root->right != NULL) 
    rightVal = root->right->value; 
    if(root->left != NULL) 
    leftVal = root->left->value; 

    root->value = leftVal + rightVal; 

}

来源

2014-04-27 20:42:43

@ enzom83快速提问：叶子的值是否已预先初始化？ –

这是一个非常好的问题。我想你已经假设如果一个节点是叶节点，值字段被初始化。否则没有太多的选择 - 否则你可能会到处都是零。 –

在每个节点的值将是它的lChild和rChild的值的总和。

编辑编辑来处理所有的整数（必须做包括limits.h使用INT_MAX）

int postOrder(struct node* node) 
{ 
    if(node == NULL) 
    { 
     return INT_MAX; 
    } 
    int x = postOrder(node->left); 
    int y = postOrder(node->right); 
    if(x != INT_MAX) 
    { 
     node->data = x; 
    } 
    if(y != INT_MAX) 
    { 
     node->data +=y; 
    } 
    return(node->data); 
} 


//Test code 
void printinorder(struct node* node) 
{ 
    if(node == NULL) 
    { 
     return; 
    } 
    printinorder(node->left); 
    printf("%d\t",node->value); 
    printinorder(node->right); 
} 

int main() 
{ 
    struct node* root = newNode(10); 
    insert(root,5); 
    insert(root,-2); 
    insert(root,6); 
    insert(root,15); 
    insert(root,12); 
    insert(root,16); 
    printinorder(root); 
    printf("\n"); 
    postOrder(root); 
    printinorder(root); 
    printf("\n"); 
}

来源

2014-04-27 20:54:39 arunmoezhi

任何你没有做的原因：'node-> value = x + y;'？还要注意，BST与二元树不同（这是OP称之为的）。换句话说，并不能保证节点是按照任何特定的顺序，它们可能意味着完全不同的东西。 –

'node-> value = x + y;'将所有值设为'0'。基本情况返回'0'，然后它将一直传播到根。是的，你是对的。我误解为BST。将编辑我的回答 – arunmoezhi

因为你没有处理与任何其他类型节点不同的叶节点。在你的回答中，也暗示了这些值是正值。 OP没有提到这一点。但是，如果非叶节点的值为0，则可以这样做：'node-> value + =（x + y）;' –

访问二叉树的后序为了改变其节点的内容

回答

相关问题