BST中节点的所有父节点？

一尘不染

BST中节点的所有父节点？

algorithm

使用递归功能（预购）打印二进制搜索树（BST）时。我需要打印当前节点的所有父级（路径形式为root）。
可以使用辅助数据结构（例如，代码中的路径），但是我不想保留 _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中有很多节点。有人可以建议我其他数据结构/方法吗？一个建议就足够了，但应该是有效的。

阅读 238

2020-07-28

共1个答案

一尘不染

这是一个老技巧，仍然有效： 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可能是一个简单的循环（或尾部递归）。

2020-07-28