介绍
对于二叉搜索树的查找指定元素、查找最大元素、查找最小元素、删除指定元素、插入元素等基础操作。除了删除操作外,基本上都是使用的非递归函数解决。
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); }
文章评论