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

一、二叉排序树

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

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

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

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

二、示例

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

 三、代码

#include
   
    #include
    
     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
     
      number << " ,and the data is " << BST->data << " ;\n";	}	if (BST->lChild)		VisitTree(BST->lChild,data);}void main() {	BiSortTree BST = NULL;	int data ;	while (number
      
       > data;	VisitTree(BST, data);}
      
     
    
   

四、实现效果

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