目录
第2关：在二叉排序树中查找元素e及其存在情况exist,并返回所查找的次数.
第3关：在二叉排序树中删除元素e,若存在就删除它并返回true,否则返回false
第一关：从文件中读入数据创建二叉排序树
任务描述
本关任务：从文件中读入数据创建二叉排序树。
测试说明
当文件 bstDataChar.txt 内容如下时:
-
TvNVB1erdPFyiaKMQ80bJx2pUZflO3Ln
预期输出：
-
Char type
-
Create binary sort tree success!
-
Inorder traversal:
-
0,1,2,3,8,B,F,J,K,L,M,N,O,P,Q,T,U,V,Z,a,b,d,e,f,i,l,n,n,p,r,v,x,y,
-
Preorder traversal:
-
T,N,B,1,0,8,2,3,F,K,J,M,L,P,O,Q,v,V,U,e,d,a,Z,b,r,i,f,p,l,n,n,y,x,
当文件 bstDataChar.txt 内容如下时:
-
33 49 39 51 61 30 1 11 52 3 14 63 27 17
-
89 19 46 21 58 29 76
预期输出：
-
Int type
-
Create binary sort tree success!
-
Inorder traversal:
-
1,3,11,14,17,19,21,27,29,30,33,39,46,49,51,52,58,61,63,76,89,
-
Preorder traversal:
-
33,30,1,11,3,14,27,17,19,21,29,49,39,46,51,61,52,58,63,89,76,
#include "BinSortTree.h" /*********************************** * Copyright(c) 2016-2099 CTGU YOUNGMIEN * All rights reserved. * Version: v1.0 * Author: YOUNGMIEN * Date: 16/04/20 * Company: CTGU * * fileName: BinSortTree.cpp * Descripton: 任务文件 * *******************************/ /* Round 1 由文件生成二叉排序树 如文件数据如下: 18 14 7 3 11 22 35 27 生成BST中序遍历得到序列如下: 3,7,11,14,18,22,27,35, @param fileName:string, file name */ template <typename T> void BinSortTree<T>::createBSTFromFile(ifstream &ifs){ /*************** Begin ****************/ //ifstream ifs(fileName.c_str()); T e; if(ifs.good()){ ifs >> e; } mp_root = new BinTNode<T>(e); while(ifs.good()){ ifs >> e; insert(mp_root, e); } /*************** End ****************/ } // --- createBSTFromFile() END /*Round 1 === 在根为cur的二叉树中插入元素e */ template<typename T> void BinSortTree<T>:: insert(BinTNode<T> * cur, T e){ /*************** Begin ****************/ //生成新结点 BinTNode<T> * newNode = new BinTNode<T>(e); //循环查找,直到找到newNode要插入的位置 while(1) { //大则向左、小则向右 if(moreThan(newNode, cur)){ //newNode > cur if(cur->m_right != NULL){ cur = cur->m_right; } else{ //cur 没有 右孩子 //找到 cur->m_right = newNode; break; } } //newNode > cur END else{ //newNode <= cur if(cur->m_left != NULL){ cur = cur->m_left; } else{ //cur 没有 左孩子 //找到 cur->m_left = newNode; break; } } } /*************** End ****************/ }//insert() END /* Round 2 ===searchTimes:在根为start中查找元素e,返回查找的次数 @param start: 子树的根结点 @param e: 元素 @param exist:查找结果, true,存在;false,不存在 @return 查找所花费的次数 */ template<typename T> int BinSortTree<T>::searchTimes(BinTNode<T> * start, T e, bool &exist){ /*************** Begin ****************/ if(NULL == start ){ exist = false; return 1; } else if(!cmpType(start->m_data,e) ){ exist = true; return 1; } else if(cmpType(start->m_data, e) < 0){ return 1+searchTimes(start->m_right, e, exist); } else{ return 1+searchTimes(start->m_left, e, exist); } /*************** End ****************/ } /* Round 3 === 删除,在根为start中删除元素e,成功返回true否则为false @param start: BinTNode<T> * &,引用类型 @param e:T,element @return :true,树中存在该元素;false,不存在 */ template<typename T> bool BinSortTree<T>::removeFromBST(BinTNode<T> * & start, T e){ /*************** Begin ****************/ if(NULL == start){ return false; } else{ //查找 if( !cmpType(start->m_data,e) ){ delBSTNode(start); return true; } else if(cmpType(start->m_data,e) > 0){ return removeFromBST(start->m_left, e); } else{ return removeFromBST(start->m_right, e); } } /*************** End ****************/ } /*===在二叉排序树中删除cur删除结点 @param cur, BinTNode<T> * &,引用类型,写操作 */ template<typename T> void BinSortTree<T>:: delBSTNode(BinTNode<T> * & cur){ /*************** Begin ****************/ BinTNode<T> * tmp = cur; if(NULL == cur->m_left){ cur = cur->m_right; delete tmp; } else if(NULL == cur->m_right){ cur = cur->m_left; delete tmp; } else{ BinTNode<T> * start = cur; tmp = cur->m_left; while(tmp->m_right != NULL){ start = tmp; tmp = tmp->m_right; } cur->m_data = tmp->m_data; if(start != cur){ start->m_right = tmp->m_left; } else{ cur->m_left = tmp->m_left; } delete tmp; } /*************** End ****************/ }
第2关：在二叉排序树中查找元素e及其存在情况exist,并返回所查找的次数.
任务描述
本关任务：在二叉排序树中查找元素 e 及其存在情况 exist，并返回所查找的次数。
测试说明
平台会对你的代码进行测试。 文件 bstDataString.txt 内容如下：
-
bed bee add bad ebb cab dad be a art db
测试输入：
-
bed
预期输出：
-
String type
-
Create binary sort tree success!
-
Inorder traversal:
-
a,add,art,bad,be,bed,bee,cab,dad,db,db,ebb,
-
Preorder traversal:
-
bed,add,a,bad,art,be,bee,ebb,cab,dad,db,db,
-
Search an element at the tree,input key:
-
bed
-
Exist!The number of times to find this element is: 1
测试输入：
-
abc
预期输出：
-
String type
-
Create binary sort tree success!
-
Inorder traversal:
-
a,add,art,bad,be,bed,bee,cab,dad,db,db,ebb,
-
Preorder traversal:
-
bed,add,a,bad,art,be,bee,ebb,cab,dad,db,db,
-
Search an element at the tree,input key:
-
abc
-
Not exist!The number of times to find this element is: 4
#include "BinSortTree.h"
/***********************************
* Copyright(c) 2016-2099 CTGU YOUNGMIEN
* All rights reserved.
* Version: v1.0
* Author: YOUNGMIEN
* Date: 16/04/20
* Company: CTGU
*
* fileName: BinSortTree.cpp
* Descripton: 任务文件
*
*******************************/
/* Round 1
由文件生成二叉排序树
如文件数据如下:
18 14 7 3 11 22 35 27
生成BST中序遍历得到序列如下:
3,7,11,14,18,22,27,35,
@param fileName:string, file name
*/
template <typename T>
void BinSortTree<T>::createBSTFromFile(ifstream &ifs){
/*************** Begin ****************/
//ifstream ifs(fileName.c_str());
T e;
if(ifs.good()){
ifs >> e;
}
mp_root = new BinTNode<T>(e);
while(ifs.good()){
ifs >> e;
insert(mp_root, e);
}
/*************** End ****************/
} // --- createBSTFromFile() END
/*Round 1
=== 在根为cur的二叉树中插入元素e
*/
template<typename T>
void BinSortTree<T>:: insert(BinTNode<T> * cur, T e){
/*************** Begin ****************/
//生成新结点
BinTNode<T> * newNode = new BinTNode<T>(e);
//循环查找,直到找到newNode要插入的位置
while(1) { //大则向左、小则向右
if(moreThan(newNode, cur)){ //newNode > cur
if(cur->m_right != NULL){
cur = cur->m_right;
}
else{ //cur 没有 右孩子
//找到
cur->m_right = newNode;
break;
}
} //newNode > cur END
else{ //newNode <= cur
if(cur->m_left != NULL){
cur = cur->m_left;
}
else{ //cur 没有 左孩子
//找到
cur->m_left = newNode;
break;
}
}
}
/*************** End ****************/
}//insert() END
/* Round 2
===searchTimes:在根为start中查找元素e,返回查找的次数
@param start: 子树的根结点
@param e: 元素
@param exist:查找结果, true,存在;false,不存在
@return 查找所花费的次数
*/
template<typename T>
int BinSortTree<T>::searchTimes(BinTNode<T> * start, T e, bool &exist){
/*************** Begin ****************/
if(NULL == start ){
exist = false;
return 1;
}
else if(!cmpType(start->m_data,e) ){
exist = true;
return 1;
}
else if(cmpType(start->m_data, e) < 0){
return 1+searchTimes(start->m_right, e, exist);
}
else{
return 1+searchTimes(start->m_left, e, exist);
}
/*************** End ****************/
}
/* Round 3
=== 删除,在根为start中删除元素e,成功返回true否则为false
@param start: BinTNode<T> * &,引用类型
@param e:T,element
@return :true,树中存在该元素;false,不存在
*/
template<typename T>
bool BinSortTree<T>::removeFromBST(BinTNode<T> * & start, T e){
/*************** Begin ****************/
if(NULL == start){
return false;
}
else{
//查找
if( !cmpType(start->m_data,e) ){
delBSTNode(start);
return true;
}
else if(cmpType(start->m_data,e) > 0){
return removeFromBST(start->m_left, e);
}
else{
return removeFromBST(start->m_right, e);
}
}
/*************** End ****************/
}
/*===在二叉排序树中删除cur删除结点
@param cur, BinTNode<T> * &,引用类型,写操作
*/
template<typename T>
void BinSortTree<T>:: delBSTNode(BinTNode<T> * & cur){
/*************** Begin ****************/
BinTNode<T> * tmp = cur;
if(NULL == cur->m_left){
cur = cur->m_right;
delete tmp;
}
else if(NULL == cur->m_right){
cur = cur->m_left;
delete tmp;
}
else{
BinTNode<T> * start = cur;
tmp = cur->m_left;
while(tmp->m_right != NULL){
start = tmp;
tmp = tmp->m_right;
}
cur->m_data = tmp->m_data;
if(start != cur){
start->m_right = tmp->m_left;
}
else{
cur->m_left = tmp->m_left;
}
delete tmp;
}
/*************** End ****************/
}
第3关：在二叉排序树中删除元素e,若存在就删除它并返回true,否则返回false
任务描述
任务描述：在二叉排序树中删除元素 e，若存在就删除它并返回 true，否则返回 false。
测试说明
平台会对你的代码进行测试。 文件 bstDataString.txt 内容如下:
-
bed bee add bad ebb cab dad be a art db
测试输入：
-
add
预期输出：
-
String type
-
Create binary sort tree success!
-
Inorder traversal:
-
a,add,art,bad,be,bed,bee,cab,dad,db,db,ebb,
-
Preorder traversal:
-
bed,add,a,bad,art,be,bee,ebb,cab,dad,db,db,
-
Remove an element from the tree,input key:
-
add
-
add Exist,Delete element success!
-
After deleting
-
Inorder traversal:
-
a,art,bad,be,bed,bee,cab,dad,db,db,ebb,
-
Preorder traversal:
-
bed,a,bad,art,be,bee,ebb,cab,dad,db,db,
#include "BinSortTree.h"
/***********************************
* Copyright(c) 2016-2099 CTGU YOUNGMIEN
* All rights reserved.
* Version: v1.0
* Author: YOUNGMIEN
* Date: 16/04/20
* Company: CTGU
*
* fileName: BinSortTree.cpp
* Descripton: 任务文件
*
*******************************/
/* Round 1
由文件生成二叉排序树
如文件数据如下:
18 14 7 3 11 22 35 27
生成BST中序遍历得到序列如下:
3,7,11,14,18,22,27,35,
@param fileName:string, file name
*/
template <typename T>
void BinSortTree<T>::createBSTFromFile(ifstream &ifs){
/*************** Begin ****************/
//ifstream ifs(fileName.c_str());
T e;
if(ifs.good()){
ifs >> e;
}
mp_root = new BinTNode<T>(e);
while(ifs.good()){
ifs >> e;
insert(mp_root, e);
}
/*************** End ****************/
} // --- createBSTFromFile() END
/*Round 1
=== 在根为cur的二叉树中插入元素e
*/
template<typename T>
void BinSortTree<T>:: insert(BinTNode<T> * cur, T e){
/*************** Begin ****************/
//生成新结点
BinTNode<T> * newNode = new BinTNode<T>(e);
//循环查找,直到找到newNode要插入的位置
while(1) { //大则向左、小则向右
if(moreThan(newNode, cur)){ //newNode > cur
if(cur->m_right != NULL){
cur = cur->m_right;
}
else{ //cur 没有 右孩子
//找到
cur->m_right = newNode;
break;
}
} //newNode > cur END
else{ //newNode <= cur
if(cur->m_left != NULL){
cur = cur->m_left;
}
else{ //cur 没有 左孩子
//找到
cur->m_left = newNode;
break;
}
}
}
/*************** End ****************/
}//insert() END
/* Round 2
===searchTimes:在根为start中查找元素e,返回查找的次数
@param start: 子树的根结点
@param e: 元素
@param exist:查找结果, true,存在;false,不存在
@return 查找所花费的次数
*/
template<typename T>
int BinSortTree<T>::searchTimes(BinTNode<T> * start, T e, bool &exist){
/*************** Begin ****************/
if(NULL == start ){
exist = false;
return 1;
}
else if(!cmpType(start->m_data,e) ){
exist = true;
return 1;
}
else if(cmpType(start->m_data, e) < 0){
return 1+searchTimes(start->m_right, e, exist);
}
else{
return 1+searchTimes(start->m_left, e, exist);
}
/*************** End ****************/
}
/* Round 3
=== 删除,在根为start中删除元素e,成功返回true否则为false
@param start: BinTNode<T> * &,引用类型
@param e:T,element
@return :true,树中存在该元素;false,不存在
*/
template<typename T>
bool BinSortTree<T>::removeFromBST(BinTNode<T> * & start, T e){
/*************** Begin ****************/
if(NULL == start){
return false;
}
else{
//查找
if( !cmpType(start->m_data,e) ){
delBSTNode(start);
return true;
}
else if(cmpType(start->m_data,e) > 0){
return removeFromBST(start->m_left, e);
}
else{
return removeFromBST(start->m_right, e);
}
}
/*************** End ****************/
}
/*===在二叉排序树中删除cur删除结点
@param cur, BinTNode<T> * &,引用类型,写操作
*/
template<typename T>
void BinSortTree<T>:: delBSTNode(BinTNode<T> * & cur){
/*************** Begin ****************/
BinTNode<T> * tmp = cur;
if(NULL == cur->m_left){
cur = cur->m_right;
delete tmp;
}
else if(NULL == cur->m_right){
cur = cur->m_left;
delete tmp;
}
else{
BinTNode<T> * start = cur;
tmp = cur->m_left;
while(tmp->m_right != NULL){
start = tmp;
tmp = tmp->m_right;
}
cur->m_data = tmp->m_data;
if(start != cur){
start->m_right = tmp->m_left;
}
else{
cur->m_left = tmp->m_left;
}
delete tmp;
}
/*************** End ****************/
}
版权声明：本文为weixin_63423226原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。