저장 성 빅 데이터 구조 연습 문제 노트: 이 진 트 리 검색

두 갈래 검색 트 리
느낌

#include 
#include 
using namespace std;

typedef int ElemType;

typedef struct TreeNode *BinTree;
struct TreeNode{
    ElemType data;
    BinTree left;
    BinTree right;
};

BinTree FindTail(ElemType x,BinTree BST)
{
    if(!BST){
        return NULL;
    }
    if(x > BST->data){
        //   
        return FindTail(x,BST->right);
    }else if(x < BST->data){
        return FindTail(x,BST->left);
    }else{
        return BST;
        //  
    }
}

BinTree FindFor(ElemType x,BinTree BST)
{
    while(!BST){
        if(x > BST->data){
            BST = BST->right;
        }else if(x < BST->data){
            BST = BST->left;
        }else{
            return BST;
        }
    }
    return NULL;
}

//     ，            
BinTree FindMin(BinTree BST)
{
    if(!BST){
        return NULL;
    }else if(!BST->left){
        return BST;
    }else{
        return FindMin(BST->left);
    }
}

BinTree FindMax(BinTree BST)
{
    if(BST){
        while(BST->right){
            BST = BST->right;
        }
    }
    return BST;
}

BinTree Insert(ElemType x,BinTree BST)
{
    if(!BST){
        BST = (BinTree)malloc(sizeof(struct TreeNode));
        BST->data = x;
        BST->left = BST->right = NULL;
    }else{
        if(x < BST->data){
            BST->left = Insert(x,BST->left);
        }else if(x > BST->data){
            BST->right = Insert(x,BST->right);
        }
    }
    return BST;
}

BinTree Delete(ElemType x,BinTree BST)
{
    BinTree temp;
    if(!BST){
        printf("Not found");
    }else if(x < BST->data){
        BST->left = Delete(x,BST->left);
    }else if(x > BST->data){
        BST->right = Delete(x,BST->right);
    }else //      
        if(BST->left && BST->right){    //     
            temp = FindMin(BST->right);
            //          
            BST->data = temp->data;
            BST->right = Delete(BST->data,BST->right);
            //            
        }else{  //         
            temp = BST;
            if(!BST->left){
                BST = BST->right;
            }else if(!BST->right){
                BST = BST->left;
            }
            free(temp);
        }
    return BST;
}

void InOrder(BinTree BT)
{
    if(BT){
        InOrder(BT->left);
        printf("%d ",BT->data);
        InOrder(BT->right);
    }
}

int main(){
	BinTree BST = NULL;
	BST = Insert(5,BST); 
	BST = Insert(7,BST); 
	BST = Insert(3,BST); 
	BST = Insert(1,BST); 
	BST = Insert(2,BST); 
	BST = Insert(4,BST); 
	BST = Insert(6,BST); 
	BST = Insert(8,BST); 
	BST = Insert(9,BST); 
	/*
			    5
			   /\
			  3  7
             /\	 /\
            1 4 6  8
			\      \
			 2      9
	*/
	printf("InOrder"); 
    InOrder(BST);
    printf("
");
	printf("Min Value:%d
",FindMin(BST)->data);
	printf("Max Value:%d
",FindMax(BST)->data); 
	//printf("Find 3 Value:%d
",FindFor(3,BST)->data);
	//printf("Find 7 Value:%d
",FindTail(7,BST)->data);
	printf("Delete 5
");
	Delete(5,BST);
	/*
			    6
			   /\
			  3  7
             /\	  \
            1 4    8
			\      \
			 2      9
	*/
	printf("InOrder:"); 
	InOrder(BST);
	printf("
");
	return 0;
}