【数据结构周周练】020 二叉排序树的排序与迭代查找

我不是女神ヾ 2021-06-11 15:13 352阅读 0赞

#  一、二叉排序树 #

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

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

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

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

# 二、示例 #

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

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

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    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<length)
    	{
    		EstablishBiSortTree(BST);
    	}
    
    	cout << "【Sort the data form small to large】 : \n\t" ;
    	InOrderVisitTree(BST);
    	cout << "\n\n";
    
    	SearchBiSortTree(BST, 22);
    	SearchBiSortTree(BST, 23);
    	SearchBiSortTree(BST, 33);
    	SearchBiSortTree(BST, 55);
    
    }

# 四、实现效果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/64a942491f9e415a94a8df70fad5d281.png