第1关:二叉排序树的定义、查找和构造
任务描述
本关任务:按要求构造二叉排序树。
测试说明
平台会对你编写的代码进行测试:
测试输入:
1 10 21 33 44 55
预期输出:
55
说明:输入的是待构造成二叉排序树的数组array(长度固定为6),输出的是构造好的二叉排序树最右下方的叶子节点。
该例子最终构造的二叉排序树应该是下面这个样子:
代码如下
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//二叉树的定义
typedef struct BinaryNode {
int data;//数据
int index;//在数组中的位置
struct BinaryNode* leftChild, * rightChild;//左子树和右子树
}BinaryNode, * BinaryTree;
//创建二叉排序树
//tree:待构造的二叉树
//array:顺序表
//start:本次操作创建的子树在顺序表中的起始索引
//end:本次操作创建的子树在顺序表中的结束索引
void createBinarySortTree(BinaryTree tree, int array[], int start, int end) {
/********* Begin *********/
//从start到end中随机找一个数字作为根节点的索引
int rootIndex = start == end ? start : (rand() % (end - start) + start);
//对树根赋值
tree->data = array[rootIndex];
/********* End *********/
tree->index = rootIndex;
//当左子树中元素个数大于1
if (start < rootIndex) {
//给左子树分配空间
tree->leftChild = (BinaryTree)malloc(sizeof(BinaryNode));
//递归调用,生成左子树
createBinarySortTree(tree->leftChild, array, start, rootIndex - 1);
}
else {
//左子树中已经没有元素
tree->leftChild = NULL;
}
//当右子树中元素个数大于1
if (rootIndex < end) {
//给右子树分配空间
tree->rightChild = (BinaryTree)malloc(sizeof(BinaryNode));
//递归调用,生成右子树
createBinarySortTree(tree->rightChild, array, rootIndex + 1, end);
}
else {
//右子树中已经没有元素
tree->rightChild = NULL;
}
return;
}
//主函数
int main() {
//顺序表
int array[6];
for (int i = 0; i < 6; i++) {
scanf("%d", &array[i]);
}
//顺序表构造的次优静态查找树
BinaryTree tree = (BinaryTree)malloc(sizeof(BinaryNode));
//构造次优静态查找树
createBinarySortTree(tree, array, 0, 5);
printf("%d\n", tree->rightChild->rightChild->data);
return 0;
}
第2关:二叉排序树的插入
任务描述
本关任务:按照要求修改相关知识中的代码。
测试说明
平台会对你编写的代码进行测试:
测试输入:
100 0 89 100 89 20 21
预期输出:
-1
-1
-1
0
1
-1
-1
说明:输入的是待构造成二叉排序树的数组array(长度固定为7),输出的每一行中,如果是-1,表示该行对应的元素在插入之前,在二叉树中不存在,否则这个值表示的是已有的元素在array中的位置。
代码如下
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//二叉树的定义
typedef struct BinaryNode {
int data;//数据
int index;//在数组中的位置
struct BinaryNode* leftChild, * rightChild;//左子树和右子树
}BinaryNode, * BinaryTree;
//初始化二叉树
void initBinaryTree(BinaryTree tree) {
tree->data = -1;
tree->index = -1;
tree->leftChild = NULL;
tree->rightChild = NULL;
}
//创建二叉排序树
//tree:待构造的二叉树
//target:待插入的元素
//index:待插入元素在数组中的索引
int binaryTreeInsert(BinaryTree tree, int target, int index) {
if (tree->data == -1) {
tree->data = target;
tree->index = index;
return -1;
}
else {
if (target > tree->data) {
//待插入元素大于当前子树的根节点,进入右子树
if (tree->rightChild == NULL) {
//如果右子树不存在,构建右子树
tree->rightChild = (BinaryTree)malloc(sizeof(BinaryNode));
//初始化右子树
initBinaryTree(tree->rightChild);
}
//递归插入右子树中
return binaryTreeInsert(tree->rightChild, target, index);
}
else if (target < tree->data){
/********* Begin *********/
if (tree->leftChild == NULL) {
//如果左子树不存在,构建左子树
tree->leftChild = (BinaryTree)malloc(sizeof(BinaryNode));
//初始化右子树
initBinaryTree(tree->leftChild);
}
//递归插入右子树中
return binaryTreeInsert(tree->leftChild, target, index);
/********* End *********/
}
else {
/********* Begin *********/
return tree->index;
/********* End *********/
}
}
}
//主函数
int main() {
int array[7];
for (int i = 0; i < 7; i++) {
scanf("%d", &array[i]);
}
BinaryTree tree = (BinaryTree)malloc(sizeof(BinaryNode));;
initBinaryTree(tree);
for (int i = 0; i < 7; i++) {
printf("%d\n", binaryTreeInsert(tree, array[i], i));
}
return 0;
}
第3关:二叉排序树的删除
任务描述
本关任务:按照要求完成“删除左右子树都不为空的节点”这个函数
测试说明
平台会对你编写的代码进行测试,我们将删除在”删除的三种情况”中介绍的第三种情况的二叉树的某个节点,然后中序遍历该二叉树,打印出遍历结果。
测试输入:
112
预期输出:
100 102 105 108 120
说明:输入的是待删除节点,输入是删除后中序遍历二叉树的结果。
代码如下
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
//二叉树的定义
typedef struct BinaryNode {
int data;//数据
int index;//在数组中的位置
struct BinaryNode* leftChild, * rightChild;//左子树和右子树
}BinaryNode, * BinaryTree;
//初始化二叉树
void initTree(BinaryTree tree, int data) {
tree->data = data;
tree->leftChild = NULL;
tree->rightChild = NULL;
}
//查找指定节点的前驱节点以及前驱节点的父节点
//tree:待查找的节点
//preParentNode:待查找的节点的前驱节点的父节点
//返回待查找的节点的前驱节点
BinaryTree searchPreNode(BinaryTree tree, BinaryTree *preParentNode) {
//初始的时候,父节点就是待查找的节点
*preParentNode = tree;
//进入左子树
BinaryTree preNode = tree->leftChild;
//循环遍历右子树,直到走到空节点
while (preNode->rightChild != NULL) {
//在进入右子树之前,记录下父节点
*preParentNode = preNode;
//进入右子树
preNode = preNode->rightChild;
}
return preNode;
}
//根据值找节点
//tree:查找树
//target:目标节点的值
//parentNode:目标节点的父节点
//返回目标节点
BinaryTree searchNode(BinaryTree tree, int target, BinaryTree *parentNode) {
if (tree->data == target) {
return tree;
}
//目标值大于根节点的值,进入右子树
else if (tree->data < target) {
*parentNode = tree;
//递归查找
return searchNode(tree->rightChild, target, parentNode);
}
//目标值大于根节点的值,进入左子树
else {
*parentNode = tree;
//递归查找
return searchNode(tree->leftChild, target, parentNode);
}
}
//删除左右子树都为空的节点
void deleteBothEmpty(BinaryTree parentNode, int target) {
//如果节点是父节点的左子树的根,则将父节点的左子树清空
if (parentNode->leftChild != NULL && parentNode->leftChild->data == target) {
parentNode->leftChild = NULL;
}
//如果节点是父节点的右子树的根,则将父节点的右子树清空
else {
parentNode->rightChild = NULL;
}
}
//删除左右子树只有一个为空的节点
void deleteOneEmpty(BinaryTree targetNode, BinaryTree parentNode, int target) {
//被删除节点是父节点的左子树
if (parentNode->leftChild != NULL && parentNode->leftChild->data == target) {
//将被删除节点的左子树挂到父节点的左子树上
if (targetNode->leftChild != NULL) {
parentNode->leftChild = targetNode->leftChild;
}
//将被删除节点的右子树挂到父节点的左子树上
else {
parentNode->leftChild = targetNode->rightChild;
}
}
//被删除节点是父节点的右子树
else {
//将被删除节点的左子树挂到父节点的右子树上
if (targetNode->leftChild != NULL) {
parentNode->rightChild = targetNode->leftChild;
}
//将被删除节点的右子树挂到父节点的右子树上
else {
parentNode->rightChild = targetNode->rightChild;
}
}
}
//删除左右子树都不为空的节点
void deleteNotEmpty(BinaryTree targetNode, BinaryTree parentNode, int target) {
//前驱节点的父节点的初始值
BinaryTree preParentNode = targetNode;
//找到前驱节点以及前驱节点的父节点
BinaryTree preNode = searchPreNode(targetNode, &preParentNode);
//先删除前驱节点和整棵树的连接
deleteOneEmpty(preNode, preParentNode, preNode->data);
//然后用前驱节点替代当前节点
//替代的第一步是更换父节点的指针
//替代的第二步是将子节点挂到前驱节点上
//代码未给出,作为练习
/********* Begin *********/
targetNode->data = preNode->data;
/********* End *********/
}
void binaryTreeDelete(BinaryTree tree, int target) {
//待删除元素的父节点
BinaryTree parentNode = tree;
//首先找到待删除的元素所在的节点以及父节点
BinaryTree targetNode = searchNode(tree, target, &parentNode);
if (targetNode->leftChild == NULL && targetNode->rightChild == NULL) {
deleteBothEmpty(parentNode, target);
}
//如果这个节点没有左子树,或者没有右子树
else if (targetNode->leftChild == NULL || targetNode->rightChild == NULL) {
deleteOneEmpty(targetNode, parentNode, target);
}
else {
deleteNotEmpty(targetNode, parentNode, target);
}
}
void middleSearch(BinaryTree rootTree) {
if (rootTree->leftChild != NULL) {
middleSearch(rootTree->leftChild);
}
printf("%d ", rootTree->data);
if (rootTree->rightChild != NULL) {
middleSearch(rootTree->rightChild);
}
}
//主函数
int main() {
BinaryTree rootTree = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(rootTree, 100);
BinaryTree rightRootTree = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(rightRootTree, 112);
BinaryTree tree3 = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(tree3, 102);
BinaryTree tree4 = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(tree4, 120);
BinaryTree tree5 = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(tree5, 108);
BinaryTree tree6 = (BinaryTree)malloc(sizeof(BinaryNode));
initTree(tree6, 105);
//构建二叉树
rootTree->rightChild = rightRootTree;
rightRootTree->leftChild = tree3;
rightRootTree->rightChild = tree4;
tree3->rightChild = tree5;
tree5->leftChild = tree6;
//删除节点
int deleteNum;
scanf("%d", &deleteNum);
binaryTreeDelete(rootTree, deleteNum);
middleSearch(rootTree);
return 0;
}
第4关:平衡二叉树
任务描述
本关任务:完成右旋操作的代码。
编程要求
根据提示,在右侧编辑器Begin和End之间补充代码,完成右旋操作,请参考左旋操作的代码。
测试说明
平台会对你编写的代码进行测试:
测试输入:
100 112 120 105 108 102
预期输出:
1
说明:输入的是待构造成二叉平衡树树的数组array(长度固定为6),输出表示这颗二叉树是否是平衡二叉树,其中1表示是,0表示否。
代码如下
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//二叉树的定义
typedef struct BinaryNode {
int data;//数据
int balance;//节点的平衡因子
struct BinaryNode* leftChild, * rightChild;//左子树和右子树
}BinaryNode, * BinaryTree;
//左旋转
//对以p为根结点的树左旋,同时使得p指针指向新的根结点
void leftRotate(BinaryTree* p)
{
//右节点,新的树根节点
BinaryTree rightNode = (*p)->rightChild;
//原来的根的右节点,是新根的左节点
(*p)->rightChild = rightNode->leftChild;
rightNode->leftChild = *p;
*p = rightNode;
}
//右旋转
//对以p为根结点的树右旋,同时使得p指针指向新的根结点
void rightRotate(BinaryTree* p)
{
/********* Begin *********/
BinaryTree leftNode = (*p)->leftChild;
//原来的根的右节点,是新根的左节点
(*p)->leftChild = leftNode->rightChild;
leftNode->rightChild = *p;
*p = leftNode;
/********* End *********/
}
//左子树比右子树的高度大2
void balanceLeftTree(BinaryTree* tree)
{
//左子树,左子树的右子树
BinaryTree leftNode, leftRightNode;
//左子树赋值
leftNode = (*tree)->leftChild;
//如果左子树的左子树比右子树高1,说明是新节点是插入在了左子树的左子树上
if (leftNode->balance == 1) {
(*tree)->balance = leftNode->balance = 0;
//对整个书右旋即可
rightRotate(tree);
}
//如果左子树的左子树比右子树矮1,说明是新节点是插入在了左子树的右子树上
if (leftNode->balance == -1) {
leftRightNode = leftNode->rightChild;
if (leftRightNode->balance == 1) {
(*tree)->balance = -1;
leftNode->balance = 0;
}
else if (leftRightNode->balance == -1) {
(*tree)->balance = 0;
leftNode->balance = 1;
}
else {
(*tree)->balance = leftNode->balance = 0;
}
leftRightNode->balance = 0;
//对左子树进行左旋,并将tree调整为左旋完成后左子树的根节点
leftRotate(&(*tree)->leftChild);
//右旋
rightRotate(tree);
}
}
//RR旋转
//右子树的平衡处理同左子树的平衡处理完全类似
void balanceRightTree(BinaryTree* tree)
{
BinaryTree leftNode, leftLeftNode;
leftNode = (*tree)->rightChild;
if (leftNode->balance == -1) {
(*tree)->balance = leftNode->balance = 0;
leftRotate(tree);
}
if (leftNode->balance == 1) {
leftLeftNode = leftNode->leftChild;
if (leftLeftNode->balance == 1) {
(*tree)->balance = 0;
leftNode->balance = -1;
}
else if (leftLeftNode->balance == 0) {
(*tree)->balance = leftNode->balance = 0;
}
else {
(*tree)->balance = 0;
leftNode->balance = 1;
}
leftLeftNode->balance = 0;
rightRotate(&(*tree)->rightChild);
leftRotate(tree);
}
}
insertAVLTree(BinaryTree* tree, int data, int* isTaller)
{
//如果是空树,则新建
if ((*tree) == NULL)
{
//分配空间
(*tree) = (BinaryTree)malloc(sizeof(BinaryNode));
//初始化平衡因子为0
(*tree)->balance = 0;
//初始化数据
(*tree)->data = data;
(*tree)->leftChild = NULL;
(*tree)->rightChild = NULL;
//树的高度增加了
*isTaller = 1;
}
//如果待插入的数据小于根节点的数据
else if (data < (*tree)->data)
{
//插入到左子树中
insertAVLTree(&(*tree)->leftChild, data, isTaller);
//如果插入使得左子树变高
if (*isTaller)
{
//如果本来左子树就比右子树高1,则现在左子树比右子树高2
if ((*tree)->balance == 1) {
//需要对整个树进行平衡调整(左旋和先左旋再右旋)
balanceLeftTree(tree);
//树高度不变(平衡之前树的高度比原来大了1,平衡之后又恢复了)
*isTaller = 0;
}
//如果本来左子树和右子树一样高,则现在左子树比右子树高1
else if ((*tree)->balance == 0) {
//平衡因子加1
(*tree)->balance = 1;
//树高度增加
*isTaller = 1;
}
//如果本来左子树就比右子树矮1
else {
//平衡因子变为0
(*tree)->balance = 0;
//树高度不变
*isTaller = 0;
}
}
}
//和上面完全对称
else
{
insertAVLTree(&(*tree)->rightChild, data, isTaller);
if (*isTaller)
{
if ((*tree)->balance == 1) {
(*tree)->balance = 0;
*isTaller = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->balance = -1;
*isTaller = 1;
}
else {
balanceRightTree(tree);
*isTaller = 0;
}
}
}
}
void middleSearch(BinaryTree rootTree) {
if (rootTree->leftChild != NULL) {
middleSearch(rootTree->leftChild);
}
printf("%d ", rootTree->data);
if (rootTree->rightChild != NULL) {
middleSearch(rootTree->rightChild);
}
}
//求树高
int getTreeHeight(BinaryTree tree) {
if (tree == NULL) {
return 0;
}
else {
int leftHeight = getTreeHeight(tree->leftChild);
int rightHeight = getTreeHeight(tree->rightChild);
int res = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
return res;
}
}
//是否是AVL树
//0否1是
int isAVLTree(BinaryTree tree) {
if (tree == NULL) {
return 1;
}
int leftHeight = getTreeHeight(tree->leftChild);
int rightHeight = getTreeHeight(tree->rightChild);
if (1 >= abs(leftHeight - rightHeight) && isAVLTree(tree->leftChild) && isAVLTree(tree->rightChild)) {
return 1;
}
return 0;
}
int main()
{
//数组
int array[6];
for (int i = 0; i < 6; i++)
{
scanf("%d", &array[i]);
}
//树的根节点
BinaryTree tree = NULL;
//树在插入完成之后是否增高了,1是0否
int isTaller;
//构建AVL树
for (int i = 0; i < 6; i++)
{
insertAVLTree(&tree, array[i], &isTaller);
}
printf("%d\n", isAVLTree(tree));
}