1

我正在尝试做我的家庭作业，但我遇到了一些困难。

创建一个递归函数，它打印整数二叉树中叶子到另一个叶子之间的路径（即树保存整数）。

int printPath(Tree* t, int a, int b)。

注意：您将不得不处理以下情况：

  • 树中没有 a 和/或 b。如果是，则返回 -1。

  • 如果有，则打印其 valuea的节点和 value 的节点之间的所有值b。返回 0。

我试过这段代码：

int print1(Tree* tree, int a, int b) {
    int cnt;
    int c = MAX(a, b), d = MIN(a, b);
    a = d;
    b = c;
    if (!tree)
        return -1;
    /*
     if (tree->key.id > b || tree->key.id < a) {
         if(tree->key.id > b)
             cnt = print(tree->left, a, b);
         else
             cnt = print(tree->right, a, b);
     }*/

    if (tree->key.id == a || tree->key.id == b) {
        if (tree->key.HWGrade) {
            printf("e) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        }
        return 0;
    }

    if (tree->key.id > b) {
        cnt = print1(tree->left, a, b);
        if (tree->key.HWGrade) {
            printf("c) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        } else
            return 0;
    } else {
        if (tree->key.id > a) {
            cnt = print1(tree->left, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {

                if (tree->key.HWGrade) {
                    printf("d) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (tree->key.id < a) {
        cnt = print1(tree->right, a, b);
        if (tree->key.id != a && tree->key.id != b && !cnt) {
            if (tree->key.HWGrade) {
                printf("a) , %d -> ", tree->key.id);
                tree->key.HWGrade = 0;
            } else
                return 0;
        }
    } else {
        if (tree->key.id < b) {
            cnt = print1(tree->right, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {
                if (tree->key.HWGrade) {
                    printf("b) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (cnt == 0)
        return 0;
    return -1;
}

但这似乎不起作用。

使用过的结构：

typedef struct {
    int id;
    int HWGrade;
    int ExamGrade;
} MatamStudent;

typedef struct Tree{
    int Data;
    struct Link* list;
    MatamStudent key;
    struct Tree *left;
    struct Tree *right;
} Tree;

我在 Ubuntu 下使用 GCC 和 Eclipse。

4

2 回答 2

1

我没有看到你的数组在哪里说你的树必须被排序。一个直观的算法可能是：

  • 在（大小）中搜索a并保存从根到该节点的路径。p1n
  • 在（大小）中搜索b并保存从根到该节点的路径。p2m
  • 比较两条路径。当两个值p1[i]和p2[i]不同时，您可以p1从p1[m]到p1[i]，第二条路径从p2[i]到p[m]。

该算法在 中运行O(S)，其中S是叶子的数量。

#include <stdio.h>

size_t mid, i;
int p1[MAX_LEAVES];
int p2[MAX_LEAVES];
int n = searchTree(p1, tree, a);
int m = searchTree(p2, tree, b);

if (n == 0 || m == 0)
    return -1;

for (mid = 0; mid < n && mid < m && p1[mid] == p2[mid]; mid++)
    ;

for (i = n - 1; i >= mid; i--)
    printf("%d ", p1[i]);

for (i = mid; i < m; i++)
    printf("%d ", p2[i]);

putchar('\n');

return 0;
于 2013-05-30T17:25:34.060 回答
0

您在平衡树中搜索节点的方式将与您插入节点的方式相对应；如果你有一个递归函数来插入一个新值，那么你已经有了找到它的代码:)

这是一个查找示例；导出代码以打印路径作为练习留给学生:)

注意事项

每片叶子都有四种可能性：1）叶子是您要搜索的叶子 2）左侧叶子的 id 低于您要搜索的叶子，并且键将是该叶子的子节点3) 右侧叶子的 id 大于您要搜索的叶子 4) 没有更多叶子并且该值不存在。

您的代码比它需要的要复杂得多。树结构可以具有任意一组属性，但它必须具有根叶。叶结构只需要 3 个属性（它可以有更多，但不是必须的）：它需要 2 个（对于二叉树）指向子节点的指针，并且它需要一个键。如果你有比这更多的数据，你会让这变得比现在更难。这里给你一个有趣的挑战——在不修改搜索代码的情况下添加打印代码；关注点分离，编程面包和黄油:)

Node* find_child(Node* parent, int id)
{
    if (parent->id == id)
        return parent;
    else if (parent->left.id < id)
        return find_child(parent->left, id);
    else if(parent->right.id < id)
        return find_child(parent->right, id)
    else
        return NULL;
}

祝你好运，我希望这会有所帮助。:)

于 2013-05-30T17:42:30.300 回答