c - 二叉树 - 打印叶到叶路径 [C]

Question

我正在努力做作业，但遇到了一些困难。

Create a recursive function who prints the path between a leaf to another in an integer binary tree (i.e. the tree holds integers).

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

Note: You will have to handle the following situations:

• there's no a and/or b in the tree. if so, return -1.

• If there are, print all the values between the node whose value a and the node whose value b. return 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。

Answer 1

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

• 搜索 a并将从根到该节点的路径保存在p1中(大小 n )。
• 搜索 b并将从根到该节点的路径保存在p2中(大小 m )。
• 比较两条路径。当两个值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;