二叉樹 - 打印葉到葉的路徑[C]

Question

我想做我的功課，但我有一些困難。

創建一個遞歸函數，用於在整數二叉樹（即樹保留整數）中打印葉與另一葉之間的路徑。

int printPath（Tree * t，int a，int b）。

注意：您將不得不處理以下情況：

• 有樹沒有一個和/或b。如果是這樣，則返回-1。

• 如果存在，則打印值爲a的節點與其值爲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。

Answer 1

我看不到你的數組在哪裏，說你的樹必須被排序。一個直觀的算法可以是：

• 搜索a和根的路徑保存到此節點p1（大小n）。
• 搜索b並保存從根到此節點的路徑p2（大小爲m）。
• 比較兩條路徑。當兩個值p1[i]和p2[i]不同時，您可以從p1[m]到p1[i]以及從p2[i]到p[m]的第二條路徑p1。

算法運行在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; 

Answer 2

您在平衡樹中搜索節點的方式將與您插入節點的方式相對應;如果你有一個遞歸函數來插入一個新的值，那麼你已經有了代碼來找到它:)

這是一個查找的例子;導出代碼打印路徑作爲一個練習的學生:)

注意事項

有四個possibilites在每片葉子： 1）葉是你正在尋找 的一個2）左邊的葉子有一個比你要搜索的葉子低的葉子，葉子的葉子會是葉子的葉子 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; 
} 

祝你好運，我希望這有助於。 :)