Функция, чтобы определить, упорядочено ли дерево (т. Е. 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 

Большая проблема в том, что это происходит из теста, и я обязан использовать этот «код» и заполнить пробелы.

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 
}