3

再帰関数（事前注文）を使用して二分探索木（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にはノードがたくさんあるので、パス配列を保持したくありません。誰かが私に他のデータ構造/または方法を提案できますか？提案で十分ですが、効率的である必要があります。

4

2 に答える 2

6

これが古いトリックですが、それでも機能します。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、引数構造体を作成し、そのアドレスを次の再帰に渡します。これprintpath_helperにより、実際にパスを出力するためにウォークアップできる引数のリンクリストが効果的に作成されます。パスを上から下にprintpath_helper出力するため、リンクリストも逆にする必要があります。そのため、関数の再帰の深さが2倍になります。下から上への印刷を回避printpath_helperできる場合は、単純なループ（または末尾再帰）である可能性があります。

于 2012-10-17T15:59:15.077 に答える
1

新しい配列を作成する代わりに、単一の配列を使用して現在のノードの親を保持し、再帰を実行するときにそれを渡すことができます。1つの再帰が終了したときに配列を再開することを忘れないでください。そうすればたくさんの思い出を保存できると思います。コードは以下のとおりです。

#include<iostream>
#include<vector>
#include<algorithm>

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<int>& parents)
{
     if(root!=NULL)
     {
              cout<<root->data<<"\t";
              for(size_t i=0;i<parents.size();++i)cout<<parents[i]<<",";
              cout<<root->data<<endl;

              parents.push_back(root->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<int> parents;

    cout<<"NODE\tPATH"<<endl;
    print_preorder_path(root,parents);

    getchar();
    return 0;
}

コードは簡単にするためにstlで書かれています。必要に応じて変更できます。お役に立てば幸いです！

于 2012-10-18T06:11:39.317 に答える