判别二叉树是否为二叉排序树

川长思鸟来 2022-08-02 12:40 130阅读 0赞

设二叉树用二叉链表表示，且每个结点的键值互不相同，请编写判别该二叉树是否为二叉排序树的非递归算法。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：  
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；  
（3）左、右子树也分别为二叉排序树；  
（4）没有键值相等的节点。

#include "stdafx.h"
    #include<vector>
    #include<iostream>   
    using namespace std;
    
    struct BiNOde
    {
    	int ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    
    
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	root->ele = 45;
    	node1->ele = 38;
    	node2->ele = 55;
    	node3->ele = 33;
    	node4->ele = 43;
    	node5->ele = 19;
    	node6->ele = 16;
    	node7->ele = 52;
    	node8->ele = 58;
    	node9->ele = 50;
    	node10->ele = 4;
    	node11->ele = 35;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = node11;
    	node4->lnode = node10;
    	node4->rnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = NULL;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;    
    	//node12->ele = 12;    
    	//node12->lnode = NULL;    
    	//node12->rnode = NULL;    
    	//node6->lnode = node11;    
    	return root;
    }
    
    
    //非递归
    bool IsBanarySearchTree(BiNOde*root)
    {
    	vector<BiNOde*>vec,aa;
    	vec.push_back(root);
    	BiNOde*n;
    	while (!vec.empty())
    	{
    		for (int i = 0; i < vec.size(); i++)
    		{
    			if (vec[i]->lnode != NULL)
    			{
    				if (vec[i]->ele < vec[i]->lnode->ele)
    					return false;
    				if (vec[i]->lnode->rnode != NULL)
    					if (vec[i]->lnode->rnode->ele > vec[i]->ele)
    						return false;
    				aa.push_back(vec[i]->lnode);
    			}
    
    			if (vec[i]->rnode != NULL)
    			{
    				if (vec[i]->ele > vec[i]->rnode->ele)
    					return false;
    				if (vec[i]->rnode->lnode != NULL)
    					if (vec[i]->rnode->lnode->ele < vec[i]->ele)
    						return false;
    				aa.push_back(vec[i]->rnode);
    			}
    		}
    		vec = aa;
    		aa.clear();
    	}
    	return true;
    }
    
    
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	BiNOde*root = create_tree();
    	if (IsBanarySearchTree(root))
    		cout << "是二分查找树" << endl;
    	else
    		cout << "不是二分查找树" << endl;
    	system("pause");
    	return 0;
    }