更新二进制文件中的父指针

Question

问题是，给定一个二叉树，其中每个节点有四个数据：left，right，data和一个空指针{}，我们必须更新树，使每个节点的parent指针指向其父节点（根父指针自然指向空值）。现在我该怎么做？我尝试过这样的后序遍历：

last = None
def mypostorder(root):
    if root:
      mypostorder(root.left)
      mypostorder(root.right)
      if last:
        last.parent = root
      last = root

但显然它不起作用，我知道为什么在更新左子元素的parent指针后，它将其设置为last，所以下次当它访问右子对象（它的兄弟姐妹）时，它会将它的parent设置为左子对象。如何调整它以获得正确的结果？有没有可能用堆栈迭代的方式来实现呢？在

Answer 1

void setParent(node * ptr,node * parent_ptr)
{

if(ptr==NULL)
return;

ptr->parent=parent_ptr; //update the parent for the current node

parent_ptr=ptr; //now update the parent pointer

setParent(ptr->left,parent_ptr); //repeat the process for children

setParent(ptr->right,parent_ptr);
}

初始调用：setParent(root,NULL);

Answer 2

你走错了路。我认为你的解决方案会使一个节点的父节点指向它的子节点

试试看：

def myPostOrder(root, par=None):
    if root:
        root.parent = par
        myPostOrder(root.left, root)
        myPostOrder(root.right, root)