二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
头文件SearchTree.h
#ifndef SEARCHTREE_H #define SEARCHTREE_H typedef int Element; typedef struct Node{ Element data; struct Node* Left; struct Node* Right; }SearchNode,*SearchTree,*Position; void MakeEmpty(SearchTree T); bool IsEmpty(SearchTree T); bool Find(Element x,SearchTree T); Position FindMin(SearchTree T); Position FindMax(SearchTree T); Position Insert(Element x,SearchTree &T); Position Delete(Element x,SearchTree T); void InOrderTraverse(SearchTree T); #endif //SEARCHTREE_H
实现文件SearchTree.cpp
#include "SearchTree.h" #include <stdio.h> #include <stdlib.h> #include <math.h> void MakeEmpty(SearchTree T) //清空二叉树 { if(T) { MakeEmpty(T->Left); MakeEmpty(T->Right); free(T); } } bool IsEmpty(SearchTree T) //判断二叉树是否为空 { if(T == NULL) return true; else return false; } bool Find(Element x,SearchTree T) //查找x是否在树中存在 { if(T == NULL) return false; else if(x < T->data) return Find(x,T->Left); else if(x > T->data) return Find(x,T->Right); return true; } Position FindMin(SearchTree T) //查找最小数 { if(T == NULL) return NULL; else if(T->Left == NULL) return T; else return FindMin(T->Left); } Position FindMax(SearchTree T) //查找最大数 { if(T == NULL) return NULL; while(T->Right != NULL) T = T->Right; return T; } Position Insert(Element x,SearchTree &T) //向二叉树中插入数据 { if(T == NULL) { T = (SearchTree)malloc(sizeof(SearchNode)); if(!T) { printf("内存分配失败\n"); exit(1); } T->data = x; T->Left = T->Right = NULL; } else { if(x < T->data) T->Left = Insert(x,T->Left); else if( x > T->data) T->Right = Insert(x,T->Right); } return T; } Position Delete(Element x,SearchTree T) //删除元素为x的节点 { SearchTree temp = NULL; SearchTree tp = NULL; if(T == NULL) return NULL; else if(x < T->data) T->Left = Delete(x,T->Left); else if(x > T->data) T->Right = Delete(x,T->Right); else if(T->Left && T->Right) { temp = FindMin(T->Right); T->data = temp->data; T->Right = Delete(temp->data,T->Right); } else { tp = T; if(T->Left == NULL) T = T->Right; if(T->Right == NULL) T = T->Left; free(tp); } return T; } void InOrderTraverse(SearchTree T) //前序遍历 { if(T) { printf("%d ",T->data); InOrderTraverse(T->Left); InOrderTraverse(T->Right); } }
测试文件main.cpp
#include "SearchTree.h" #include <stdio.h> int main() { SearchTree T = NULL; printf("please enter the element\n"); int ch; while(scanf_s("%d",&ch) != EOF) Insert(ch,T); printf("集合中的内容为:\n"); InOrderTraverse(T); printf("\n"); printf("请输入要查找的数据\n"); scanf_s("%d",&ch); if(Find(ch,T)) printf("在集合中找到元素:%d\n",ch); else printf("在集合中没有找到元素:%d\n",ch); printf("集合中的最小元素为:%d\n",FindMin(T)->data); printf("集合中的最大元素为:%d\n",FindMax(T)->data); printf("请输入要删除的元素\n"); int word; scanf_s("%d",&word); Delete(word,T); printf("删除后集合的元素为:\n"); InOrderTraverse(T); return 0; }