Dilshan
Dilshan

Reputation: 45

Iterate through Binary search tree java

Can some one show me the way to loop a binary tree in order to traverse all nodes. I will add students by insert method. I just want to print all the students objects. This is my BST :

public class BinarySearchTree<Students extends Comparable<? super Student>> {
    public static BinaryNode root;

    public BinarySearchTree() {
        this.root = null;
    }

public void insert(Student student) {

        root = insert(student, root);
    }

    protected BinaryNode<Student> insert(Student student, BinaryNode<Student> t) {
        if (t == null) {

            t = new BinaryNode<Student>(student);
        } else if (student.compareTo(t.element) < 0) {
            t.left = insert(student, t.left);
        } else if (student.compareTo(t.element) > 0) {
            t.right = insert(student, t.right);
        } else {
            // throw new DuplicateItemException(student.toString());
        }
        return t;
    }
}

Node Class :

class BinaryNode<Student> {
    // Constructor
    BinaryNode(Student theElement) {
        element = theElement;
        left = right = null;
    }

    // Data; accessible by other package routines
    Student element; // The data in the node
    BinaryNode<Student> left; // Left child
    BinaryNode<Student> right; // Right child
}

Upvotes: 2

Views: 4531

Answers (3)

Add this method to the BinarySearchTree class:

public void inorder(BinaryNode node) {
    if (node == null) {
        return;
    }
    inorder(node.left);
    System.out.print(...); //whatever you want to do with the node
    inorder(node.right);
}

In a similar way you can do preorder and postorder traversals.

Upvotes: 1

thepaulo
thepaulo

Reputation: 380

public class BinarySearchTree<Students extends Comparable<? super Student>> {
    public static BinaryNode root;

    public BinarySearchTree() {
        this.root = null;
    }
    ...
    public void print() {
        print(root);
    }

    public void print(BinaryNode<Student> node) {
        if (node == null) {
            return;
        }
        print(node.left);
        doSomething(node.getStudent());
        print(node.right);
    }
}

Upvotes: 0

bolec_kolec
bolec_kolec

Reputation: 510

There are 3 ways to traverse Binary Search Trees.

  • Pre-order

    public void preOrder(BinaryNode node) {
        if (node == null) {
            return;
        }
        doSomethig(node.element); // process node
        preOrder(node.left);
        preOrder(node.right);
    }
    
  • In-order in this case nodes are traversed in order

    public void inOrder(BinaryNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        doSomethig(node.element); // process node
        inOrder(node.right);
    }
    
  • Post-order

    public void postOrder(BinaryNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        doSomethig(node.element); // process node
    }
    

You have to choose one of these and run for example:

    preOrder(root); // where root is a handle to your BST

Upvotes: 0

Related Questions