本文共 1951 字，大约阅读时间需要 6 分钟。

 一、二叉排序树

二叉排序树可以说是数据结构中相当重要的内容之一啦，昨天给大家讲了二叉排序树的创建与遍历，包括原理以及代码。今天给大家分享的是二叉排序树的排序与查找。

二叉排序树排序从小到大排序就是中序遍历，我们通过递归来实现。

二叉排序树的特点大家都知道，左子树结点值<根结点<右子树结点，所以二叉排序树的查找原理很简单，判断当前值与查找值的关系，查找值大，查找右子树，查找值小，查找左子树，查找值与当前值一样，查找成功，查找到空结点，查找失败，说明没有该结点。

所以我们既可以通过迭代来实现，又可以通过递归来实现，我给大家分享的是迭代，欢迎大家能积极思考，在下面评论附上你的代码。

二、示例

利用递归算法将下列一组数据存入二叉排序树中，并将其从小到大排序，判断22，23，33，55是否为该二叉排序树上的点。

{ 41,22,14,35,56,23,47,28,69,10,61,12 }

 三、代码

#include
   
    #include
    
     using namespace std;typedef struct BiSTNode {	int data;	int number;	struct BiSTNode *lChild, *rChild;}BiSTNode,*BiSortTree;int numData[] = { 41,22,14,35,56,23,47,28,69,10,61,12 };int length = sizeof(numData) / sizeof(int);int number = 0;int OperationBiSortTree(BiSortTree &BST,int data) {	BST = (BiSortTree)malloc(sizeof(BiSTNode));	if (!BST)	{		cout << "空间分配失败(Allocate space failure.)" << endl;		exit(OVERFLOW);	}	BST->data = data;	BST->number = number++;	BST->lChild = NULL;	BST->rChild = NULL;		return 1;}int EstablishBiSortTree(BiSortTree &BST) {	BiSortTree p = BST;	if (!BST)	{		OperationBiSortTree(BST, numData[number]);	}	else if (BST->data == numData[number])	{		cout << "This data \" " << BST->data << " \" is existing.\n";		number++;		return 0;	}	else if (BST->data > numData[number])		EstablishBiSortTree(BST->lChild);	else		EstablishBiSortTree(BST->rChild);	return 1;}void InOrderVisitTree(BiSortTree BST) {		if (BST->lChild)		InOrderVisitTree(BST->lChild);	cout << BST->data << " , ";	if (BST->rChild)		InOrderVisitTree(BST->rChild);}int SearchBiSortTree(BiSortTree BST, int data) {	BiSortTree p = BST;	while (p)	{		if (p->data == data)		{			cout << "This binary sort tree has the data " << data << ", and the number of the node is " << p->number << endl << endl;			return 1;		}		else if (p->data > data)			p = p->lChild;		else			p = p->rChild;	}	cout << "This binary sort tree does not have the data " << data << endl << endl;	return 0;}void main() {	BiSortTree BST = NULL;	while (number
    
   

四、实现效果

转载地址：http://xdyni.baihongyu.com/