//
// Created by 13265 on 2023/5/25.
//
#include <queue>
# include "iostream"
# include "vector"
using namespace std;
//todo 完成数据结构中的二叉树章节的相关练习
struct Node{
    int val;
    Node *left, *right;
    Node(int x) : val(x) ,left(nullptr), right(nullptr){};
    Node(){};
};
/**
 * 创建二叉树的节点
 * @param root 根节点
 * @return 返回创建的节点
 */
Node* createNode(Node* root, int data) {
    if (root == nullptr) {
        return new Node(data);
    } else if (data <= root->val) {
        root->left = createNode(root->left, data);
    } else {
        root->right = createNode(root->right, data);
    }
    return root;
}
/**
 * 注意：  必须有序的二叉树
 * 删除某个二叉树的节点
 *  分为三种情况，删除的节点为叶子节点，有一个节点的节点 ，有一个子树的节点
 *
 *
 * @param root 树的根节点
 * @param index 要删除的节点val
 */
Node* deleteNode(Node *& root,int index){
    if(root == nullptr){
        return root;
    }
    //todo 先遍历找到要删除的节点
    else if(root->val > index){
        root->left = deleteNode(root->left, index);
    }else if (root->val < index){
        root->right = deleteNode(root->right, index);
    }
    //todo 找到了， 开始分情况删除
    else{
        //case1 : 要删除的节点是叶子节点
        if (root->left == nullptr && root->right == nullptr){
            delete root;
            root = nullptr;
        }
        //case2 : 要删除的节点上有一个子节点
        else if (root->left == nullptr || root->right == nullptr){
            Node* temp = root;
            //左子节点不为空
            if(root->left != nullptr){
                root = root->left;
            }
            //右子节点不为空
            else{
                root = root->right;
            }
            delete temp;
        }
        //case3 : 要删除的节点上有两个子节点
        else{/** 为了保持二叉搜索树的性质，我们选择该结点的右子树中的最小值结点来作为替代结点（也可以选择左子树中的最大值结点）。*/
            Node* temp = root->right;
            /*从该结点的右子树开始，找到右子树中的最小值结点。在这个过程中，我们不断遍历右子树的左子结点，直到找到没有左子结点的结点，即为右子树中的最小值结点。*/
            while(temp->left != nullptr){
                temp = temp->left;
            }
            /*然后，我们将该最小值赋值给待删除的结点，并递归地删除该最小值结点（因为该最小值结点已经成为了待删除结点的替代结点，所以要将其从右子树中删除）。*/
            root->val = temp->val;
            root->right = deleteNode(root->right , temp->val);
        }
    }
    return root;
}
/**
 * 更新节点
 * @param root 树的根节点
 * @param oldVal 原来的节点val
 * @param newVal  新的节点val
 */
void updateNode(Node *& root, int oldVal , int newVal){
    if (root == nullptr){
        return;
    }
    Node* temp = root;
    //因为是有序二叉树，所以需要先删除， 然后在进行插入
    deleteNode(root,oldVal);
    createNode(root,newVal);
}
/**
 * 二叉树的层序遍历
 * @param root 二叉树根节点的指针
 */
void listNode(Node *root){
    //可以有三种遍历方式
    queue<Node*> que ;
    que.push(root);
    while (!que.empty()){
        //先出队列， 然后将值输出 ，然后将该节点的子节点全部入队列
        Node * temp = que.front();
        que.pop();
        cout<<temp->val<<" ";
        if (temp->left != nullptr){
            que.push(temp->left);
        }
        if (temp->right != nullptr){
            que.push(temp->right);
        }
    }
}
void preOrder(Node* root){
    if (root== nullptr){
        return;
    }
    cout<<root->val<<" -> ";
    if (root->left != nullptr){
        preOrder(root->left);
    }
    if(root->right != nullptr){
        preOrder(root->right);
    }
}
void midOrder(Node* root){
    if (root== nullptr){
        return;
    }
    midOrder(root->left);
    cout<<root->val<<" -> ";
    midOrder(root->right);
}
void postOrder(Node* root){
    if (root== nullptr){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<" -> ";
}
int main(){
    cout<<"test"<<endl;
    //添加节点
    Node* root = nullptr;
    root = createNode(root, 5);
    root = createNode(root, 3);
    root = createNode(root, 7);
    root = createNode(root, 1);
    root = createNode(root, 4);
    root = createNode(root, 6);
    root = createNode(root, 8);
    deleteNode(root,4);
    cout<<"\n前序遍历: "<<endl;
    preOrder(root);
    cout<<"\n中序遍历: "<<endl;
    midOrder(root);
    updateNode(root,3,10);
    cout<<"\n后序遍历: "<<endl;
    postOrder(root);
    cout<<endl;
    cout<<"层序遍历 "<<endl;
    listNode(root);
    return 0;
}