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那么可以断定，这棵树上没有找到我们的结点，那么创建一个结点就行，同样要传引用参数。
