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, so the tree must have a to l as left child, root as m and right child as n-z, am i right? how do i do it?

View Answers

October 24, 2011 at 12:25 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);
  }
}









Related Tutorials/Questions & Answers:
How to create binary search tree using an array?
binary search tree
Advertisements
binary search tree
How to using Binary Search Array Java ?
Binary Search Tree
Binary Search Tree
binary search tree
Binary search tree (insertion) urgent!!
How to create arrays in JavaScript?
binary search tree from text file
Building a Binary Tree using std::map, std:set
Java Array Binary Search example
binary tree
Binary tree
Binary tree
binary tree
How to Append Arrays in PHP
Binary Search on array
how to compare 2 arrays using java?
Binary Search - Java Beginners
binary search program
binary search program
binary search program
binary search program
binary search program
create arrays in JavaScript
How do I use JGraph to create a MST(minimum spanning tree) using java?
JAVA: Recusrion, Binary Search
Binary Search in Java
ModuleNotFoundError: No module named 'binary-tree'
how to create using jsp
ModuleNotFoundError: No module named 'binary-search'
how to covert JPG format to Binary formart using java code..
JavaScript Array Binary Search
binary search - Java Beginners
ModuleNotFoundError: No module named 'binary_tree_dict_mod'
Binary Search!!! - Java Beginners
ModuleNotFoundError: No module named 'binary-file-search'
How to perform search using AJAX?
How to Create Instance using PHP
Java binary tree code
php array binary search
Java binary tree insert
how to search data in xml files using php
Which of the following statements are true with respect to binary search
how to write a program to search a record using mvc2
How to write a search functionality using javascript/jquery
Java Convert decimal to binary using Stacks
how to create exce sheet using java
How to create primary key using hibernate?

Ads