Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
2.9 kB
2
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;
        }
        
    }
    
}


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);
    

    
    return 0;
}
Leave a Comment