C++数据结构——习题7-2 二叉排序树

  • A+
所属分类:C/C++ 笔记

HLOJ 9576,习题7-2 二叉排序树

输入一个整数关键字序列,生成一棵用链式存储结构存储的二叉排序树,对该二叉排序树能进行查找和插入结点的操作,并对该二叉排序树中结点的关键字按递增和递减顺序输出。
要求依次完成以下工作:
(1) 以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树;
(2) 按递增顺序输出该二叉排序树中的整数(关键字); (3) 输入一个整数key1,对该二叉排序树进行查找,给出“find”(找到)或“not find”(没找到)的信息;
(4) 输入一个整数key2,若该二叉排序树中不存在整数key2,则将key2插入到该二叉排序树中(插入后仍为二叉排序树);否则不必插入;
(5)在(4)的基础上,按递减顺序输出该二叉排序树中的整数(关键字)。

输入格式:

首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据第一行输入正整数n(5≤n≤20),第二行输入n个整数,第三行输入整数key1,第四行输入整数key2。

输出格式:

对于每组测试,输出三行,第一行按递增顺序输出该二叉排序树中的整数(关键字),每两个整数之间留一个空格;第二行,输出“find”或“not find”分别表示是否找到关键字key1;第三行按递减顺序输出该二叉排序树中的整数(关键字),每两个整数之间留一个空格。

输入样例:
2
8
10 79 6 81 43 75 26 69
43
69
10
94 22 25 24 20 42 39 71 53 57
88
1
输出样例:
6 10 26 43 69 75 79 81
find
81 79 75 69 43 26 10 6
20 22 24 25 39 42 53 57 71 94
not find
94 71 57 53 42 39 25 24 22 20 1

代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

解题代码

#include<bits/stdc++.h>
using namespace std;
template<class T>
struct treeNode{
   
	T data;
	treeNode *L_child,*R_child;
};
int flag; //用来判断是不是第一个输出 
template<class T>
class Tree{
   
	public:
		//构造函数 
		Tree(){
   
			this->root=NULL;	
		};
		//创建树 
		void createTree(treeNode<T> *&root,T data){
   
			if(root==NULL){
   
				//cout<<"root:"<<data<<endl;
				root=new treeNode<T>();
				root->data=data;
				root->L_child=root->R_child=NULL;
				return;
			}else if(data<root->data){
   
				createTree(root->L_child,data);
			}else{
   
				createTree(root->R_child,data);
			}
		};
		//返回私有成员root 
		treeNode<T>* getRoot(){
   
			return this->root;
		};
		//按递增顺序输出该二叉排序树中的整数
		void findByAsc(treeNode<T> *root){
   
			if(root==NULL) return;
			findByAsc(root->L_child);
			if(flag==1){
   
				cout<<root->data;
				flag=0;
			}else{
   
				cout<<" "<<root->data;
			}
			
			findByAsc(root->R_child);
		};
		
		//输入一个整数key1,对该二叉排序树进行查找,给出“find”(找到)或“not find”(没找到)的信息
		//这里也是有可能会修改树,所以需要传一个引用参数*& 
		bool findKey(treeNode<T> *root,T key){
   
			//cout<<"root->data:"<<root->data<<endl;
			if(root==NULL) return false;
			if(key==root->data){
   
				return true;
			}else if(key<root->data){
   
				return findKey(root->L_child,key);
			}else {
   
				return findKey(root->R_child,key);
			}
			return false;
		};
		//输入一个整数key2,若该二叉排序树中不存在整数key2,则将key2插入到该二叉排序树中(插入后仍为二叉排序树);否则不必插入
		void findOrInsert(treeNode<T> *&root,T key){
   
			
			if(root==NULL){
   
				root= new treeNode<T>();
				root->data=key;
				root->L_child=root->R_child=NULL;
				return;
			}else if(root->data==key){
   
				return;
			}else if(root->data>key){
   
				findOrInsert(root->L_child,key);
			}else {
   
				findOrInsert(root->R_child,key);
			}
		};
		//在(4)的基础上,按递减顺序输出该二叉排序树中的整数
		void findByDesc(treeNode<T> *root){
   
			if(root==NULL) return;
			findByDesc(root->R_child);
			if(flag==1){
   
				cout<<root->data;
				flag=0;
			}else{
   
				cout<<" "<<root->data;
			}
			findByDesc(root->L_child);
		};
	private:
		treeNode<T> *root;	
	
};

int main()
{
   
	int n,m,num,key;

	cin>>n;
	while(n--){
   
		Tree<int> *tree = new Tree<int>();
		treeNode<int> *root=tree->getRoot();
		cin>>m;
		for(int i=0;i<m;i++){
   
			cin>>num;
			tree->createTree(root,num);
		}
		flag = 1;
		tree->findByAsc(root);
		cout<<endl; 
		cin>>key;
		if(tree->findKey(root,key)){
   
			cout<<"find"<<endl;
		}else{
   
			cout<<"not find"<<endl;
		}
		cin>>key;
		tree->findOrInsert(root,key);
		flag = 1;
		tree->findByDesc(root);
		cout<<endl;
	}
}

解题思路
写了一个模板类,二叉排序树就是二叉搜索树,将值小于根节点的的放在左子树,值大的放在右子树。
我写了一个模板类,每输入一个值,就遍历插入结点,void createTree(treeNode *&root,T data)函数不能只传root指针,因为我们要创建插入结点,那么就会更改值,所以这里要传引用参数*&。递增和递减遍历无非就是从左边或者从右边遍历,左子树先遍历就是递增,因为左子树必然比根节点要小,同理右子树必然比根节点要大。
关于查找就递归查找,然后如果找不到就插入其实很好理解,我们找一个树,因为是左小右大,那么任何一边递归查找时根节点为NULL那么可以断定,这棵树上没有找到我们的结点,那么创建一个结点就行,同样要传引用参数。

w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: