介绍

对于二叉搜索树的查找指定元素、查找最大元素、查找最小元素、删除指定元素、插入元素等基础操作。除了删除操作外，基本上都是使用的非递归函数解决。

Code

#include<stdio.h>
#include<stdlib.h>
// 二叉搜索树的各种操作 By Titan

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode {
  int Data;
  Position Left;
  Position Right;
};

//插入操作
BinTree Insert(BinTree BST,int X) {
  if(!BST) {
    BST = (BinTree)malloc(sizeof(struct TNode));
    BST->Data=X;
    BST->Left=BST->Right=NULL;
  } else {
    BinTree Parent,Cur=BST;
    while(Cur) {
      Parent=Cur;
      if(Cur->Data > X) {
        Cur=Cur->Left;
      } else if(Cur->Data < X) {
        Cur=Cur->Right;
      } else {
        return BST;
      }
    }
    BinTree TempNode = (BinTree)malloc(sizeof(struct TNode));
    TempNode->Data=X;
    TempNode->Left=TempNode->Right=NULL;
    if(Parent->Data>X) {
      Parent->Left=TempNode;
    } else {
      Parent->Right=TempNode;
    }
  }
  return BST;
}
//查找操作
//基础查找
BinTree Find(BinTree BST,int X) {
  if(!BST) {
    return NULL;
  }
  BinTree Found=NULL;
  while(BST) {
    if(BST->Data > X ) {
      BST=BST->Left;
    } else if(BST->Data < X) {
      BST=BST->Right;
    } else if(BST->Data == X) {
      Found=BST;
      break;
    }
  }
  return Found;
}
//找最小值
BinTree FindMin(BinTree BST) {
  if(!BST) {
    return NULL;
  }
  while(BST->Left) {
    BST=BST->Left;
  }
  return BST;
}
//找最大值
BinTree FindMax(BinTree BST) {
  if(!BST) {
    return NULL;
  }
  while(BST->Right) {
    BST=BST->Right;
  }
  return BST;
}

// 删除操作
BinTree Delete(BinTree BST,int X) {
  Position Tmp;
  if( !BST ) {
    printf("Not Found\n");
  } else {
    if( X < BST->Data ) {
      BST->Left = Delete( BST->Left, X );
    } else if( X > BST->Data ) {
      BST->Right = Delete( BST->Right, X );
    } else {
      if( BST->Left && BST->Right ) {
        Tmp = FindMin( BST->Right );
        BST->Data = Tmp->Data;
        BST->Right = Delete( BST->Right, BST->Data );
      } else {
        if( !BST->Left ) {
          BST = BST->Right;
        } else {
          BST = BST->Left;
        }
      }
    }
  }
  return BST;
}

//先序遍历
void preOrder(BinTree BST) {
  if(BST) {
    printf("%d ",BST->Data);
    preOrder(BST->Left);
    preOrder(BST->Right);
  }
}


int main(void) {
  int n,tempX;
  BinTree BST=NULL;
  // 数据读入,建立二叉树
  scanf("%d",&n);
  for(int i=0; i<n; i++) {
    scanf("%d",&tempX);
    BST = Insert(BST,tempX);
  }
  // 先序遍历
  preOrder(BST);
  printf("\n");
  // 寻找某个元素
  int toFind;
  printf("请输入要查找的元素:");
  scanf("%d",&toFind);
  BinTree FoundNode = Find(BST,toFind);
  if(FoundNode) {
    printf("%d is Found.\n",toFind,FoundNode);
  } else {
    printf("%d Not Found!\n",toFind);
  }
  // 寻找最大值
  BinTree FoundMax=FindMax(BST);
  if(FoundMax) {
    printf("Max: %d.\n",FoundMax->Data,FoundMax);
  } else {
    printf("Find Max ERROR!\n");
  }
  // 寻找最小值
  BinTree FoundMin=FindMin(BST);
  if(FoundMin) {
    printf("Min: %d.\n",FoundMin->Data,FoundMin);
  } else {
    printf("Find Min ERROR!\n");
  }
  // 删除元素
  int target;
  printf("请输入要删除的元素: ");
  scanf("%d",&target);
  BST = Delete(BST,target);
  preOrder(BST);


}