在使用递归函数(前序遍历)打印二叉搜索树(BST)时,我需要打印当前节点的所有父节点(从根开始的路径)。
可以使用辅助数据结构(例如我的代码中的path),但我不想使用node->path来存储路径。
假设我正在使用先序遍历按行打印节点:4 / \ / \ 2 6 / \ / \ 1 3 5 7
NODE PATH
4 4
2 4,2
1 4,2,1
3 4,2,3
6 4,6
5 4,6,5
7 4,6,7
我按照以下步骤进行:工作正常!
在此代码中,路径以0(零)值结尾。而且在BST中没有节点值为0。
void printpath(int* mypath){
while(*mypath)
printf("%d ", *mypath++);
}
void preorder(struct tree *p, int* path){
int *mypath = calloc(sizeof(path)/sizeof(int) + 1 , sizeof(int*));
int* myp=mypath;
if(p!=NULL){
while( *myp++ = *path++ );
--myp;
*myp=p->data;
*(myp+1)=0;
printf("%d PATH ",p->data);
printpath(mypath);
printf("\n");
preorder(p->left, mypath);
preorder(p->right, mypath);
}
free(mypath);
}
但是我不想保留路径数组,因为BST中有很多节点。有人能给我建议其他的数据结构或方法吗?一个建议就足够了,但应该高效。