二叉排序树和二叉平衡树

Source

第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));
}