ডেটা স্ট্রাকচারে বাইনারি ট্রি ট্রাভার্সাল

এই সেকশনে আমরা বাইনারি সার্চ ট্রিতে উপস্থিত কীগুলো ট্রাভার্স করার জন্য বিভিন্ন ট্রাভার্সাল অ্যালগরিদম দেখব। এগুলো হল ইনঅর্ডার ট্রাভার্সাল, প্রি-অর্ডার ট্রাভার্সাল, পোস্ট-অর্ডার ট্রাভার্সাল এবং লেভেল-অর্ডার ট্রাভার্সাল।

ধরা যাক আমাদের একটা ট্রি আছে এরকম -

ইনঅর্ডার ট্রাভার্সাল সিকোয়েন্স হবে যেন - 5 8 10 15 16 20 23

প্রি-অর্ডার ট্রাভার্সাল সিকোয়েন্স হবে যেন - 10 5 8 16 15 20 23

পোস্ট-অর্ডার ট্রাভার্সাল সিকোয়েন্স হবে যেন - 8 5 15 23 20 16 10

লেভেল-অর্ডার ট্রাভার্সাল সিকোয়েন্স হবে যেন - 10, 5, 16, 8, 15, 20, 23

অ্যালগরিদম

inorderTraverse(root):
Begin
    if root is not empty, then
        inorderTraversal(left of root)
        print the value of root
        inorderTraversal(right of root)
    end if
End
preorderTraverse(root):
Begin
    if root is not empty, then
        print the value of root
        preorderTraversal(left of root)
        preorderTraversal(right of root)
    end if
End
postorderTraverse(root):
Begin
    if root is not empty, then
        postorderTraversal(left of root)
        postorderTraversal(right of root)
        print the value of root
    end if
End
levelOrderTraverse(root):
Begin
    define queue que to store nodes
    insert root into the que.
    while que is not empty, do
        item := item present at front position of queue
        print the value of item
        if left of the item is not null, then
            insert left of item into que
        end if
        if right of the item is not null, then
            insert right of item into que
        end if
        delete front element from que
    done
End

উদাহরণ

#include 
#include 
using namespace std;
class node {
public:
    int h_left, h_right, bf, value;
    node *left, *right;
};
class tree {
private:
    node *get_node(int key);
public:
    node *root;
    tree() {
        root = NULL; //set root as NULL at the beginning
    }
    void inorder_traversal(node *r);
    void preorder_traversal(node *r);
    void postorder_traversal(node *r);
    void levelorder_traversal(node *r);
    node *insert_node(node *root, int key);
};
node *tree::get_node(int key) {
    node *new_node;
    new_node = new node; //create a new node dynamically
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key; //store the value from given key
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}
void tree::inorder_traversal(node *r) {
    if(r != NULL) { //When root is present, visit left - root - right
        inorder_traversal(r->left);
        cout << r->value << " ";
        inorder_traversal(r->right);
    }
}
void tree::preorder_traversal(node *r) {
    if(r != NULL) { //When root is present, visit left - root - right
        cout << r->value << " ";
        preorder_traversal(r->left);
        preorder_traversal(r->right);
    }
}
void tree::postorder_traversal(node *r) {
    if(r != NULL) { //When root is present, visit left - root - right
        postorder_traversal(r->left);
        postorder_traversal(r->right);
        cout << r->value << " ";
    }
}
void tree::levelorder_traversal(node *root) {
    queue  que;
    node *item;
    que.push(root); //insert the root at first
    while(!que.empty()) {
        item = que.front(); //get the element from the front end
        cout << item->value << " ";
        if(item->left != NULL) //When left child is present, insert into queue
            que.push(item->left);
        if(item->right != NULL) //When right child is present, insert into queue
            que.push(item->right);
        que.pop(); //remove the item from queue
    }
}
node *tree::insert_node(node *root, int key) {
    if(root == NULL) {
        return (get_node(key)); //when tree is empty, create a node as root
    }
    if(key < root->value) { //when key is smaller than root value, go to the left
        root->left = insert_node(root->left, key);
    } else if(key > root->value) { //when key is greater than root value, go to the right
        root->right = insert_node(root->right, key);
    }
    return root; //when key is already present, do not insert it again
}
main() {
    node *root;
    tree my_tree;
    //Insert some keys into the tree.
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "In-Order Traversal: ";
    my_tree.inorder_traversal(my_tree.root);
    cout << "\nPre-Order Traversal: ";
    my_tree.preorder_traversal(my_tree.root);
    cout << "\nPost-Order Traversal: ";
    my_tree.postorder_traversal(my_tree.root);
    cout << "\nLevel-Order Traversal: ";
    my_tree.levelorder_traversal(my_tree.root);
}

আউটপুট

In-Order Traversal: 5 8 10 15 16 20 23
Pre-Order Traversal: 10 5 8 16 15 20 23
Post-Order Traversal: 8 5 15 23 20 16 10
Level-Order Traversal: 10 5 16 8 15 20 23