java - java的二叉树前序、后序和中序

Question

我正在学习计算机科学的第二学期，在我的数据结构课上，我们看到了带有递归的二叉树。我们要基于以下Java代码进行递归的前序后序和中序遍历:

    public class BinaryTree {

    Node root;

    public void addNode(int key, String name) {
        // Create a new Node and initialize it
        Node newNode = new Node(key, name);
        // If there is no root this becomes root
        if (root == null) {
            root = newNode;
        } else {
            // Set root as the Node we will start
            // with as we traverse the tree
            Node focusNode = root;
            // Future parent for our new Node
            Node parent;

            while (true) {
                // root is the top parent so we start
                // there
                parent = focusNode;

                // Check if the new node should go on
                // the left side of the parent node

                if (key < focusNode.key) {

                    // Switch focus to the left child

                    focusNode = focusNode.leftChild;

                    // If the left child has no children

                    if (focusNode == null) {

                            // then place the new node on the left of it

                            parent.leftChild = newNode;
                            return; // All Done

                    }

                } else { // If we get here put the node on the right
                    focusNode = focusNode.rightChild;

                    // If the right child has no children

                    if (focusNode == null) {

                            // then place the new node on the right of it

                            parent.rightChild = newNode;
                            return; // All Done
                    }
                }
            }
        }
    }

    // Traversals recursion methods

    public void inOrderTraverseTree(Node focusNode) {

    }

    public void preorderTraverseTree(Node focusNode) {

    }

    public void postOrderTraverseTree(Node focusNode) {

    }

    //******************************************************************

    public Node findNode(int key) {
        // Start at the top of the tree
        Node focusNode = root;
        // While we haven't found the Node
        // keep looking
        while (focusNode.key != key) {
            // If we should search to the left
            if (key < focusNode.key) {
                    // Shift the focus Node to the left child
                    focusNode = focusNode.leftChild;
            } else {
                    // Shift the focus Node to the right child
                    focusNode = focusNode.rightChild;
            }
            // The node wasn't found
            if (focusNode == null)
                    return null;
        }
        return focusNode;
    }

    public static void main(String[] args) {
        BinaryTree theTree = new BinaryTree();
        theTree.addNode(50, "Boss");
        theTree.addNode(25, "Vice President");
        theTree.addNode(15, "Office Manager");
        theTree.addNode(30, "Secretary");
        theTree.addNode(75, "Sales Manager");
        theTree.addNode(85, "Salesman 1");

        // Different ways to traverse binary trees
         theTree.inOrderTraverseTree(theTree.root);
         theTree.preorderTraverseTree(theTree.root);
         theTree.postOrderTraverseTree(theTree.root);
        // Find the node with key 75
        System.out.println("\nNode with the key 75");
        System.out.println(theTree.findNode(75));
    }
}

class Node {
    int key;
    String name;
    Node leftChild;
    Node rightChild;

    Node(int key, String name) {
        this.key = key;
        this.name = name;
    }

    public String toString() {
        return name + " has the key " + key;
        /*
         * return name + " has the key " + key + "\nLeft Child: " + leftChild +
         * "\nRight Child: " + rightChild + "\n";
         */

    }
}

有人可以解释一下这些遍历是如何工作的以及如何编码吗？

Answer 1

网上有一些很棒的二叉树可视化，因此您可以更好地理解它，但这里是我使用的一些图像。

public void inOrderTraverseTree(Node focusNode) {
    if (focusNode != null) {
        // Traverse the left node
        inOrderTraverseTree(focusNode.leftChild);
        // Visit the currently focused on node
        System.out.println(focusNode);
        // Traverse the right node
        inOrderTraverseTree(focusNode.rightChild);
    }
}

public void postOrderTraverseTree(Node focusNode) {
    if (focusNode != null) {
        postOrderTraverseTree(focusNode.leftChild);
        postOrderTraverseTree(focusNode.rightChild);

        System.out.println(focusNode);
    }
}

public void preorderTraverseTree(Node focusNode) {
    if (focusNode != null) {
        System.out.println(focusNode);

        preorderTraverseTree(focusNode.leftChild);
        preorderTraverseTree(focusNode.rightChild);
    }
}