创建二叉树

祖先矩阵对于给定的二进制树，我们需要创建一个矩阵[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

回答

相关问题