NOJ数据结构024——二叉排序树的判别

蔚落 2022-10-05 01:52 142阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70][]

代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct BiTNode {
        
    	int data;
    	struct BiTNode* left;
    	struct BiTNode* right;
    }BiTNode, * BiTree;
    
    BiTree CreateBiTree();   //创建二叉树
    int JudgeBinary(BiTree T);   //判断是否是二叉排序树
    
    int main()
    {
        
    	BiTree T;
    	T = CreateBiTree();
    	if (JudgeBinary(T)) {
        
    		printf("yes");
    	}
    	else {
        
    		printf("no");
    	}
    	return 0;
    }
    
    BiTree CreateBiTree()
    {
           //创建二叉树
    	int data;
    	scanf("%d", &data);
    	if (data == -1) {
        
    		return NULL;
    	}
    	BiTree tmp;
    	tmp = (BiTree)malloc(sizeof(BiTNode));
    	if (!tmp) {
        
    		return NULL;
    	}
    	tmp->data = data;
    	tmp->left = CreateBiTree();
    	tmp->right = CreateBiTree();
    	return tmp;
    }
    
    int JudgeBinary(BiTree T)
    {
           //判断是否是二叉排序树
    	if (!T) {
        
    		return 1;
    	}
    	else if (T->left && T->right) {
        
    		if (T->data < T->left->data || T->data>T->right->data) {
        
    			return 0;
    		}
    		else {
        
    			return(JudgeBinary(T->left) && JudgeBinary(T->right));
    		}
    	}
    	else if (T->left) {
        
    		if (T->data > T->left->data) {
        
    			return (JudgeBinary(T->left));
    		}
    		else {
        
    			return 0;
    		}
    	}
    	else if (T->right) {
        
    		if (T->data < T->right->data) {
        
    			return (JudgeBinary(T->right));
    		}
    		else {
        
    			return 0;
    		}
    	}
    	return 1;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221005/461faf69e13e4235890579fa45551056.png