更新父指針

Question

的問題是，給定一個二叉樹，每個節點有數據的四件：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設置爲左邊的孩子。如何調整它以獲得正確的結果？也可以迭代地使用堆棧，可能是？

Answer 1

你有錯誤的方式。我認爲您的解決方案將使一個節點處的父及其子

試試這個：

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

Answer 2

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