【数据结构周周练】021 求某一个数据在二叉排序树中的层数

骑猪看日落 2021-06-11 15:13 343阅读 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 InOrderVisitTree(BiSortTree BST) {
    	
    	if (BST->lChild)
    		InOrderVisitTree(BST->lChild);
    	cout << BST->data << " , ";
    	if (BST->rChild)
    		InOrderVisitTree(BST->rChild);
    }
    
    int FindLevel(BiSortTree BST,int data) {
    	BiSortTree pT = BST;
    	int level = 1;
    	while (pT && pT->data != data)
    	{
    		if (pT->data > data)
    			pT = pT->lChild;
    		else
    			pT = pT->rChild;
    		level++;
    	}
    	if (pT) {
    		cout << "This binary sort tree has the data : " << pT->data << " , and the level is " << level << ";\n";
    		return 1;
    	}
    		
    	else {
    		cout << "This binary sort tree doesn't have the data : " << data << endl;
    		return 0;
    	}
    		
    }
    
    void main() {
    	BiSortTree BST = NULL;
    	while (number<length)
    	{
    		EstablishBiSortTree(BST);
    	}
    	cout << "\n****【中序遍历二叉排序树。 Inorder traversal binary sort tree】****" << endl;
    	InOrderVisitTree(BST);
    	cout << "\n\n";
    
    	FindLevel(BST, 12);
    	FindLevel(BST, 11);
    	FindLevel(BST, 33);
    
    }

# 四、实现效果 #

![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/2c7f941476704a168a490ffe363478e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/de2bc2b20e984a97a8c576bd04db04e0.png