Реализация двоичного дерева поиска в java с обходом

Question

Я реализовал двоичное дерево поиска со способом вставки и обхода, но не получаю корректного вывода для PreOrder и Postorder, я получаю inOrder в правильном порядке. Может кто-нибудь, скажите мне, где это неправильно.

Я попробовал такой же пример на бумаге, но PreOrder и PostOrder не то же самое.

Вот мой код

Node Class

package com.BSTTest; 

public class Node implements Comparable<Node> { 
    private int data; 
    private Node leftChild; 
    private Node rightChild; 

    public Node(int data) { 
     this(data, null, null); 
    } 

    public Node(int data, Node leftChild, Node rightChild) { 
     this.data = data; 
     this.leftChild = leftChild; 
     this.rightChild = rightChild; 

    } 

    public int getData() { 
     return data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public Node getLeftChild() { 
     return leftChild; 
    } 

    public void setLeftChild(Node leftChild) { 
     this.leftChild = leftChild; 
    } 

    public Node getRightChild() { 
     return rightChild; 
    } 

    public void setRightChild(Node rightChild) { 
     this.rightChild = rightChild; 
    } 

    public int compareTo(Node o) { 
     return Integer.compare(this.data, o.getData()); 
    } 
} 

Дерево Класс

package com.BSTTest; 

import com.BSTTest.Node; 

public class Tree { 
    private Node root = null; 

    public Node getRoot() { 
     return root; 
    } 
    //Inserting data**strong text** 
    public void insertData(int data) { 
     Node node = new Node(data, null, null); 
     if (root == null) { 
      root = node; 
     } else { 
      insert(node, root); 
     } 
    } 
    //Helper method for insert 
    private void insert(Node node, Node currNode) { 
     if (node.compareTo(currNode) < 0) { 
      if (currNode.getLeftChild() == null) { 
       currNode.setLeftChild(node); 
      } else { 
       insert(node, currNode.getLeftChild()); 
      } 
     } else { 

      if (currNode.getRightChild() == null) { 
       currNode.setRightChild(node); 
      } else { 
       insert(node, currNode.getRightChild()); 
      } 
     } 
    } 

    public void printInorder() { 
     printInOrderRec(root); 
     System.out.println(""); 
    } 


     //Helper method to recursively print the contents in an inorder way 

    private void printInOrderRec(Node currRoot) { 
     if (currRoot == null) { 
      return; 
     } 
     printInOrderRec(currRoot.getLeftChild()); 
     System.out.print(currRoot.getData() + ", "); 
     printInOrderRec(currRoot.getRightChild()); 
    } 

    public void printPreorder() { 
     printPreOrderRec(root); 
     System.out.println(""); 
    } 


    // Helper method for PreOrder Traversal recursively 

    private void printPreOrderRec(Node currRoot) { 
     if (currRoot == null) { 
      return; 
     } 
     System.out.print(currRoot.getData() + ", "); 
     printPreOrderRec(currRoot.getLeftChild()); 
     printPreOrderRec(currRoot.getRightChild()); 
    } 

    public void printPostorder() { 
     printPostOrderRec(root); 
     System.out.println(""); 
    } 

    /** 
    * Helper method for PostOrder method to recursively print the content 
    */ 
    private void printPostOrderRec(Node currRoot) { 
     if (currRoot == null) { 
      return; 
     } 
     printPostOrderRec(currRoot.getLeftChild()); 
     printPostOrderRec(currRoot.getRightChild()); 
     System.out.print(currRoot.getData() + ", "); 
    } 
    //Main Mthod 
    public static void main(String[] args) { 
     Tree obj = new Tree(); 
     //Inserting data 
     obj.insertData(3); 
     obj.insertData(5); 
     obj.insertData(6); 
     obj.insertData(2); 
     obj.insertData(4); 
     obj.insertData(1); 
     obj.insertData(0); 

     //printing content in Inorder way 
     System.out.println("Inorder traversal"); 
     obj.printInorder(); 

     //printing content in Inorder way 
     System.out.println("Preorder Traversal"); 
     obj.printPreorder(); 

     //printing content in Inorder way 
     System.out.println("Postorder Traversal"); 
     obj.printPostorder(); 
    } 
} 

Answer 1

Посмотрите мой друг, ваш код абсолютно нормально, как выходы вы упомянули абсолютно правильно.

Я думаю, что вы не поняли концепцию дерева двоичного поиска правильно.

Вы правы, 3 - это корневой узел, но вы ошибаетесь, говоря, что 1 - его левый ребенок.

Первое значение, которое появляется после того, как 3 и меньше 3 2, поэтому 2 оставляют ребенка от 3, а не 1

Обратитесь к Cormenn книге, если до сих пор существует путаница.