binary search tree

Ads
 

binary search tree

how can i make binary search tree? i want write a code that make dictionary with binary search tree data structure.please help me?

View Answers

January 9, 2012 at 12:47 PM

class bnode {   
  String key;
  bnode left;
  bnode right;
  bnode() {           
    key = null;
    left = null;
    right = null;
  }
  bnode(String key) {
    this.key = key;
    left = null;
    right = null;
  }
};
class BinarySearchTree {                
  bnode root;
  BinarySearchTree() {
    root = null;
  }
  void put(String key) {
    bnode current = root;
    bnode prev = current;
    if (root == null) {
      root = new bnode(key);
    }
    else {
      boolean insert = false;
      while (insert == false) {
        prev = current;
        if (key.compareTo(current.key) < 0) {
          if (current.left == null) {
            current.left = new bnode(key);
            insert = true;
          }
          current = current.left;
        }
        else {
          if (current.right == null) {
            current.right = new bnode(key);
            insert = true;
          }
          current = current.right;
        }
      }
    }
  }
  boolean delete(String key) {        
    boolean deleted = true;
    bnode current = root;
    bnode prev = current;
    while (current != null) {
      if (key.compareTo(current.key) > 0) {
        prev = current;
        current = current.right;
      }
      else if (key.compareTo(current.key) < 0) {
        prev = current;
        current = current.left;
      }
      else if (key.compareTo(current.key) == 0) {
        deleted = false;
        break;
      }
    }
    if (check(current) == 0) {
      if (current.key.compareTo(prev.key) > 0) {
        prev.right = null;
      }
      else {
        prev.left = null;
      }
    }
    else if (check(current) == 1) {

      if (current.key.compareTo(prev.key) > 0) {
        if (current.left != null) {
          prev.right = current.left;
        }
        else {
          prev.right = current.right;
        }
      }
      else {
        if (current.left != null) {
          prev.left = current.left;
        }
        else {
          prev.left = current.right;
        }
      }
    }
    else if (check(current) == 2) {
      bnode temp = inord(current);
      if (current == root) {
        root.key = temp.key;
      }
      else {
        if (current.key.compareTo(prev.key) > 0) {
          prev.right.key = temp.key;
        }
        else {
          prev.left.key = temp.key;
        }
      }
    }
    return deleted;
  }
  bnode inord(bnode a) {                    
    int t = 0;
    bnode ret, prev = new bnode();
    prev = a;
    a = a.right;
    while (a.left != null) {
      prev = a;
      a = a.left;
      t = 1;
    }
    ret = a;
    if (t == 0) {
      prev.right = null;
    }
    else {
      prev.left = null;
    }
    a = null;
    return ret;
  }
  int check(bnode a) { 
    int ret;
    if ( (a.left != null) && (a.right != null)) {
      ret = 2;
    }
    else if ( (a.left == null) && (a.right == null)) {
      ret = 0;
    }
    else {
      ret = 1;
    }
    return ret;
  }
  void printIn(bnode oot) {                  
    if (oot.left != null) {
      printIn(oot.left);
    }
    System.out.println("--------" + oot.key + "----------");
    if (oot.right != null) {
      printIn(oot.right);
    }
  }
  public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();
    String names[]={"A","B","C","D"};
    for(int i=0;i<names.length;i++){
        a.put(names[i]);
    }
    a.printIn(a.root);
  }
}

January 9, 2012 at 12:48 PM

import java.util.*;

    class TNode{
    int number;
    TNode parent;
    TNode leftChild;
    TNode rightChild;
    }
    public class BinarySearchTree{

    public TNode root = null; 
    TNode currentNode = root;

    public boolean IsEmpty(){
    if(root == null)
    return true;
    return false;
    }

    TNode create(int number){
    TNode node = new TNode();
    node.number = number;
    node.parent = null;
    node.leftChild = null;
    node.rightChild = null;
    return node;
    }

    public void insert(int number){
    currentNode = add (root,number);
    if(IsEmpty() == true && currentNode != null)
    root = currentNode;
    currentNode = root;
    }

    TNode add(TNode node, int number){
    if(node == null){
    node = create(number);
    return node;
    }
    else if(number < node.number){
    if(node.leftChild != null)
    add(node.leftChild,number);
    else
    node.leftChild = create(number);
    }
    else if(number >= node.number){
    if(node.rightChild != null)
    add(node.rightChild,number);
    else
    node.rightChild = create(number);
    }
    return null;
    }

    public void find(int number){
    IsEmpty();
    currentNode = find(root, number);

    System.out.println("Search returned Node: " + currentNode.number);
    System.out.println("Node's left child: " + currentNode.leftChild);
    System.out.println("Node's right child: " + currentNode.rightChild);
    }
    TNode find(TNode currentNode, int number){
    while(currentNode.number != number && currentNode != null){
    if(number < currentNode.number){
    currentNode = currentNode.leftChild;
    }
    else if(number > currentNode.number){
    currentNode = currentNode.rightChild;
    }
    else{
    currentNode = currentNode.rightChild;
    }
    }
    return currentNode;
    }
    public TNode getRoot(){
        return root;
    }
    private void display(TNode input){
    if(input == null){
    return;
    }
    display(input.leftChild);
    System.out.println(input.number);
    display(input.rightChild);
    }
    public static void main(String[] args){
    BinarySearchTree RBT = new BinarySearchTree();
    Scanner console = new Scanner(System.in);
    System.out.println("How many numbers would you like to enter into the Red Black Tree?");
    int k = console.nextInt();
    int inputarray[] = new int[k];
    for(int i=0; i< k; i++){
    System.out.println("Please enter the " + (i+1)+ " number: ");
    inputarray[i]= console.nextInt();
    }
    System.out.println("\n\n****Display Start****");
    for(int i=0; i<k; i++){
    RBT.insert(inputarray[i]);
    }
    RBT.display(RBT.getRoot());
    }
     }

Ads









Related Tutorials/Questions & Answers:
binary search tree
binary search tree  Construct a binary search tree by inserting the following sequence of characters into an empty tree. N O N L I N E A R D A T A Visit the tree using all three traversal algorithms and list the output sequence
binary search tree
binary search tree  Construct a binary search tree by inserting words into an empty tree. "cut your coat according to your cloth" Visit the tree.... get a word from the user and search the level/levels of that word. refer split
Advertisements
binary search tree
binary search tree  how can i make binary search tree? i want write a code that make dictionary with binary search tree data structure.please help me...){ IsEmpty(); currentNode = find(root, number); System.out.println("Search
Binary Search Tree
Binary Search Tree  Question-1 ) Modify the BinarySearchTree class so that the iterators are fail-fast.Test your class with amain method ? Question-2 ) Modify the BinarySearchTree class so that the BinarySearchTree objects
Binary Search Tree
Binary Search Tree  Question-1 ) Modify the BinarySearchTree class so that the iterators are fail-fast.Test your class with amain method ? Question-2 ) Modify the BinarySearchTree class so that the BinarySearchTree objects
Binary search tree (insertion) urgent!!
Binary search tree (insertion) urgent!!  Create a program to construct a binary search tree consisting of nodes that each stores an integer.... Assume a binary search tree is constructed from the values 14, 35, 2, 3, 39
binary search tree from text file
binary search tree from text file  How so I go about constructing a binary search tree from a text file, which has letters and numbers, which must be sorted and printed in ascending order. E.g. Text file contents 3 apples pears
How to create binary search tree using an array?
How to create binary search tree using an array?  hello people, pls guide me on the topic above. i have an string array, i want to make a binary search tree based on data inside this array. the array contains names of people
Binary tree
Binary tree  a. Construct a method to implement a binary tree using an array. b. Implement the binary tree to store numbers in sorted order
binary tree
binary tree  how to count no. of nodes in a binary tree for mlm if it complet tree or incomplet tree in php using mysql db
binary tree
binary tree  can a binary tree be implemented with out comparing...://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml http://www.roseindia.net/java/java-get-example/java-binary-tree-insert.shtml
binary search program
binary search program  write a program to searching a string using binary search
binary search program
binary search program  write a program to searching a string using binary search
binary search program
binary search program  write a program to searching a string using binary search
binary search program
binary search program  write a program to searching a string using binary search
binary search program
binary search program  write a program to searching a string using binary search
ModuleNotFoundError: No module named 'binary-tree'
ModuleNotFoundError: No module named 'binary-tree'  Hi, My Python... 'binary-tree' How to remove the ModuleNotFoundError: No module named 'binary-tree' error? Thanks   Hi, In your python environment
Binary Search on array
Binary Search on array  What requirement is placed on an array, so that binary search may be used to locate an entry? ? The array elements must form a heap. ? The array must have at least 2 entries. ? The array must
ModuleNotFoundError: No module named 'binary_tree_dict_mod'
ModuleNotFoundError: No module named 'binary_tree_dict_mod'  Hi...: No module named 'binary_tree_dict_mod' How to remove the ModuleNotFoundError: No module named 'binary_tree_dict_mod' error? Thanks   Hi
JAVA: Recusrion, Binary Search
JAVA: Recusrion, Binary Search  I want to learn about Binary Search... it using a recursive implementation of Binary Search. For the cases when more than one result can be returned, modify Binary Search to return all the elements
ModuleNotFoundError: No module named 'binary-search'
ModuleNotFoundError: No module named 'binary-search'  Hi, My... 'binary-search' How to remove the ModuleNotFoundError: No module named 'binary-search' error? Thanks   Hi, In your python
JavaScript Array Binary Search
JavaScript Array Binary Search       The JavaScript Binary Search becomes very useful in case of large Arrays.  The Binary Search algorithm is used to  handle
Which of the following statements are true with respect to binary search
Which of the following statements are true with respect to binary search  Which of the following statements are true with respect to binary search? 1. The array need not be sorted for carrying out binary search 2. Binary search
ModuleNotFoundError: No module named 'binary-file-search'
ModuleNotFoundError: No module named 'binary-file-search'  Hi, My... named 'binary-file-search' How to remove the ModuleNotFoundError: No module named 'binary-file-search' error? Thanks   Hi, In your
How to using Binary Search Array Java ?
How to using Binary Search Array Java ?  Hi, I am beginners in Java... functions. The problem is that how to use binary search array in Java. Please give any online reference show that i will implement the binary search array in Java
Building a Binary Tree using std::map, std:set
Building a Binary Tree using std::map, std:set  Hi, can someone... a simple binary tree? I do not seem to understand how these 2 containers can be used to represent a binary tree because I can't help but to see that map and set act
ModuleNotFoundError: No module named 'tree-edge-search'
ModuleNotFoundError: No module named 'tree-edge-search'  Hi, My... named 'tree-edge-search' How to remove the ModuleNotFoundError: No module named 'tree-edge-search' error? Thanks   Hi, In your
Binary Search in Java
Binary Search in Java is used to search an element from an array. Programmers opt for Binary search over linear search when it comes to large numbers. It can... the answer "Not Found". Following is the example of Binary Search in Java: import
Retrive data from database and perform binary tree operations on that data in jsp or java
Retrive data from database and perform binary tree operations on that data... Left and Subbinary tree node count. Check balanced tree of particular Id ,unbalaced tree node and so on. Please Help me
binary
binary  Hi I want to write a program in pascal that ask a user to input a decimal number and then return its binary equivalent in the minimum number of bits required to repesent the number. Thks
Tree
Tree  print("code sample");1) Write Java code to create the following tree using new Tree state- ments: 1

Ads