二叉排序树插入结点

二叉排序树插入结点

BSTree *InsertBST(BSTree *bst,int key)       //插入节点
{
	BSTree *p,*s,*pre;
	s=(BSTree*)malloc(sizeof(BSTreeNode));
	s->data=key;
	s->lchild=s->rchild=NULL;
	if(bst==NULL)
	{
		bst=s;
		return bst;
	}
	p=bst;
	while(p)
	{
		pre=p;//指向其父节点
		if(p->data==key)return p;
		else if(p->data>key)p=p->lchild;
		else p=p->rchild;
	}
	if(pre->data<key)
		pre->rchild=s;
	else
		pre->lchild=s;
	return s;
}

 判断一棵二叉树是不是二叉排序树

#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct BSTreeNode
{
	int data;
	struct BSTreeNode *lchild,*rchild;
}BSTree;
int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}
BSTree *pre=NULL;//中序遍历二叉排序树，所得序列为增序，在遍历中将当前结点和前驱结点比较。全局变量pre保存其前驱结点
bool flag=true;//全局变量，初值为true，若不是二叉排序树，置flag为false
void JudgeBST(BSTree *t,bool flag)
{
	if(t!=NULL && flag)
	{
		JudgeBST(t->lchild,flag);//中序遍历左子树
		if(pre==NULL)pre=t;//中序遍历的第一个结点不必判断
		else if(pre->data<t->data)pre=t;//前驱指针指向当前结点
		else {flag=false;}//不是二叉排序树
		JudgeBST(t->rchild,flag);//中序遍历右子树
	}
}