0

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

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

但显然它不起作用，我知道为什么在更新parent左孩子的指针后，它将它设置为last，所以下次当它访问右孩子（它的兄弟姐妹）时，它会将其设置parent为左孩子. 如何调整它以获得正确的结果？是否也可以使用堆栈迭代地执行此操作？

4

2 回答 2

3 
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);

于 2012-11-21T16:55:41.270 回答
2

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

试试这个：

def myPostOrder(root, par=None):
    if root:
        root.parent = par
        myPostOrder(root.left, root)
        myPostOrder(root.right, root)
于 2012-11-21T16:51:43.637 回答