仅给定后序构造完整的二叉树?

Constructing full binary tree given only postorder?

我正在尝试构建一个完整的二叉树(完整的意思是每个非叶节点都有两个叶节点连接到它,即 node->rightnode->left!= NULL)仅给出树的后序遍历。此外,还给出了后序遍历中的节点是否为叶节点。给定的后序遍历如下所示:

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)" 是非叶节点。通常你不能只使用后序构造一棵树,因为连接有多种可能性,但我确信能够区分叶节点和非叶节点在某种程度上是很重要的。我当前的函数如下所示:

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。显然,这个实现只是向右构建节点。我怎样才能更新它以正确构建树?

编辑:让我补充一些我所知道的信息。因此,第一个节点必须始终是叶节点,而最后一个节点始终必须是根节点。由于这不是二叉搜索树,而只是一棵二叉树,因此您不能每次都使用更新的范围参数递归调用该函数。我的实现应该在O(n)时间内解决,但我就是想不通如何在构造树时利用节点是否为叶节点的知识。

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

  • 你应该使用ungetc()而不是fseek()回溯一个字符以避免在不支持搜索的流上失败。

  • 你应该写 (check == '(') 而不是硬编码 ASCII 字符值。它更便携,更易读。

  • 为了避免未定义的行为,您应该检查 EOFfscanf() 解析是否成功。事实上,这将避免对 check.

  • 进行测试的需要
  • 当你解析一个叶节点时,你不应该递归和解析当前节点下面的更多节点。

  • index 似乎是多余的,因为节点序列应该足以完全确定停止位置。

这是修改后的版本:

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;
}