构造仅给定后序的完整二叉树? [英] Constructing full binary tree given only postorder?

问题描述

我正在尝试构造一个完整的二叉树(完全意味着每个非叶节点都有两个与其连接的叶节点，即node->right和node->left为!= NULL)，仅给出了该树的后序遍历.另外，给出了后遍历中的节点是否为叶节点.给定的后序遍历如下所示:

I'm trying to construct a full binary tree (full meaning that every non leaf node has two leaf nodes connecting to it, i.e. node->right and node->left are != NULL) given only the postorder traversal of the tree. In addition, I am given whether or not the node in the postorder traversal is a leaf node or not. The given postorder traversal looks like this:

2(1.000000e+00)
3(1.000000e+00)
(1.000000e+00 1.000000e+00)
1(1.000000e+00)
(1.000000e+00 2.000000e+00)

例如，

，其中格式"%d(%le)"的行是叶节点，而"(%le %le)"是非叶节点.通常，您不能仅使用后序来构造树，因为存在多种连接可能性，但是我敢肯定，区分叶子节点和非叶子节点在某种程度上很重要.我当前的功能如下:

for example, where a line of the format "%d(%le)" is a leaf node and "(%le %le)" is a non-leaf node. Normally you can't construct a tree using only postorder because there would be multiple possibilities for connections, but I'm sure that being able to differentiate leaf vs. non-leaf nodes is important somehow. My current function looks like this:

Node *constructTreeHelper(FILE *infile, int *index) { 
    // Base case 
    if (*index <= 0) {
        return NULL; 
    }
    Node *root = NULL;

    // Check for the "(" character
    int check;
    check = getc(infile);
    fseek(infile, -1, SEEK_CUR);

    // If the node is not a leaf node
    if (check == 40) {
        double lwire, rwire;
        fscanf(infile, "(%le %le)\n", &lwire, &rwire);
        root = createNode(0, 0, lwire, rwire);
        *index = *index - 1;
        if (*index >= 0) { 
            root->right = constructTreeHelper(infile, index); 
            root->left = constructTreeHelper(infile, index); 
        } 
    } else {
        // If the node is a leaf node
        int sink;
        double cap;
        fscanf(infile, "%d(%le)\n", &sink, &cap);
        root = createNode(sink, cap, 0, 0);
        *index = *index - 1;
        if (*index >= 0) { 
            root->right = constructTreeHelper(infile, index); 
            root->left = constructTreeHelper(infile, index); 
        } 
    }
    return root;
} 

其中，index等于树中的节点数-1.显然，此实现仅在右侧构建节点.如何更新它以正确构造树?

where index is equal to the number of nodes in the tree - 1. Obviously, this implementation only builds nodes to the right. How can I update this to properly construct the tree?

让我添加一些有关我所知道的信息.因此，第一个节点始终必须是叶节点，而最后一个节点始终必须是根节点.由于这不是二进制搜索树，而是简单的二进制树，因此您不能每次使用更新的范围参数来递归地调用该函数.我的实现应在O(n)时间内解决它，但我只是想不通如何在构造树时利用节点是否为叶节点的知识.

Let me add some more information about what I know. So, the first node always has to be a leaf node, and the last node always has to be the root. Since this is not a binary search tree, but rather simply a binary tree, you cannot recursively call the function with updated range parameters each time. My implementation should solve it in O(n) time, but I just can't figure out how to make use of the knowledge in whether or not a node is a leaf node in constructing the tree.

推荐答案

您的代码中存在一些问题:

There are some problems in your code:

• 您应该使用ungetc()而不是fseek()回溯一个字符，以避免在不支持查找的流上失败.

• you should use ungetc() instead of fseek() to backtrack by one character to avoid failure on streams that do not support seeking.

您应该编写(check == '(')，而不是对ASCII字符值进行硬编码.它既可移植，也更具可读性.

you should write (check == '(') instead of hard coding the ASCII character value. It is both more portable and more readable.

为避免未定义的行为，应检查EOF和fscanf()解析是否成功.实际上，这将避免在check上进行测试的需要.

To avoid undefined behavior, you should check for EOF and for fscanf() parsing success. As a matter of fact, this would avoid the need for the test on check.

解析叶节点时，不应递归并解析当前节点以下的其他节点.

When you parse a leaf node, you should not recurse and parse further nodes below the current one.

index似乎是多余的，因为节点顺序应足以确定停在哪里.

index seems redundant as the sequence of nodes should suffice to full determine where to stop.

这是修改后的版本:

Node *constructTreeHelper(FILE *infile, int *index) { 
    double lwire, rwire;
    int sink;
    double cap;
    Node *node;

    // Base case 
    if (*index <= 0) {
        // This test seems redundant with the file contents */
        return NULL; 
    }

    // this fscanf will fail on the byte byte if it is not a '('
    if (fscanf(infile, " (%le %le)", &lwire, &rwire) == 2) {
       // If the node is not a leaf node
        node = createNode(0, 0, lwire, rwire);
        *index -= 1;
        node->right = constructTreeHelper(infile, index); 
        node->left = constructTreeHelper(infile, index); 
    } else if (fscanf(infile, "%d(%le)\n", &sink, &cap) == 2) {
        // If the node is a leaf node
        node = createNode(sink, cap, 0, 0);
        *index -= 1;
    } else {
        // invalid format or end of file */
        node = NULL;
    }
    return node;
} 

这篇关于构造仅给定后序的完整二叉树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！