BST节点的所有父母？
在使用递归函数（预订）打印二进制搜索树（BST）时。 我需要打印当前节点的所有父节点（路径根目录）。
可以使用辅助数据结构（例如，我的代码中的路径 ），但我不想保留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中有很多节点。 有人可以建议我其他数据结构/方法吗？ 一个建议就够了，但应该是有效的。
这是一个老技巧，它仍然有效： 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); }
preorder_helper每次递归都会创建一个参数struct并将其地址传递给下一个递归，从而有效地创建一个参数的链接列表， printpath_helper可以走向实际打印路径。 由于要从上到下打印路径， printpath_helper还需要反转链表，因此最终会使函数的递归深度加倍; 如果你可以从底部到顶部打印， printpath_helper可能是一个简单的循环（或尾递归）。
您可以使用单个数组来保留当前节点的父节点，并在执行递归时将其传递下来，而不是创建新数组，只需记住在一次递归完成后恢复数组。 我想通过这种方式你可以节省很多回忆。 代码如下：
#include #include #include using namespace std; struct node { int data; struct node *left, *right; }; // A utility function to create a node struct node* newNode( int data ) { struct node* temp = (struct node *) malloc( sizeof(struct node) ); temp->data = data; temp->left = temp->right = NULL; return temp; } void print_preorder_path(struct node *root,vector& parents) { if(root!=NULL) { cout<data<<"\t"; for(size_t i=0;idata<data); print_preorder_path(root->left,parents); print_preorder_path(root->right,parents); parents.pop_back(); } } int main() { // Let us construct the tree given in the above diagram struct node *root = newNode(4); root->left = newNode(2); root->left->left = newNode(1); root->left->right = newNode(3); root->right = newNode(6); root->right->left = newNode(5); root->right->right = newNode(7); vector parents; cout<<"NODE\tPATH"<
为简单起见，代码用stl编写，您可以根据需要进行修改，希望它有所帮助！