PTA 6-12 二叉搜索树的操作集

本题要求实现给定二叉搜索树的5种常用操作。函数接口定义BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X ); Position FindMin( BinTree BST ); Position FindMax( BinTree BST );函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针函数Delete将X从二叉搜索树BST中删除并返回结果树的根结点指针如果X不在树中则打印一行Not Found并返回原树的根结点指针函数Find在二叉搜索树BST中找到X返回该结点的指针如果找不到则返回空指针函数FindMin返回二叉搜索树BST中最小元结点的指针函数FindMax返回二叉搜索树BST中最大元结点的指针。其中BinTree结构定义如下typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };裁判测试程序样例#include stdio.h #include stdlib.h typedef int ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; void PreorderTraversal( BinTree BT ); /* 先序遍历由裁判实现细节不表 */ void InorderTraversal( BinTree BT ); /* 中序遍历由裁判实现细节不表 */ BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X ); Position FindMin( BinTree BST ); Position FindMax( BinTree BST ); int main() { BinTree BST, MinP, MaxP, Tmp; ElementType X; int N, i; BST NULL; scanf(%d, N); for ( i0; iN; i ) { scanf(%d, X); BST Insert(BST, X); } printf(Preorder:); PreorderTraversal(BST); printf(\n); MinP FindMin(BST); MaxP FindMax(BST); scanf(%d, N); for( i0; iN; i ) { scanf(%d, X); Tmp Find(BST, X); if (Tmp NULL) printf(%d is not found\n, X); else { printf(%d is found\n, Tmp-Data); if (TmpMinP) printf(%d is the smallest key\n, Tmp-Data); if (TmpMaxP) printf(%d is the largest key\n, Tmp-Data); } } scanf(%d, N); for( i0; iN; i ) { scanf(%d, X); BST Delete(BST, X); } printf(Inorder:); InorderTraversal(BST); printf(\n); return 0; } /* 你的代码将被嵌在这里 */输入10 5 8 6 2 4 1 0 10 9 7 5 6 3 10 0 5 5 5 7 0 10 3输出Preorder: 5 2 1 0 4 8 6 7 10 9 6 is found 3 is not found 10 is found 10 is the largest key 0 is found 0 is the smallest key 5 is found Not Found Inorder: 1 2 4 6 8 9代码BinTree Insert( BinTree BST, ElementType X ){ if(BST NULL){ BST (BinTree)malloc(sizeof(struct TNode)); BST-Data X; BST-Left NULL; BST-Right NULL; }else if(XBST-Data){ BST-Left Insert(BST-Left,X); }else if(XBST-Data){ BST-Right Insert(BST-Right,X); } return BST; } BinTree Delete( BinTree BST, ElementType X ){ BinTree temp; if(BST ! NULL){ if(XBST-Data){ BST-Left Delete(BST-Left,X); }else if(XBST-Data){ BST-Right Delete(BST-Right,X); }else{ if(BST-LeftBST-Right){ temp FindMin(BST-Right); BST-Data temp-Data; BST-Right Delete(BST-Right,temp-Data); }else{ temp BST; if(BST-Left NULL) BST BST-Right; else if(BST-Right NULL) BST BST-Left; free(temp); } } return BST; } printf(Not Found\n); return BST; } Position Find( BinTree BST, ElementType X ){ if(BSTNULL) return NULL; if(BST-Data X) return BST; if(BST!NULL){ if(XBST-Data) return Find(BST-Left,X); else if(XBST-Data) return Find(BST-Right,X); } } Position FindMin( BinTree BST ){ if(BST){ while(BST-Left){ BST BST-Left; } } return BST; } Position FindMax( BinTree BST ){ if(BST){ while(BST-Right){ BST BST-Right; } } return BST; }删除代码解读