【数据结构周周】022从二进制输出树中小于一定值的所有节点的编号和数据从大到小输出

今天，我将与您分享二进制排序树的应用程序. 从大到小，将输出二进制排序树中小于特定值的所有节点号和数据.

我们知道，当我们进行中阶遍历时，我们首先访问左子树，然后是根节点，最后是右子树；通过中阶遍历，我们将得到一个递增的序列. 该应用程序需要从大到小的降序排列. 通过先访问右子树，然后访问根节点，最后访问左子树，我们可以获得递减的序列.

当然，我们也可以使用有序遍历，将数据保存到堆栈中并输出，然后以相反的顺序输出；或者我们可以使用head插值方法构建一个单链列表二叉排序树排序，然后遍历单链列表输出也可以满足需求，即代码量更多，您可以尝试自己编写.

为了让每个人都能更好地看到效果，我们支持用户自己定义数据.

给出下面的二进制排序树和一个值，将二进制排序树中小于该值的所有节点号和数据从大到小输出. 圆角矩形中的数据是节点数据二叉排序树排序，其旁边的数字是节点号，箭头所指的节点是箭头末端的子节点.

二进制排序树

#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);
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-273866-1.html