具有遍历的 java 中的二叉搜索树实现

Question

我已经使用插入和遍历方法实现了二叉搜索树，但没有得到正确的预购和后序输出，我以正确的顺序获得inOrder。有人可以告诉我哪里错了。

我在纸上尝试了同样的例子，但预购和后购并不相同。

这是我的代码

节点类

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书。