收集 BST 的所有叶子并列出它们

Question

我有一个简单的 BST，定义了节点结构:

struct node
{
  int key_value;
  struct node *left;
  struct node *right;
};

typedef struct node * tree;

现在我应该创建一个“叶子”函数，它将收集所有叶子的值并制作它们的列表，其中列表是定义如下的结构

typedef struct l_node * pnode;

typedef struct
{
  int val;
  pnode next; 
} l_node;

问题是我不知道如何将适当的指针传递给函数 leaves。我不知道它应该是指向 pnode 的指针还是简单的 pnode。到目前为止我所做的是:

pnode leaves(tree tr)
{
   // create a pointer to empty list 
   // and pass it to another function maybe?
}

// this is an extra function to go through all leaves
void leaves_rec(tree tr, pnode * node) // pnode or pnode *?
{
  if(tr == NULL)
    return;
  if(tr->left == NULL && tr->right == NULL)
    {
       // ???
    }
  else
    {
      if(tr->left != NULL)
    leaves_rec(tr->left, node);
      if(tr->right != NULL)
    leaves_rec(tr->right, node);
    }
}

Answer 1

我希望这个问题与学习和理解树和列表的工作原理有关。对于真正的应用程序，您应该考虑使用提供这一切的 std 库。

有一个给定的树节点结构。我宁愿将其命名为 leaf，并向其中添加一些数据。通常您使用树来管理某种数据。我还添加了一个指向父元素的指针 - 如果您计划以某种方式平衡树，您将需要它。该树由一个根叶定义。

struct leaf {
  int key_value;
  leaf * top;
  leaf * left;
  leaf * right;
  void * data;
};

这是列表节点

struct {
  node * next; 
  void * data;
} node;

现在需要一个方法从给定的树创建一个列表。

node * leaves(leaf * tree) {
    node * list = new node();
    list->next = NULL;
    list->data = NULL;

    if (tree != NULL)
        leaf2node(tree, list);
    return list;
}

node * leaf2node(leaf * l, node * n) {
    // go left first
    if (l->left != NULL)
        n = leaf2node(l->left, n); // list node n is updated

    // omit this if statement, to collect the whole tree
    if (l->left == NULL && l->right == NULL) {
        // create a new list node and copy the data pointer
        node * add = new node();
        add->data = l->data;
        add->next = NULL;

        // append the list node and make the new node current
        n->next = add;
        n = add;
    }

    // go right
    if (l->right != NULL)
        n = leaf2node(l->right, n);  // list node n is updated

    return n;
}

通过改变左/右的位置，列表的顺序就会改变。