確定樹是否有序的函數（即BST）

Question

我有這些函數來確定二叉樹是否被排序。

（假設我們已經實施了treemanagement.c，我已經修改爲主機整數，而不是字符串）

int ordtree(Treeptr p) { 
    int a, b; 
    return (p == NULL || fun(p, &a, &b)); 
} 

int fun(Treeptr p, int * ap, int * bp) { 
    int a, b; 
    // Is 'p' a leaf? 
    if (p->left == NULL && p->right == NULL) { 
    *ap = p->value; 
    return 1; 
    } 

    // Does 'p' have only a left child? 
    if (p->right == NULL) { 
    *bp = p->value; 
    return (fun(p->left, &b, ap) && p->value > b); 
    } 

    // Does 'p' have only a right child? 
    if (p->left == NULL) { 
    *ap = p->value; 
    return (fun(p->right, &a, bp) && p->value < a); 
    } 

    // 'p' has two children 
    return (fun(p->right, &a, bp) && fun(p->left, &b, ap)); 
} 

的問題是，這不是一個完美的樹工作（所有節點兩個孩子，因爲在我的代碼中沒有完美的樹的情況下檢查值！）。

例如，這個無序樹將被評估爲有序樹！

 4 
    2  6 
1 8 5 7 

更大的問題是，這是來自一個測試，我有義務使用這個「代碼」並填寫GAPs。

int fun(Treeptr p, .....GAP A.....) 
{ 
    int a, b; 
    if (p->left == NULL && .....GAP B.....) { 
    *ap = p->value; 
    .....GAP C..... 
    } 
    if (p->right == NULL) { 
    *bp = p->value; 
    return (fun(.....GAP D.....) && p->value > b); 
    } 
    if (.....GAP E.....) { 
    .....GAP F..... 
    return (fun(p->right, &a, bp) && GAP .....G.....); 
    } 
    return (.....GAP H.....); 
} 

任何指導？

Answer 1

這是我能做的最好的代碼。

int fun(Treeptr p, int * ap, int * bp) { 
    int a, b; 
    // Is 'p' a leaf? 
    if (p->left == NULL && p->right == NULL) { 
    *ap = p->value; 
    *bp = p->value; return 1; //gap c 
    } 

    // Does 'p' have only a left child? 
    if (p->right == NULL) { 
    *bp = p->value; 
    return (fun(p->left, ap, &b) && p->value > b); //gap d 
    } 

    // Does 'p' have only a right child? 
    if (p->left == NULL) { 
    *ap = p->value; 
    return (fun(p->right, &a, bp) && p->value < a); // gap g 
    } 

    // 'p' has two children 
    return (fun(p->right, &a, bp) && fun(p->left, ap, &b) && a > p->value && p->value > b); // gap h 
}