#include <stdio.h>
#define QUEUE_MAX_SIZE 20
#define STACK_MAX_SIZE 10
typedef int elemType;
#include "BT.c"
/************************************************************************/
/* 以下是关于二叉搜索树操作的4个简单算法 */
/************************************************************************/
/* 1.查找 */
/* 递归算法 */
elemType *findBSTree1(struct BTreeNode *bst, elemType x)
{
/* 树为空则返回NULL */
if (bst == NULL){
return NULL;
}else{
if (x == bst->data){
return &(bst->data);
}else{
if (x < bst->data){ /* 向左子树查找并直接返回 */
return findBSTree1(bst->left, x);
}else{ /* 向右子树查找并直接返回 */
return findBSTree1(bst->right, x);
}
}
}
}
/* 非递归算法 */
elemType *findBSTree2(struct BTreeNode *bst, elemType x)
{
while (bst != NULL){
if (x == bst->data){
return &(bst->data);
}else if (x < bst->data){
bst = bst->left;
}else{
bst = bst->right;
}
}
return NULL;
}
/* 2.插入 */
/* 递归算法 */
void insertBSTree1(struct BTreeNode* *bst, elemType x)
{
/* 新建一个根结点 */
if (*bst == NULL){
struct BTreeNode *p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = x;
p->left = p->right = NULL;
*bst = p;
return;
}else if (x < (*bst)->data){ /* 向左子树完成插入运算 */
insertBSTree1(&((*bst)->left), x);
}else{ /* 向右子树完成插入运算 */
insertBSTree1(&((*bst)->right), x);
}
}
/* 非递归算法 */
void insertBSTree2(struct BTreeNode* *bst, elemType x)
{
struct BTreeNode *p;
struct BTreeNode *t = *bst, *parent = NULL;
/* 为待插入的元素查找插入位置 */
while (t != NULL){
parent = t;
if (x < t->data){
t = t->left;
}else{
t = t->right;
}
}
/* 建立值为x，左右指针域为空的新结点 */
p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = x;
p->left = p->right = NULL;
/* 将新结点链接到指针为空的位置 */
if (parent == NULL){
*bst = p; /* 作为根结点插入 */
}else if (x < parent->data){ /* 链接到左指针域 */
parent->left = p;
}else{
parent->right = p;
}
return;
}
/* 3.建立 */
void createBSTree(struct BTreeNode* *bst, elemType a[], int n)
{
int i;
*bst = NULL;
for (i = 0; i < n; i++){
insertBSTree1(bst, a[i]);
}
return;
}
/* 4.删除值为x的结点，成功返回1,失败返回0 */
int deleteBSTree(struct BTreeNode* *bst, elemType x)
{
struct BTreeNode *temp = *bst;
if (*bst == NULL){
return 0;
}
if (x < (*bst)->data){
return deleteBSTree(&((*bst)->left), x); /* 向左子树递归 */
}
if (x > (*bst)->data){
return deleteBSTree(&((*bst)->right), x); /* 向右子树递归 */
}
/* 待删除的元素等于树根结点值且左子树为空，将右子树作为整个树并返回1 */
if ((*bst)->left == NULL){
*bst = (*bst)->right;
free(temp);
return 1;
}
/* 待删除的元素等于树根结点值且右子树为空，将左子树作为整个树并返回1 */
if ((*bst)->right == NULL){
*bst = (*bst)->left;
free(temp);
return 1;
}else{
/* 中序前驱结点为空时，把左孩子结点值赋给树根结点，然后从左子树中删除根结点 */
if ((*bst)->left->right == NULL){
(*bst)->data = (*bst)->left->data;
return deleteBSTree(&((*bst)->left), (*bst)->data);
}else{ /* 定位到中序前驱结点，把该结点值赋给树根结点，然后从以中序前驱结点为根的
树上删除根结点*/
struct BTreeNode *p1 = *bst, *p2 = p1->left;
while (p2->right != NULL){
p1 = p2;
p2 = p2->right;
}
(*bst)->data = p2->data;
return deleteBSTree(&(p1->right), p2->data);
}
}
}
/************************************************************************/
int main(int argc, char *argv[])
{
int x, *px;
elemType a[10] = {30, 50, 20, 40, 25, 70, 54, 23, 80, 92};
struct BTreeNode *bst = NULL;
createBSTree(&bst, a, 10);
printf("建立的二叉搜索树的广义表形式为： ");
printBTree(bst);
printf(" ");
printf("中序遍历： ");
inOrder(bst);
printf(" ");
printf("输入待查找元素的值：");
scanf(" %d", &x);
if (px = findBSTree1(bst, x)){
printf("查找成功！得到的x为：%d ", *px);
}else{
printf("查找失败！ ");
}
printf("输入待插入的元素值：");
scanf(" %d", &x);
insertBSTree1(&bst, x);
printf("输入待删除元素值：");
scanf(" %d", &x);
if (deleteBSTree(&bst, x)){
printf("1 ");
}else{
printf("0 ");
}
printf("进行相应操作后的中序遍历为： ");
inOrder(bst);
printf(" ");
printf("操作后的二叉搜索树的广义表的形式为： ");
printBTree(bst);
printf(" ");
clearBTree(&bst);
return 0;
}
查看本文来源
京公网安备 11010802021500号