【数据结构周周练】019 利用递归算法创建二叉排序树并遍历

川长思鸟来 2021-06-11 15:13 365阅读 0赞

#  一、二叉排序树 #

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

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

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

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

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

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

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

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

# 二、示例 #

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

{ 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, *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<length)
    	{
    		EstablishBiSortTree(BST);
    	}
    	
    	cout << "\n********【先序遍历二叉排序树。Preorder traversal binary sort tree】********" << endl;
    	PreOrderVisitTree(BST);
    
    	cout << "\n********【中序遍历二叉排序树。Inorder traversal binary sort tree】********" << endl;
    	InOrderVisitTree(BST);
    }

# 四、实现效果 #

![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 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/62649e0748da4e4a954e294ec65fa244.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/49723e40c9254bddb96d8947821896d1.png