【刷题】算法设计题+程序设计题【2】2019-2024

11.20	2019年真题*2	BST二叉排序树分裂、双向冒泡排序

2019 真题

【2019 1】编写算法，将一棵二叉排序树 分解成两棵二叉排序树 t1和t2，使得t1中的所有结点关键字的值都小于x，t2中所有结点关键字都大于x。

typedef struct BSTNode{
int data;
struct BSTNode *left,*right;
}BSTNode;

void splitBST(BSTNode* t,int x, BSTNode *&A,BSTNode *&B){
if(t == NULL){
A = NULL;
B = NULL;
return ;
}
if(t->data <= x){
//当前结点属于A，且左子树都属于A
A = t;
//递归处理右子树
splitBST(t->right , x , A->right , B);
}else{
//当前节点属于B，且右子树都属于B
B = t;
//递归处理左子树，判断是否还有大于x的值
splitBST(t->left , x , A , B->left);
}
}

【2019 2】传统的冒泡排序始终从低位开始往高位索引方向扫描元素进行排序，但是有一种改进的冒泡排序既能从低位往高位扫描元素，也能从高位往低位双向扫描元素，请编写算法实现这种双向冒泡排序。

//默认是升序
void DoubleBubble(int arr[] , int n){
int begin = 0 , end = n-1;
while(begin < end){
//低位往高位，将大的往后
for(int i = begin ; i < end ; i++){
if(arr[i] > arr[i+1])
swap(arr[i] , arr[i+1]);
}
end--;
//高位往低位，将小的往前
for(int j = end; j > begin ; --j){
if(arr[j] < arr[j-1])
swap(arr[j] , arr[j-1]);
}
begin++;
}
}

原文地址：https://blog.csdn.net/emmm_Yeah/article/details/143925607

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！