判断一棵二叉树是否为二叉排序树

2021-07-08 20:05

阅读:441

标签:void   style   stat   arc   malloc   表示   int   源代码   bit   

判断二叉排序树的代码如下:

 

static boolean IsSearchTree(Bitree *t)
{
	if(!t)             //空二叉树情况
		return true;
	else if(!(t.lchild)&&!(t.rchild))  //左右子树都无情况
		return true;
	else if((t.lchild)&&!(t.rchild)){  //只有左子树情况
		if(t.lchild.data>t.data)
			return false;
		else
			return IsSearchTree(t.lchild);
	}
	else if((t.rchild)&&!(t.lchild)){  //只有右子树的情况
		if(t.rchild.datat.data) || (t.rchild.data

  

完整的源代码如下:

#include "stdio.h"
#include "stdlib.h"
typedef struct node
{
    int data;
    struct node *lchild,*rchild;
}Bitree;
Bitree *B[100];
Bitree *CreateBiTree()
{
    int num,i,n;
    Bitree *t,*s;
    t=NULL;
    printf("建立二叉树(1表示为虚结点,0表示输入结束):/n");
    num=0;
    scanf("%d",&n);
    while(n!=0)
    {
        s=(Bitree *)malloc(sizeof(Bitree));
        s->data=n;
        s->lchild=s->rchild=NULL;
        num++;
        if(!t)
            t=s;
        B[num]=s;
        scanf("%d",&n);
    }
    for(i=1;i)
    {
        if(B[i]->data!=1)
        {
            if(2*i2*i]->data!=1)
                B[i]->lchild=B[2*i];
            if(2*i+12*i+1]->data!=1)
                B[i]->rchild=B[2*i+1];
        }
    }
    return t;
}
int IsSearchTree(const Bitree *t)  //递归遍历二叉树是否为二叉排序树
{
    if(!t)        //空二叉树情况
        return 1;
    else if(!(t->lchild) && !(t->rchild))   //左右子树都无情况
        return 1;
    else if((t->lchild) && !(t->rchild))    //只有左子树情况
    {
        if(t->lchild->data>t->data)
            return 0;
        else
            return IsSearchTree(t->lchild);
    }
    else if((t->rchild) && !(t->lchild))   //只有右子树情况
    {
        if(t->rchild->datadata)
            return 0;
        else
            return IsSearchTree(t->rchild);
    }
    else         //左右子树全有情况
    {                                
        if((t->lchild->data>t->data) || (t->rchild->datadata))
            return 0;
        else
            return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );
    }
}
int main(void)
{
    int flag=0;
    Bitree *tree;
    tree=CreateBiTree();
    flag=IsSearchTree(tree);
    if(flag)
        printf("这棵树是二叉排序树!/n");
    else
        printf("这棵树不是二叉排序树!/n");
    system("pause");
    return 0;
}

 

判断一棵二叉树是否为二叉排序树

标签:void   style   stat   arc   malloc   表示   int   源代码   bit   

原文地址:https://www.cnblogs.com/wuyepeng/p/9582011.html

上一篇:Spring03-AOP

下一篇:java中捕获异常


评论


亲,登录后才可以留言!