更改二叉树中每个节点的信息部分

Question

我有一个二叉树。

  2 
    / \ 
     3  4 
    /\  \ 
    5 1  8 
    \  /
    6  9 

我想改变每个节点的信息的一部分，使得

nodeinfo = nodeinfo + nextInorderNodeInfo 

所以实际序遍历

5, 6, 3, 1, 2, 4, 9, 8 

将变更为

5+6,6+3,3+1,1+2,2+4,4+9,9+8,8+0 

11, 9, 4, 3, 6, 13, 17, 8 

我需要写一个wi的函数将修改每个节点的二叉树信息部分。

我已经以这种方式我不能够修改是右手叶节点的节点做了以下

调用

change(root,NULL); 

函数定义

void change(node* n, node *k) 
{ 
if (n) 
    { 
    if (n->left) change(n->left,n); 
    if (n->right) change(n,n->right); 
    n->info + = k->info; 
    } 
} 

。

有人可以给出正确的解决方案。

在此先感谢

Answer 1

写反向中序遍历函数（如right, this, left而非left, this, right）（这在技术上仍处于有序，只是不同的定义，但是这是除了点） 。

所以这个功能将在这个顺序处理节点：

8, 9, 4, 2, 1, 3, 6, 5 

这个功能一定还记得上次处理节点的值（你添加到它之前），只需将此值添加到当前节点。

这里甚至一些代码，应该工作：

int last = 0; 
void change(node* n) 
{ 
    if (n) 
    { 
    change(n->right); 
    int tempLast = n->info; 
    n->info += last; 
    last = tempLast; 
    change(n->left); 
    } 
}