基于C的二叉排序树实现数据结设计

阳光穿透心脏的1/2处 2024-04-03 08:09 7阅读 0赞

目录  
一、使用说明 3  
1、 操作手册 3  
1)建立二叉排序树 3  
2)插入元素 4  
3)查找元素 5  
4)退出 6  
2、 注意事项 5  
二、 概述 5  
1、 程序设计目的 5  
2、 算法思路 6  
3、 数据结构 6  
三、 函数接口 6  
1、 node结构体 6  
2、 Tree接口 7  
四、体会 7  
1、程序设计目的  
本题要求实现一个二叉排序树。二叉排序树是一个所有的左节点都比根节点小，右节点都比根节点大，易于查找的数据结构。本题要求我们熟悉二叉排序树的生成和节点的插入。

2、算法思路  
只是说二叉排序树的话算法非常简单，如果是ALV树的话就很复杂了。二叉排序树节点的插入只需要从根节点开始，不断地判定插入值和节点值的大小，小则进入左子树，大则进入右子树，在这过程中，本文转载自http://www.biyezuopin.vip/onews.asp?id=14638如果不存在子树了，就插入在该处即可。查找的算法也是一样的  
3、数据结构  
本题的数据结构为二叉树，用结构体来保存节点。  
这道题让我见识到了一个强而有力的查找数据结构二叉排序树。并操练了二叉排序树的插入和查找。对于排序的算法还有很多更优的方案，但二叉排序树是必须学习的一个数据结构，相信学会这个数据结构对我可以有很大的帮助。

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    struct Node{
         
    	int data;               //保存的数据
    	Node * leftChild;       //左子树
    	Node * rightChild;      //右子树
    };
    
    class Tree{
        
    private:
    	Node * root;                          //根节点
    public:
    	Tree() :root(NULL){
        };                 //默认构造函数
    	~Tree();                              //析构函数
    
    	void one_BuildTree();                 //生成二叉排序树
    	void two_Insert();                    //插入节点
    	void three_Find();                    //查找节点
    
    	void destroy(Node *p);                //摧毁节点
    	void build(Node *p, Node *current);   //生成二叉排序树辅助函数
    	void Print(Node *node);               //打印
    	void search(int number, Node *node);  //查找辅助函数
    
    	Node * create();                      //创建空节点
    };
    
    /*---析构函数---*/
    Tree::~Tree(){
        
    	destroy(root);
    }
    /*---摧毁节点---*/
    void Tree::destroy(Node *p){
        
    	if (p->leftChild)
    		destroy(p->leftChild);
    	if (p->rightChild)
    		destroy(p->rightChild);
    	delete p;
    }
    /*---创建空节点---*/
    Node * Tree::create(){
        
    	Node *p = new Node();
    
    	p->data = 0;
    	p->leftChild = NULL;
    	p->rightChild = NULL;
    
    	return p;
    }
    /*---生成二叉排序树---*/
    void Tree::one_BuildTree(){
        
    	vector <int> que;
    	int key, flag = 0;
    	cout << "Please input key to create Bsort_Tree(end with 0):" << endl;
    	cin >> key;
    	while (key != 0){
        
    		for (int i = 0; i < que.size(); i++){
        
    			if (que[i] == key){
        
    				cout << "The input key<" << key << "> is have in!" << endl;
    				flag = 1;
    				break;
    			}
    		}
    		if (!flag)
    			que.push_back(key);
    		flag = 0;
    		cin >> key;
    	}
    
    	root = create();
    	if (!root){
        
    		cout << "内存分配失败！" << endl;
    		return;
    	}
    	root->data = que[0];
    
    	for (int i = 1; i < que.size(); i++){
        
    		Node *p = create();
    		if (!p){
        
    			cout << "内存分配失败" << endl;
    			return;
    		}
    		p->data = que[i];
    		build(p, root);
    	}
    
    	cout << "Bsort_Tree is:" << endl;
    	Print(root);
    	cout << endl << endl;
    }
    /*---插入节点---*/
    void Tree::two_Insert(){
        
    	int num;
    	cout << "Please input  key which inserted: ";
    	cin >> num;
    
    	Node *p = create();
    	if (!p){
        
    		cout << "内存分配失败！" << endl;
    		return;
    	}
    	p->data = num;
    
    	build(p, root);
    
    	cout << "Bsort_Tree is:" << endl;
    	Print(root);
    	cout << endl << endl;
    }
    /*---查找节点---*/
    void Tree::three_Find(){
        
    	int num;
    	cout << "Please input key which searched: ";
    	cin >> num;
    
    	search(num, root);
    }
    /*---生成二叉树辅助函数---*/
    void Tree::build(Node *p, Node *current){
        
    	if (p->data > current->data){
        
    		if (!current->rightChild){
        
    			current->rightChild = p;
    			return;
    		}
    		build(p, current->rightChild);
    	}
    	if (p->data < current->data){
        
    		if (!current->leftChild){
        
    			current->leftChild = p;
    			return;
    		}
    		build(p, current->leftChild);
    	}
    	if (p->data == current->data)
    		cout << p->data << " have in！";
    }
    /*---打印---*/
    void Tree::Print(Node *node){
        
    	Node *p = node;
    	if (p->leftChild)
    		Print(p->leftChild);
    	cout << p->data << " -> ";
    	if (p->rightChild)
    		Print(p->rightChild);
    }
    /*---查找辅助函数---*/
    void Tree::search(int number, Node *node){
        
    
    	if (number < node->data){
        
    		if (!node->leftChild){
        
    			cout << number << " is not exist!" << endl;
    			return;
    		}
    		search(number, node->leftChild);
    	}
    	if (number > node->data){
        
    		if (!node->rightChild){
        
    			cout << number << " is not exist!" << endl;
    			return;
    		}
    		search(number, node->rightChild);
    	}
    	if (number == node->data){
        
    		cout << number << " is exist." << endl;
    		if (node->leftChild)
    			cout << "It's leftChild is " << node->leftChild->data << endl;
    		if (node->rightChild)
    			cout << "It's rightChild is " << node->rightChild->data << endl;
    	}
    }
    
    int main(){
        
    	cout << "**                           二叉排序树                           **" << endl;
    	cout << "====================================================================" << endl;
    	cout << "**                         1 --- 建立二叉排序树                   **" << endl;
    	cout << "**                         2 --- 插入元素                         **" << endl;
    	cout << "**                         3 --- 查询元素                         **" << endl;
    	cout << "**                         4 --- 退出程序                         **" << endl;
    	cout << "====================================================================" << endl;
    	
    }

![在这里插入图片描述][a82a543bf3f746248d594589ef8815e3.png_pic_center]  
![在这里插入图片描述][9ff7d3623ecb418886add730dda7304a.png_pic_center]  
![在这里插入图片描述][7c48cc187c8844d4a6e4a4cb81e5610f.png_pic_center]  
![在这里插入图片描述][9ed92dc3ce7b421ba25d044308deaaeb.png_pic_center]  
![在这里插入图片描述][354530af75ba439d9397fb41c6b42091.png_pic_center]  
![在这里插入图片描述][718de15c6f2e495da9211135c93b1b08.png_pic_center]  
![在这里插入图片描述][2cf6452ca6124cf89817d05cb2db93d3.png_pic_center]  
![在这里插入图片描述][91f15ec5f230479894c8d5a7743b6f26.png_pic_center]

[a82a543bf3f746248d594589ef8815e3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/5347dc142bf548c1872311199ff5cde4.png
[9ff7d3623ecb418886add730dda7304a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e259788e800d4863849265e61a1a349e.png
[7c48cc187c8844d4a6e4a4cb81e5610f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4544a5cb3bbd466db4eb0312f342ec60.png
[9ed92dc3ce7b421ba25d044308deaaeb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e6ea8aeec438424896464d20d3cf116d.png
[354530af75ba439d9397fb41c6b42091.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7b254cd02246490687d0f7bf00844e34.png
[718de15c6f2e495da9211135c93b1b08.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8baacf24ef63422b92bf78048f61805d.png
[2cf6452ca6124cf89817d05cb2db93d3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/702c4caa6abb4a0893422430b2534d51.png
[91f15ec5f230479894c8d5a7743b6f26.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f72725c573cf4e0c871649be68dc6fdf.png