将二进制树转换为简单的链接列表

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.orgtree-traversals-inorder-preorder-and-postorder

本文介绍了3种简单的深度优先方法(preorder, inorder, postorder)来遍历二叉树。它还有一个很好的C语言的紧凑例子。

你提供的伪代码算法实际上是正确的preorder方法。

你唯一要做的修改是在

void printPreorder(struct node* node)

方法是代替打印节点的数据。

printf("%d ", node->data);

而是检查该节点是否是叶子，如果是，则将其添加到列表中。

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

当然了 appendList 是我临时创作的，但根据你在问题中提供的代码，你会知道如何添加到link-list中。如果不知道，请随时提问。

ps: https:/www.geeksforgeeks.org 是一个惊人的资源帽子的那些家伙的惊人的工作!

psps: 如果你想在第一次调用函数时返回一个错误信息，也就是说，如果没有有效的树被传递给遍历，我建议你做一个包装函数来调用递归函数。然后，在那个包装器中，你可以在你根本没有调用递归方法之前就检查传递给它的头是否为NULL。