在BST节点的所有的父母呢？ [英] All parents of a node in BST?
问题描述
在使用递归函数（pre级）打印二叉搜索树（BST）。我需要打印当前节点的所有家长（路径表根）。
辅助数据结构（如路径的在我的code）可使用，但我不希望保留的于节点>路径的存储路径。
4 / \ / \ 2 6 / \ / \ 1 3 5 7
假如我打印使用pre-序遍历行节点：
节点路径
4 4
2 4,2
1 4,2,1
3 4,2,3
6 4,6
5 4,6,5
7 4,6,7
我做了如下：做工精细
路径的结束，在此code 0（零）值。而且也没有节点值是0的BST。
无效printpath（INT * mypath中）{
而（* mypath中）
的printf（％D，* mypath中++）;
}
虚空preorder（结构树* P，为int *路径）{
为int * = mypath中释放calloc（的sizeof（路径）/的sizeof（int）的+ 1，sizeof的（为int *））;
INT * MYP = mypath中;
如果（P！= NULL）{
而（* MYP ++ = *路径++）;
--myp;
* MYP = P-＆GT;的数据;
*（MYP + 1）= 0;
的printf（％D PATH，对＆GT;数据）;
printpath（mypath中）;
的printf（\ N）;
preorder（对GT;左，mypath中）;
preorder（对GT;右，mypath中）;
}
免费（mypath中）;
}
但我不希望保留的路径阵列作为有大量的BST节点。可有一个人给我建议的其他数据结构/或方法？有人建议就足够，但应该是有效的。
下面是一个老把戏，这仍然有效：保持背部指针调用堆栈
结构stacked_list {
结构stacked_list * preV;
结构树*树;
};
无效printpath_helper（int数据，结构stacked_list *路径）{
如果（path-＆GT;！preV）
的printf（％D PATH，数据）;
其他
printpath_helper（数据，path-＆GT; preV）;
的printf（％D，path-＆GT;树形＆GT;数据）;
}
无效printpath（结构stacked_list *路径）{
printpath_helper（path-＆GT;树形＆GT;数据路径）;
的putchar（'\ N'）;
}
虚空preorder_helper（结构stacked_list *路径）{
如果（path-＆GT;树）{
printpath（路径）;
结构stacked_list孩子= {路径，path-＆GT;树形＆GT;左};
preorder_helper（安培;童）;
child.tree = path-＆GT;树形＆GT;权利;
preorder_helper（安培;童）;
}
}
虚空preorder（结构树*树）{
结构stacked_list根= {NULL，树};
preorder_helper（安培;根）;
}
中的每个递归 preorder_helper 创建一个说法结构并将其地址到下一个递归，有效地创建参数链表其中 printpath_helper 可以步行到实际打印的路径。既然要从上到下打印路径， printpath_helper 需要也扭转链表，所以你最终加倍函数的递归深度;如果你能逃脱打印底部到顶部， printpath_helper 可以是一个简单的循环（或尾递归）。
While printing Binary Search Tree(BST) using recursive function (pre-order). I need to print all the parents(path form root) of current node.
An auxiliary data structure can(e.g. path in my code) be use but I don't want to keep node->path to store path.
4 / \ / \ 2 6 / \ / \ 1 3 5 7
Suppose I am printing nodes in rows using pre-order traverse:
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
I did as follows: Working fine!
Path end with 0 (Zero) value in this code. And there is no node value is 0 in BST.
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);
}
But I don't want to keep path array as there is lots of nodes in BST. Can some one suggest me other data-structure/ or method ? A suggestion would be enough but should be efficient.
Here's an old trick, which still works: keep the back pointers in the call stack.
struct stacked_list{
struct stacked_list* prev;
struct tree* tree;
};
void printpath_helper(int data, struct stacked_list* path) {
if (!path->prev)
printf("%d PATH ", data);
else
printpath_helper(data, path->prev);
printf("%d ", path->tree->data);
}
void printpath(struct stacked_list* path) {
printpath_helper(path->tree->data, path);
putchar('\n');
}
void preorder_helper(struct stacked_list* path) {
if (path->tree) {
printpath(path);
struct stacked_list child = {path, path->tree->left};
preorder_helper(&child);
child.tree = path->tree->right;
preorder_helper(&child);
}
}
void preorder(struct tree* tree) {
struct stacked_list root = {NULL, tree};
preorder_helper(&root);
}
Each recursion of preorder_helper creates an argument struct and passes its address to the next recursion, effectively creating a linked list of arguments which printpath_helper can walk up to actually print the path. Since you want to print the path from top to bottom, printpath_helper needs to also reverse the linked list, so you end up doubling the recursion depth of the function; if you could get away with printing bottom to top, printpath_helper could be a simple loop (or tail recursion).
这篇关于在BST节点的所有的父母呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
