0

我有一棵二叉树。

         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

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

我做了以下

打电话

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;
  }
}

这样，我无法修改作为右手叶节点的节点。

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

提前致谢

4

1 回答 1

1

编写一个逆序遍历函数（如 inright, 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);
  }
}
于 2013-05-06T10:58:38.620 回答