将二叉树转换为简单链表

Question

struct Monitor {
    int codMonitor;
    char* producator;
    float diagonala;
    int numarPorturi;
};

struct nodls {
    Monitor info;
    nodls* next;
};

nodls* creareNod(Monitor m) { --create node 
    nodls* nou = (nodls*)malloc(sizeof(nodls));
    nou->info.codMonitor = m.codMonitor;
    nou->info.producator = (char*)malloc(sizeof(char)*(strlen(m.producator) + 1));
    strcpy(nou->info.producator, m.producator);
    nou->info.diagonala = m.diagonala;
    nou->info.numarPorturi = m.numarPorturi;
    nou->next = nou;

    return nou;
}

nodls* inserare(nodls* cap, Monitor m) { -- insert 
    nodls* nou = creareNod(m);
    if (cap == NULL) {
        cap = nou;
        cap->next = cap;
    }
    else
    {
        nodls* temp = cap;
        while (temp->next != cap)
            temp = temp->next;
        temp->next = nou;
        nou->next = cap;
    }
    return cap;
}

void afisareMonitor(Monitor m) { -- display struct
    printf("\nMonitorul cu codul %d, producatorul %s, diagonala %f, numarul de porturi %d",
        m.codMonitor, m.producator, m.diagonala, m.numarPorturi);
}

void traversare(nodls** cap) { --display function
    nodls* temp = *cap;
    if (cap == NULL)
        printf("\nLista este goala");
    while (temp->next != *cap) {
        afisareMonitor(temp->info);
        temp = temp->next;
    }
    afisareMonitor(temp->info);

}

void stergereNod(nodls* cap) --delete node function
{
.......
}

void dezalocare(nodls* cap) { free allocate space
............
}

我如何转换使用以下代码，我的二叉树到一个简单的链表。这也许可以用递归来完成。

getLeavesList(root) {

    if root is NULL: return

    if root is leaf_node: add_to_leaves_list(root)

    getLeavesList(root -> left)

    getLeavesList(root -> right)
}

因此，如果根为NULL，也就是，如果函数没有收到有效的指针，则返回错误消息。

如果根是叶，这是，如果左子节点和右子节点都为NULL，您必须将其添加到叶节点列表中。

Answer 1

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

本文介绍了三种简单的深度优先方法(preorder、inorder、postorder)，用于遍历二叉树。它还有一个很好的简洁的C示例。

您提供的伪代码算法实际上是正确的预序方法。

在

void printPreorder(struct node*node)

printf（“%d”，节点->数据）；

检查节点是否是叶，如果是，将其添加到列表中：

if((node->left == NULL) && (node->right == NULL))
{
     appendList(&node);   
}

当然，appendlist只是我临时创建的，但是根据问题中提供的代码，您将知道如何添加到链接列表中。如果没有，请随时询问。

ps：https://www.geeksforgeeks.org/是一个了不起的资源，感谢那些了不起的工作！

PSPS：如果您希望在第一次使用NULL调用函数时返回错误消息，也就是说，如果没有向遍历传递有效的树，我建议您创建一个包装函数来调用递归树。然后，在这个包装器中，您可以在调用递归方法之前检查传递给它的head是否为NULL。