c - 在给定的BST中查找最大子树，使其没有重复项

假设BST允许重复作为单独的顶点，我如何找到最高的子树，使其没有重复。
这是一个想法：
（1）检查根值是否出现在其右子树中（这样插入：left（2）遍历并执行（1）我可以找到所有没有重复的子树，存储它们的根指针和高度。
（3）比较高度我可以找到最大的搜索子树。
我不知道如何在遍历时存储这些信息。我找到了一些程序，可以找到所有使用散列映射的BST的复制子树，但是如果可能的话，我宁愿避免使用散列映射，因为我还没有在我的课程中使用它们。

<!-- language: lang-c -->

typedef struct vertex {
    int data;
    struct vertex *left;
    struct vertex *right;
} vertex, *pvertex;

// Utility functions

int Height(pvertex t){
    if (t == NULL)
        return 0;
    if (Height(t->left) > Height(t->right))
        return Height(t->left) + 1;
    else
        return Height(t->right) + 1;
}

int DoesItOccur(pvertex t, int k){
    if(!t)
        return 0;
    if(t->data==k)
        return 1;
    if(t->data<k){
        return DoesItOccur(t->left,k);
    }
}

// My function
pvertex MaxSeeked(pvertex t){
    if(!t)
        return NULL;
    if(DoesItOccur(t->right,t->data)==0)
        return t;
    else if{
        if(t->left && t->right){
            if(Height(MaxSeeked(t->left))>Height(MaxSeeked(t->right)))
                return t->left;
            else
                return t->right;
        }
    }
    else if{
    ......
    }
}

最佳答案

我不知道如何在遍历时存储这些信息。我找到了一些程序，可以找到所有使用散列映射的BST的复制子树，但是如果可能的话，我宁愿避免使用散列映射，因为我还没有在我的课程中使用它们。
首先，你只需要跟踪迄今为止发现的最大高度的所有子树。或者你可以把它限制在一个这样的，如果你需要发现的话。为了效率，你也应该跟踪最大高度实际上是什么。
我假设您不能将成员添加到节点结构中，但是如果可以，您可以添加一个或两个成员，在其中记录根在每个节点上的树是否包含任何重复，以及树的高度。您可以随时随地填充这些数据，并记住最大高度是什么，然后进行第二次遍历以收集节点。
但是，在不修改任何节点本身的情况下，您仍然可以通过其他方式（如链接列表）跟踪当前候选节点。你可以把你想要的任何元数据放到跟踪数据结构中。例如，

struct nondupe_subtree {
    struct vertex *root;
    int height;
    struct nondupe_subtree *next;
};

然后，比如说，您可以按广度优先顺序对树执行选择性遍历，并携带struct nondupe_subtree节点的链接列表：
首先访问根节点。
根据您描述的过程，测试每个已访问节点的根目录子树，以查看它是否包含任何重复项。
如果是，则将其子项排队进行遍历。
如果不是，则测量子树高度并相应地更新链接列表（或不更新）。不要将此节点的子节点排队。
当不再为遍历提供节点时，链表将包含所有的最大高度子树的根。
请注意，如果可以在初始DFS过程中计算和存储所有子树高度，则该算法在许多情况下会显著加快速度，因为它在其他情况下容易执行重复的树高度计算。其中很多，在某些情况下。
还请注意，尽管它确实简化了这个特定的算法，但是始终将被骗对象放在右边的规则对平衡树起作用，这也可能会降低性能。在最坏的情况下，如果顶点是重复的，则“树”的性能将是线性的。

关于c - 在给定的BST中查找最大子树，使其没有重复项，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56385827/