【数据结构周周练】022 从大到小输出二叉排序树中小于某个值的所有结点编号及数据

小鱼儿 2021-06-11 15:13 319阅读 0赞

# 一、二叉排序树 #

今天给大家分享的是二叉排序树的应用，从大到小输出二叉排序树中小于某个值的所有结点编号及数据。

我们知道，我们做中序遍历时，先访问左子树，再访问根节点，最后访问右子树；通过中序遍历会得到一个递增的序列。该应用要求得到从大到小，一个递减的序列，我们可以通过先访问右子树，再访问根节点，最后访问左子树，就可以得到一个递减的序列。

当然我们还可以使用中序遍历，将数据存到栈中输出，就可以逆序输出了；或者我们可以利用头插法建立单链表，然后遍历单链表输出也能满足需求，就是代码量比较多啦，大家可以尝试自己写一下。

为了让大家能更好的看到效果，我们支持用户自己定义该数据。

# 二、示例 #

给定下面的二叉排序树和一个值，从大到小输出二叉排序树中小于该值的所有结点编号及数据。其中圆角矩形内为结点数据，旁边数字为结点编号，箭头指向的结点为箭尾的孩子结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][] 二叉排序树

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct BiSTNode {
    	int data;
    	int number;
    	struct BiSTNode *lChild, *rChild;
    }BiSTNode, *BiSortTree;
    
    int numData[] = { 12,5,11,67,55,45,57,72 };
    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 VisitTree(BiSortTree BST,int data) {
    
    	if (BST->rChild)
    		VisitTree(BST->rChild,data);
    	if (BST->data<data)
    	{
    		cout << "The number of the current node is " << BST->number << " ,and the data is " << BST->data << " ;\n";
    	}
    	if (BST->lChild)
    		VisitTree(BST->lChild,data);
    }
    
    
    void main() {
    	BiSortTree BST = NULL;
    	int data ;
    	while (number<length)
    	{
    		EstablishBiSortTree(BST);
    	}
    
    	cout << "Please input a data and we will output all data which smaller than the data:";
    	cin >> data;
    
    	VisitTree(BST, data);
    }

# 四、实现效果 #

![20181102211137835.png][]

![20181102210954677.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/57ecc8adf4ba41eba45048ab92680f72.png
[20181102211137835.png]: /images/20210516/a7d8781c358e4254b8c9fd7d4e1438c3.png
[20181102210954677.png]: /images/20210516/66a1f3a1111144b2b57c8f7fbc127f23.png