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

 一、二叉排序树

从今天起，就给大家分享二叉排序树的代码啦，首先给大家简单讲解一下相关概念。

二叉排序树也称为二叉查找树，二叉排序树是一棵空树或具有如下性质：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

二叉排序树有这样一个特点：左子树结点值<根结点<右子树结点。所以对二叉树进行中序遍历会得到一个递增的序列。

废话不多说，接下来上代码，本次给大家分享的是二叉排序树的创建及遍历。

二、示例

利用递归算法将下列一组数据存入二叉排序树中，通过先序及中序遍历访问每个结点的编号，数据及所有的孩子结点。

{ 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, *parent;}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;BiSortTree treeParent = NULL;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 VisitBiSortTree(BiSortTree &BST) {	cout << "The number of present node is ：" << BST->number << "; ";	cout << "\tdata is ：" << BST->data << "; ";	if (BST->lChild)		cout << "\n\tlChild's number is :" << BST->lChild->number << ",\tdata is :" << BST->lChild->data << ";";	if (BST->rChild)		cout << "\n\trChild's number is :" << BST->rChild->number << ",\tdata is :" << BST->rChild->data << ";";	cout << endl;}void PreOrderVisitTree(BiSortTree &BST) {	VisitBiSortTree(BST);	if (BST->lChild)		PreOrderVisitTree(BST->lChild);	if (BST->rChild)		PreOrderVisitTree(BST->rChild);}void InOrderVisitTree(BiSortTree &BST) {		if (BST->lChild)		InOrderVisitTree(BST->lChild);	VisitBiSortTree(BST);	if (BST->rChild)		InOrderVisitTree(BST->rChild);}void main() {	BiSortTree BST = NULL;	while (number
    
   

四、实现效果

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