Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
4.0 kB
1
Indexable
Never
#include<iostream>
#include <stack>
//#include<bits/stdc++.h>
using namespace std;
class Node {
public:
    int value;
    Node* left;
    Node* right;
    Node(int value)
    {
        this->value=value;
        this->left=left;
        this->right=right;
    }
};
void insert(Node*& root, int a)
{
    Node* node=new Node(a);
    if(!root)
    {
        root=node;
        return;
    }
    Node* prev=NULL;
    Node* temp=root;
    while(temp)
    {
        if(temp->value>a)
        {
            prev=temp;
            temp=temp->left;
        }
        else if(temp->value<a)
        {
            prev=temp;
            temp=temp->right;
        }
        
    }
    if(prev->value>a)
    {
        prev->left=node;
    }
    else
    {
        prev->right=node;
    }
}
void inorder(Node* root)
{
    if (!root)
    {
        return;
    }
    inorder(root->left);
    cout<<root->value<<" ";
    inorder(root->right);
    
}
void inorder_iteratively(Node * root) {
    stack<Node *> st;
    Node * at = root;
    while(at or !st.empty()) {
        while(at) {
            st.push(at);
            at = at->left;
        }
        at = st.top();
        st.pop();
        cout << at->value << " " ;
        at=at->right;
    }
}
void preorder(Node* root)
{
    if (!root)
    {
        return;
    }
    cout<<root->value<<" ";
    preorder(root->left);
    preorder(root->right);
    
}
void preorder_iteratively(Node * root) {
    if(!root) {
        return;
    }
    stack<Node *> st;
    st.push(root);
    while(!st.empty()) {
        Node * c = st.top();
        st.pop();
        
        cout << c->value << " ";
        if(c->right) {
            st.push(c->right);
        }
        if(c->left) {
            st.push(c->left);
        }
    }
}
void postorder(Node* root)
{
    if (!root)
    {
        return;
    }
    
    postorder(root->left);
    postorder(root->right);
    cout<<root->value<<" ";
}
void postorder_iteratively(Node * root) {
    if(!root) {
        return;
    }
    stack<Node * > st;
    Node * at = root;
    Node * visited = NULL;
    
    while(at or !st.empty()) {
        while(at) {
            st.push(at);
            at = at->left;
        }
        Node * c = st.top();
        if(c->right and c->right != visited) {
            at = c->right;
        }
        else {
            cout << c->value << " ";
            st.pop();
            visited = c;
        }
        
    }
    
}

Node * delete_node(Node * root, int val) {
    if(!root) {
        return root;
    }
    if(root->value > val) {
        root->left = delete_node(root->left, val);
        return root;
    }
    else if(root->value < val){
        root->right = delete_node(root->right, val);
        return root;
    }
    
    if(!root->left) {
        Node * tmp = root->right;
        delete root;
        return tmp;
    }
    else if(!root->right) {
        Node * tmp = root->left;
        delete root;
        return tmp;
    }
    else {
        Node * child = root->right;
        Node * child_parent = root;
        while(child->left) {
            child_parent = child;
            child = child->left;
        }
        if(child_parent != root) {
            child_parent->left = child->right;
        }
        else {
            child_parent->right = child->right;
        }
        root->value = child->value;
        delete child;
        return root;
    }
    
    return NULL;
}
int main()
{
    Node* root = new Node(6);

    insert(root, 8);
    insert(root, 2);
    insert(root, 1);
    insert(root, 4);
    insert(root, 3);
    insert(root, 7);

//    cout<<"Inorder:";
//    inorder(root);
//    cout<<endl;
//    inorder_iteratively(root);
//
//    cout<<"Preorder:";
//    preorder(root);
//    cout<<endl;
//    preorder_iteratively(root);

    cout<<"Postorder:";
//    postorder(root);
//    cout << endl;
    postorder_iteratively(root);
    cout << endl;
    root = delete_node(root, 2);
    postorder(root);
    cout << endl;
    inorder_iteratively(root);
    
    return 0;
}
Leave a Comment