バイナリ検索ツリーをリンクリストに変換する

Question

バイナリ検索ツリーをリンクリストに変換しようとしています。リンクされたリストは、前面に小さい数字を、背面に大きな数字（最小から最大）を持つ必要があります。私は、バイナリ検索ツリーツリーを取り込んでリンクリストを出力する関数を作成する必要があります。

 4 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

私のバイナリ検索ツリーです。私は、リンクリストをこの方法で行う必要があります。

node<int>* makeLinkedList(binary_tree_node<int>* root_ptr); 

int main() 
{ 
    binary_tree_node<int> *s1 = sample1(); //Creates the tree 

    node<int>* node1 = makeLinkedList(s1); //invokes function to make a linked list 

    //Loop to print out the values of the linked list 
    for (node1; node1 != NULL; node1 = node1->link()){ 
     cout<<node1->data()<<endl; 
    } 
} 

node<int>* makeLinkedList(binary_tree_node<int>* root_ptr){ 
    node<int>* left; 

    if (root_ptr == NULL) { 
      return NULL; 
    } 

    else{ 

     left = makeLinkedList(root_ptr->left()); 
     list_head_insert(left, root_ptr->data()); //list_head_insert inserts a new entry at the head of the linked list 
     return left; 
    } 
} 

私は私のコードを実行すると、出力は4、2、1：1、2、3、4、5、6、7は、ここに私の現在のコードです私はこのバイナリ検索ツリーをどのようにリンクリストに変換できるのか分かりません。私は再帰呼び出しの上にlist_head_insert関数を置いてみましたが、出力は何もなく、リストは空です。

Answer 1

つまり、リンクされたリストにソートされた形式でこれが必要です。

これをトラバースする方法があります。順序通りのトラバーサル。トラバーサルの詳細については、here を参照してください。

これはどうやって行うのですか？ヒントとして、このBSTの内容を順番に「印刷」する機能を提供します。それはあなたを圧倒するはずです。 （ツリーの内容を取得する方法を理解した上で、あなたのリストに挿入機能を呼び出すだけです）