1

我正在尝试从有序和预购构建二叉树。每个节点都保存一个整数值的数据。我在拥有这些数组时遇到了问题：

预购：3,9,2,6,1,1,1,4 预购
：2,9,3,1,1,1,6,4

这是从中提取遍历的原始树：

    3
   / \
  9   6
 /   / \
2   1   4
   / \
  1   1

问题是我写的函数无法区分连续相等的数字。

这是 C 中的函数：

TREE createTreeFromPreAndIn(int pre[], int in[], int n){
    TREE res;
    res.root = createTreeFromPreAndInHelper(pre, in, n);
    return res;
}

TNODE* createTreeFromPreAndInHelper(int pre[], int in[], int n){
    int index;
    TNODE* rootL, *rootR, *root;

    if (n == 0)
        return NULL;
    else {
        index = findIndex(in, n, pre[0]); //returns the index of the first appearance of pre[0] in 'in'
        rootL = createTreeFromPreAndInHelper(pre+1, in, index);
        rootR = createTreeFromPreAndInHelper(pre+1+index, in+index+1, n-index-1);
        root = createNewTreeNode(pre[0], rootL, rootR);
        return root;
    }
}

提前致谢

4

2 回答 2

1

您没有足够的要求来识别确切的图像。您上面的树也可以表示为

              Fig 1                       Fig 2                      Fig 3

                3                          3                           3   
               / \                        / \                         / \
              9   6                      9   6                       9   6
             /   / \                    /   / \                     /   / \
            2   1   4                  2   1   4                   2   1   4
               / \                        /                             \
              1   1                      1                               1 
                                        /                               / 
                                       1                               1

根据您的启动，上述所有树都提供相同的有序和预购集。

有序= { 2,9,3,1,1,1,6,4 }

预购= { 3,9,2,6,1,1,1,4}

有歧义。因此，您无法使用此信息识别确切的树。您必须指定其他信息才能解决此问题。

如果您想重新创建它，您可以尝试在数组中包含边界。

例如：使用 -1 指定无子节点（假设我的节点值在任何情况下都不会是 -1）。

图。1：

按顺序：{-1,2,-1,9,-1,3,-1,1,-1,1,-1,1,-1,6,-1,4,-1}

预购：{3,9,2,-1,-1,-1,6,1,1,-1,-1,1,-1,-1,4,-1,-1}

图2：

按顺序：{-1,2,-1,9,-1,3,-1,1,-1,1,-1,1,-1,6,-1,4,-1}

预购：{3,9,2,-1,-1,-1,6,1,1,1,-1,-1,-1,-1,4,-1,-1}

显然预购会发生变化，它可以帮助您避免歧义并重新创建所需的结构。

于 2013-08-12T05:57:01.483 回答
0

歧义源于叶节点未完全定义的事实。为不构建的节点定义一个占位符（0 或 -1），并使用括号显示列表的结构。

预购： 3(9(2)(0))(6 (1(1)(1)) (4)) 带括号和占位符零，不带括号相同的数字序列可以“括起来”为 3 (9(2)(0))(6(1)(1(1)(4)))。

重复的数字与歧义无关。数字没有定义它在结构中的位置。相反，这是一个预序二叉树，其中每个节点（即父节点）根据定义具有左右子节点，但每个子节点都可以是具有两个子节点的父节点！因此，元素列表必须将树“填充”到它的叶子。

于 2013-08-12T06:35:05.763 回答