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

Question

我已经使用插入和遍历方法实现了一个二叉搜索树，但是我没有得到 PreOrder 和 Postorder 的正确输出，我得到的 inOrder 的顺序是正确的。谁能告诉我哪里错了。

我在纸上尝试了相同的示例，但 PreOrder 和 PostOrder 不一样。

这是我的代码

节点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());
    }
}

树Class

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是它的左边是错误的child。

3之后出现的第一个小于3的值是2，所以2剩下child of 3而不是1

如果还有不明白的地方，请参考 Cormenn 的书。

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

Binary search tree implementation in java with traversal

java

algorithm

data-structures

binary-search-tree

节点Class

树Class