//
// main.cpp
// niukewang
//
// Created by qj on 2019/8/17.
// Copyright © 2019 qj. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
//二叉搜索树的查找，添加和删除
struct TreeNode{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){
}
};
//二叉搜索树的添加
TreeNode* insert(TreeNode* BST,int data){
if(!BST){//如果原树为空，生成并返回一个结点的二叉搜索树
BST = new TreeNode(data);
}else{//开始要插入元素的位置
if(data < BST->val ){
BST->left = insert(BST->left,data);//递归插入左子树
}else if(data > BST->val){
BST->right = insert(BST->right,data);//递归插入右子树
}
//如果元素已经存在，什么都不做
}
return BST;
}
//二叉树的查找
TreeNode * find(TreeNode* BST,int data){
while(BST){
if(data < BST->val){
BST = BST->left;
}else if(data > BST->val){
BST = BST->right;
}else{
break;
}
}
return BST;
}
//查找最小值结点
TreeNode * findMin(TreeNode* BST){
if(BST){
while(BST->left){
BST = BST->left;
}
}
return BST;
}
//查找最大值结点
TreeNode * findMax(TreeNode* BST){
if(BST){
while(BST->right){
BST = BST->right;
}
}
return BST;
}
//删除结点
TreeNode * deleteNode(TreeNode *BST,int data){
if(!BST){
cout << "要删除的元素未找到" << endl;
}else if(data < BST->val){
//左子树递归删除
BST->left = deleteNode(BST->left,data);
}else if(data > BST->val){
//右子树递归删除
BST->right = deleteNode(BST->right, data);
}else{//找到要删除的结点
//被删除结点有左右两个子结点
if(BST->left && BST->right){
//在右子树中找到最小的元素填充删除结点
//1首先找到右子树里面的最小值，2将其值复制给当前结点，3删除该结点
TreeNode *temp = findMin(BST->right);
BST->val = temp->val;
//在删除结点的右子树中删除最小元素
BST->right = deleteNode(BST->right,temp->val);
}else{//被删除结点有一个或无子结点
TreeNode *temp = BST;
if(BST->left){//有左孩子
BST = BST->left;
}else if(BST->right){//有右孩子
BST = BST->right;
}else{//被删除结点是叶子结点
BST = NULL;
}
delete temp;//释放内存
}
}
return BST;
}
void preOrder(TreeNode* BST){
if(BST){
cout << BST->val << endl;
preOrder(BST->left);
preOrder(BST->right);
}
}
void inOrder(TreeNode* BST){
if(BST){
inOrder(BST->left);
cout << BST->val << endl;
inOrder(BST->right);
}
}
int main(int argc, const char * argv[]) {
return 0;
}
