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

Question

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

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

typedef struct node * tree;

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

typedef struct l_node * pnode;

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

问题是我无法找到如何将适当的指针传递给函数叶。我不知道它应该是指向 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

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

存在给定的树节点结构。我宁愿将它命名为 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;
}

通过更改去向 left/right 列表的顺序已更改。

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

Collect all leaves of BST and make list of them

c

tree

binary-search-tree