判断一棵二叉树是否为二叉搜索树(二叉排序树)的三种方法

判断一棵二叉树是否为二叉搜索树(二叉排序树)的三种方法

二叉搜索树性质：
    1.左子树的节点值<根节点值；
    2.右子树的节点值>根节点值；
    3.二叉搜索树的中序遍历序列为单调递增序列
根据以上性质可以总结出以下方法：

    方法一：如果左子树节点的最大值<根节点的值，右子树节点的最小值大于根节点，则一定为二叉搜索树
    方法二：中序遍历二叉树，若遍历结果序列单调递增，一定为二叉搜索树
        

方法一具体代码如下：

二叉树定义：

struct BiNode
{int dada;BiNode *lchild;BiNode *rchild;
};

递归找最大值：

int Find_max(BiNode *root)///找最大值
{int maxm=root->data;if(root->lchild!=NULL){int maxleft=Find_max(root->lchild);maxm=max(maxm,maxleft);}if(root->rchild!=NULL){int maxright=Find_max(root->rchild);maxm=max(maxm,maxright);}return maxm;
}

递归找最小值：

int Find_min(BiNode *root)///找最小值
{int minn=root->data;if(root->lchild!=NULL){int minleft=Find_min(root->lchild);minn=min(minn,minleft);}if(root->rchild!=NULL){int minright=Find_min(root->rchild);minn=min(minn,minnright);}return minn;
}

判断函数：

int ISBST(BiNode *root)
{if(root==NULL)return 1;if(root->lchild!=NULL && Find_max(root->lchild) > root->data)///如果左子树最大值大于根节点，直接returnreturn 0；if(root->rchild!=NULL && Find_min(root->rchild) < root->data)///如果右子树的最小值小于根节点，直接returnreturn 0;if(ISBST(root->lchild) && ISBST(root->rchild))///左子树和右子树都符合二叉搜索树的性质的二叉树才是二叉搜素树return 1;}

方法二：

将二叉树的中序遍历结果保存在数组中，判断数组中的元素是否单调递增即可

void inorder(BiNode *root)
{if(root==NULL)return;if(root->lchild!=NULL)inorder(root->lchild);temp[k++]=root->data;if(root->rchild!=NULL)inorder(root->rchild);
}
void ISBST()
{int flag=0;for(int i=1; i

int ISBST(BiNode *root)
{BiNode *pre;if(root!=NULL){if(!ISBST(root->lchild))return 0;if(pre!=NULL && root->data data)return 0;pre=root;if(!ISBST(root->rchild))return 0;}return 1;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！