二叉树的预排序，后排序和Java排序 [英] Binary Tree preorder, postorder and inorder with java

问题描述

我正在学习计算机科学的第二学期，在我的数据结构课程中，我们看到具有递归的二叉树.我们必须基于以下Java代码使用递归进行预购后继和有序遍历:

I am studying my second semester in computer science, in my data structures class we are seeing binary trees with recursion. We have to make the preorder postorder and inorder traversal with recursion based on the following Java code:

    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";
         */

    }
}

有人可以请我解释一下这些遍历如何工作以及如何编码吗?

Can some one please explain me how these trasversals work and how to code them?

推荐答案

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

There are some awsome binary tree visualizations online so you can understand it a little better but here are some images I use.

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);
    }
}

这篇关于二叉树的预排序，后排序和Java排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！