c++ - 将二叉搜索树转换为链表

Question

我正在尝试将二叉搜索树转换为链表。链表应该在前面有较小的数字，在后面有较大的数字(从小到大)。我需要创建一个接受二叉搜索树并输出链表的函数。

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

这是我的二叉搜索树。我需要这样制作链表:1、2、3、4、5、6、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。我只是不明白如何将这个二叉搜索树从最小到最大转换成一个链表。我试过将 list_head_insert 函数放在递归调用之上，但输出什么也没有，列表是空的。

Answer 1

所以换句话说，你希望它在你的链接列表中以排序的形式出现。

有一种遍历方法:中序遍历。参见 here 有关遍历的更多信息。

那么如何做到这一点呢？作为提示，我会给你一个函数来按顺序“打印”这个 BST 的内容。那应该让你滚动。 (在弄清楚如何按顺序获取树的内容之后，您所要做的就是对列表调用插入函数)

void print_in_order(Node* t) {
    if(!t)
        return;
    print_in_order(t->left);
    cout << t->data;
    print_in_order(t->right);
}