设计判断二叉树是否为二叉排序树的算法。

[问答题]

设计判断二叉树是否为二叉排序树的算法。

查看答案及解析

蝎子莱莱w

int minnum=-32768,flag=1;
typedef struct node
{
    int key;
    struct node *lchild,*rchild;
}bitree;
void inorder(bitree *bt)
{
    if (bt!=0)
    {
        inorder(bt->lchild);
        if(minnum>bt->key)
            flag=0;
        minnum=bt->key;
        inorder(bt->rchild);
    }
}

发表于 2021-12-17 20:39:43 回复(0)

牛客293941666号

int Predata = -32768;//记录中序遍历前一个结点的值
int JudgeBST(BTNode* root)
{
    //代码思想，
    //二叉排序树经过中序遍历会得到一个递增有序的数列
    //所以基于中序遍历代码，修改visit函数，边遍历边与中序遍历访问的前一个结点的值进行比较

    int left = 0;
    int right = 0;//用left,right接收递归过程左右子树的返回值

    if (root == NULL)
        return 1;//空树也是一个二叉排序树
    left = JudgeBST(root->left);
    if (left == 0 || root->data <= Predata)
        return 0;
    Predata = root->data;
    right = JudgeBST(root->right);
    return right;
}

发表于 2023-10-16 20:47:52 回复(0)