創建二叉樹

祖先矩陣對於給定的二進制樹，我們需要創建一個矩陣[7] [7] 滿足祖先屬性像[2] [1] = 1，因爲1是一個祖先2 ....創建二叉樹

我解決它通過使用額外的空間陣列...的解決方案，我想出了是

int a[n][n]={0}; 
void updatematrix(int a[][n],struct node *root,int temp[],int index){ 

if(root == NULL) 
    return ; 
int i; 

for(i=0;i< index;i++) 
    a[root->data][temp[i]]=1; 
temp[index]=root->data; 

updatematrix(a,root->left,temp,index+1); 
updatematrix(a,root->right,temp,index+1); 
}

有我的解決方案的任何錯誤？我們可以這樣做嗎？（我的意思是不使用臨時數組）

來源

2012-09-30 Sree Ram

我想在你的代碼中，你需要用'a'替換第一次出現的'arr'，並用'temp'替換第二次出現的'arr'。 – jrouquie

@jrouquie yup ..thank you ..edited .. –

temp包含從根到當前節點的路徑，

如果你在每個節點有一個父指針（但我猜不是），你可以按照這些指針走上樹遍歷與temp相同的一組節點。但是這會使用更多的內存。

你也可以走在樹數次（僞）：

def updatematrix(a,node): 
    if node is null: return 
    walkDown(a.data,node.left) 
    walkDown(a.data,node.right) 
    updatematrix(a,node.left) 
    updatematrix(a,node.right) 

def walkDown(data,node): 
    if node is null: return 
    a[node][data] = 1 
    walkDown(data,node.left) 
    walkDown(data,node.right)

相同的複雜，但內存訪問模式看少緩存友好。

來源

2012-10-01 06:49:59 jrouquie

回答

相關問題