排序二叉树的创建，插入和查找

ゞ浴缸里的玫瑰 2024-02-18 21:06 72阅读 0赞

排序二叉树，又称二叉搜索树

其定义如下：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

我们首先定义一个数据类型：typedef int KeyType; 此后用KeyType关键字来代替int。

排序二叉树使用二叉链表储存，其结构体定义如下：

typedef struct node
    {
    	KeyType key;
    	struct node *lchild,*rchild;
    } BSTNode;

插入节点算法：

bool InsertBST(BSTNode *&bt,KeyType k)
    {
    	if(bt==NULL)	//如果为空，则创建一个节点
    	{
    		bt=(BSTNode *)malloc(sizeof(BSTNode));
    		bt->key=k;  bt->lchild=bt->rchild=NULL;	//该节点为根节点，左孩子和右孩子指针均置空
    		return true;
    	}
    	else if(k==bt->key)	//如果存在，则返回false
    		return false;
    	else if(k<bt->key)	//如果被插入数据较小，则插入到左子树
    		return InsertBST(bt->lchild,k);
    	else	//如果被插入数据较大，则插入到右子数
    		return InsertBST(bt->rchild,k);
    }//bool

创建排序二叉树的方法是利用插入算法，当构造时即相当于原二叉树为空：

BSTNode *CreateBST(KeyType A[],int n)
    {
    	BSTNode *bt=NULL;	//置空
    	int i=0;
    	while(i<n)	//循环，直到A[]中每个元素均插入到二叉搜索树中
    	{
    		InsertBST(bt,A[i]);
    		i++;
    	}
    	return bt;
    }//BSTNode *

想要判断一颗树是不是排序二叉树可以用一下方法：

1.首先对二叉树进行中序遍历，并用一个全局数组储存这个路径

2.判断数组是否递增，如果是的话即为排序二叉树。

算法如下：

KeyType num[10];
    int i=0;
    void Inorder(BSTNode *bt)			//中序
    {
    	if(bt!=NULL)
    	{	
    		Inorder(bt->lchild);
    		num[i++]=bt->key;
    		Inorder(bt->rchild);
    	}
    }
    
    bool Judge(KeyType A[],int n)	//判断数组是否递增
    {
    	int i;
    	for(i=0;i<n-1;i++)
    	{	
    		if(A[i]>A[i+1])
    			return false;
    	}
    	return true;
    }

搜索二叉树的查找：

1.递归算法

BSTNode *SearchBST(BSTNode *bt,KeyType k)
    {
    	if(bt==NULL)	//如果树为空，返回bt
    	{	return bt;
    	}
    	else if(k==bt->key)
    	{
    		printf("%d ",bt->key);
    		return bt;
    	}
    	else if(k<bt->key)	//如果被查找元素小于节点元素，输出路径并递归查找左孩子
    	{	
    		printf("%d ",bt->key);
    		return SearchBST(bt->lchild,k);
    	}
    	else
    	{
    		printf("%d ",bt->key);	//如果被查找元素大于节点元素，输出路径并递归查找右孩子
    		return SearchBST(bt->rchild,k);
    	}
    }//BSTNode *

2.非递归算法

int SearchBST1(BSTNode *bt,KeyType k)
    {
    	BSTNode *a;
    	if(bt->key==k)
    	{	printf("%d ",bt->key);
    		return 1;
    	}
    	if(bt!=NULL)
    		printf("%d ",bt->key);
    	while(bt!=NULL)
    	{
    		if(k>bt->key)
    		{
    			a=bt->rchild;
    			printf("%d ",a->key);
    			if(a->key==k)	
    				break;
    			bt=a;
    		}
    		else if(k<bt->key)
    		{
    			a=bt->lchild;
    			printf("%d ",a->key);
    			if(a->key==k)			
    				break;
    			bt=a;
    		}
    		else
    		{
    			printf("%d ",bt->key);
    			break;
    		}
    	}
    	return 1;
    }