after deleting 2 ,55 and 21 ..am getting only in in-order how do i make other 2 oders
package com.eyc.roughworks.binarysearchtree;

import java.lang.*;
import java.io.*;

public class pBSTRemoveNode {

    public pBSTRemoveNode left, right;
    public Comparable data;

    public static pBSTRemoveNode tree_AddNumber(pBSTRemoveNode r, Comparable n) {
        if (r == null) {
            r = new pBSTRemoveNode();
            r.left = r.right = null;
            r.data = n;
        } else if (r.data.compareTo(n) < 0)
            r.right = tree_AddNumber(r.right, n);
        else if (r.data.compareTo(n) > 0)
            r.left = tree_AddNumber(r.left, n);
        return r;
    }

    public static pBSTRemoveNode tree_removeNumber(pBSTRemoveNode r, Comparable n) {
        if (r != null) {
            if (r.data.compareTo(n) < 0) {
                r.right = tree_removeNumber(r.right, n);
            } else if (r.data.compareTo(n) > 0) {
                r.left = tree_removeNumber(r.left, n);
            } else {
                if (r.left == null && r.right == null) {
                    r = null;
                } else if (r.left != null && r.right == null) {
                    r = r.left;
                } else if (r.right != null && r.left == null) {
                    r = r.right;
                } else {
                    if (r.right.left == null) {
                        r.right.left = r.left;
                        r = r.right;
                    } else {
                        pBSTRemoveNode q, p = r.right;
                        while (p.left.left != null)
                            p = p.left;
                        q = p.left;
                        p.left = q.right;
                        q.left = r.left;
                        q.right = r.right;
                        r = q;
                    }
                }
            }
        }
        return r;
    }

    public static void tree_InOrderPrint(pBSTRemoveNode r) {
        if (r != null) {
            tree_InOrderPrint(r.left);
            System.out.print(" " + r.data);
            tree_InOrderPrint(r.right);
        }
    }

    public static void main(String[] args) {
        pBSTRemoveNode tree = null;
        int[] numbers = { 21, 3, 4, 55, 6, 3, 44, 7, 9, 4, 2, 3, 11, 56, 7, 54, 67, 87, 54, 67, 87, 45, 66, 77, 42, 21 };
        System.out.print("inserting: ");
        for (int i = 0; i < numbers.length; i++) {
            Integer n = new Integer(numbers[i]);
            System.out.print(" " + n);
            tree = tree_AddNumber(tree, n);
        }
        System.out.print("\ntree: ");
        tree_InOrderPrint(tree);
//      int j = 6;
        int j = 0;
        int num = 2;
        deleteNode(tree, numbers, j, num);

        num = 56;
        deleteNode(tree, numbers, j, num);

        num = 21;

        deleteNode(tree, numbers, j, num);


    }

    private static void deleteNode(pBSTRemoveNode tree, int[] numbers, int j, int num) {
        for(int i = 0;i<numbers.length;i++){
            if(numbers[i]==num){
                j = i;
            }
        }

        {
            Integer n = new Integer(numbers[j]);
            System.out.print("\nremove: " + n + " tree: ");
            tree = tree_removeNumber(tree, n);
            tree_InOrderPrint(tree);
        }
        System.out.println("\ndone ;-)");
    }
}

Edited 3 Years Ago by Reverend Jim: Fixed formatting

This article has been dead for over six months. Start a new discussion instead.