0

left問題は、各ノードに、right、dataおよび空のポインタの 4 つのデータがあるバイナリ ツリーが与えられた場合、各ノード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 に答える