Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.6k views
in Technique[技术] by (71.8m points)

java - how to create binary search tree 2d model from these codes?

hi im new to codings and i have to print my binary search tree in a 2d model but this codes only print the orders of number in order(left-root-right) such as when i insert 10, 9, 11, 8, it will print inorder (left root right) = 8,9,10,11. what method or codes should i add to create a 2d tree here. sorry idk how to properly put the codes here just look at it like it is only a one code only.

 class binarySearchTree { 

   class Node { 
    int key; 
    Node left, right; 
    int data;
    public Node(int data){ 
        key = data; 
        left = right = null; 
    } 
} 
// BST root node 
Node root; 

   // Constructor for BST =>initial empty tree
   binarySearchTree(){ 
    root = null; 
} 
//delete a node from BST
void deleteKey(int key) { 
    root = delete_Recursive(root, key); 
} 

//recursive delete function
Node delete_Recursive(Node root, int key)  { 
    //tree is empty
    if (root == null)  return root; 

    //traverse the tree
    if (key < root.key)     //traverse left subtree 
        root.left = delete_Recursive(root.left, key); 
    else if (key > root.key)  //traverse right subtree
        root.right = delete_Recursive(root.right, key); 
    else  { 
        // node contains only one child
        if (root.left == null) 
            return root.right; 
        else if (root.right == null) 
            return root.left; 

        // node has two children; 
        //get inorder successor (min value in the right subtree) 
        root.key = minValue(root.right); 

        // Delete the inorder successor 
        root.right = delete_Recursive(root.right, root.key); 
    } 
    return root; 
} 

int minValue(Node root)  { 
    //initially minval = root
    int minval = root.key; 
    //find minval
    while (root.left != null)  { 
        minval = root.left.key; 
        root = root.left; 
    } 
    return minval; 
} 

// insert a node in BST 
void insert(int key)  { 
    root = insert_Recursive(root, key); 
} 

//recursive insert function
Node insert_Recursive(Node root, int key) { 
      //tree is empty
    if (root == null) { 
        root = new Node(key); 
        return root; 
    } 
    //traverse the tree
    if (key < root.key)     //insert in the left subtree
        root.left = insert_Recursive(root.left, key); 
    else if (key > root.key)    //insert in the right subtree
        root.right = insert_Recursive(root.right, key); 
      // return pointer
    return root; 
} 


void inorder() { 
    inorder_Recursive(root); 
} 

// recursively traverse the BST  
void inorder_Recursive(Node root) { 
    if (root != null) { 
        inorder_Recursive(root.left); 
        System.out.print(root.key + " x "); 
        inorder_Recursive(root.right); 
    } 
} 
 
  
 //PostOrder Traversal - Left:Right:rootNode (LRn)
void postOrder(Node node)  { 
    if (node == null) 
        return; 

    // first traverse left subtree recursively 
    postOrder(node.left); 

    // then traverse right subtree recursively 
    postOrder(node.right); 

    // now process root node 
    System.out.print(node.key + " "); 
} 
     // InOrder Traversal - Left:rootNode:Right (LnR) 
void inOrder(Node node)  { 
    if (node == null) 
        return; 
    //first traverse left subtree recursively
    inOrder(node.left); 

    //then go for root node
    System.out.print(node.key + " "); 

    //next traverse right subtree recursively
    inOrder(node.right); 
} 

   //PreOrder Traversal - rootNode:Left:Right (nLR)
void preOrder(Node node)  { 
    if (node == null) 
        return; 

    //first print root node first
    System.out.print(node.key + " "); 
    // then traverse left subtree recursively
    preOrder(node.left); 
    // next traverse right subtree recursively
    preOrder(node.right); 
} 
   // Wrappers for recursive functions 
void postOrder_traversal()  {    
    postOrder(root);  } 
void inOrder_traversal() { 
    inOrder(root);   } 
void preOrder_traversal() {
    preOrder(root);  } 

 }

here i found this codes in stackoverflow, i want te output like this, i can use this but i dont know how can i make this as user input for the data and make it insert the integer into a tree not this manually inserted of the integer. thankyou very much to whoever put effort to understand my question and my situation as newbie.

     import java.util.ArrayList;
     import java.util.Collections;
    import java.util.List;

    public class BTreePrinterTest {

         private static Node<Integer> test2() {

    Node<Integer> root = new Node<Integer>(2);
    Node<Integer> n11 = new Node<Integer>(3);
    Node<Integer> n12 = new Node<Integer>(5);
    Node<Integer> n21 = new Node<Integer>(2);
    Node<Integer> n22 = new Node<Integer>(6);
    Node<Integer> n23 = new Node<Integer>(9);
    Node<Integer> n31 = new Node<Integer>(5);
   
    
    root.left = n11;
    root.right = n12;
    
    n11.left = n21;
    n11.right = n22;

    
    n12.left = n23;
    n12.right = n31;

    return root;
}

public static void main(String[] args) {

    
    BTreePrinter.printNode(test2());

   }
   }

   class Node<T extends Comparable<?>> {
Node<T> left, right;
T data;

public Node(T data) {
    this.data = data;
}
  }

 class BTreePrinter {

public static <T extends Comparable<?>> void printNode(Node<T> root) {
    int maxLevel = BTreePrinter.maxLevel(root);

    printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}

private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
    if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
        return;

    int floor = maxLevel - level;
    int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
    int firstSpaces = (int) Math.pow(2, (floor)) - 1;
    int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

    BTreePrinter.printWhitespaces(firstSpaces);

    List<Node<T>> newNodes = new ArrayList<Node<T>>();
    for (Node<T> node : nodes) {
        if (node != null) {
            System.out.print(node.data);
            newNodes.add(node.left);
            newNodes.add(node.right);
        } else {
            newNodes.add(null);
            newNodes.add(null);
            System.out.print(" ");
        }

        BTreePrinter.printWhitespaces(betweenSpaces);
    }
    System.out.println("");

    for (int i = 1; i <= endgeLines; i++) {
        for (int j = 0; j < nodes.size(); j++) {
            BTreePrinter.printWhitespaces(firstSpaces - i);
            if (nodes.get(j) == null) {
                BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                continue;
            }

            if (nodes.get(j).left != null)
                System.out.print("/");
            else
                BTreePrinter.printWhitespaces(1);

            BTreePrinter.printWhitespaces(i + i - 1);

            if (nodes.get(j).right != null)
                System.out.print("\");
            else
                BTreePrinter.printWhitespaces(1);

            BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
        }

        System.out.println("");
    }

    printNodeInternal(newNodes, level + 1, maxLevel);
}

private static void printWhitespaces(int count) {
    for (int i = 0; i < count; i++)
        System.out.print(" ");
}

private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
    if (node == null)
        return 0;

    return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
}

private static <T> boolean isAllElementsNull(List<T> list) {
    for (Object object : list) {
        if (object != null)
            return false;
    }

    return true;
}

  }

btw im learning this by my own, i tried merging the two codes but it gives me error i cant fix it.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I should have not made the whole exercise for you, so please try to understand the code. Tell me if something is not clear for you.

public static void main(String[] args) throws IOException {
    System.out.println("Write your input");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String lines = br.readLine();    
    binarySearchTree b = new binarySearchTree();
    b.input(lines);
    b.print();
}

These functions go to binarySearchTree.

    protected void printRecursive(Node node, int depth) {
        System.out.println("");
        for(int i = 0; i<depth; i++) {
            System.out.print("  ");
        }
        System.out.print(node.key);
        if(node.left != null) {
            printRecursive(node.left, depth + 1);
        }
        if(node.right != null) {
            printRecursive(node.right, depth + 1); 
        }
    }
    public void input(String s) throws IOException {
        String[] strs = s.trim().split("\s+");
                
        for (int i = 0; i < strs.length; i++) {
            insert(Integer.parseInt(strs[i]));
        }
    }

Also i used this answer in my code.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...