二叉树的前序遍历中序遍历后序遍历

淩亂°似流年 2022-12-25 13:53 184阅读 0赞

树的遍历一般是从左至右，按照根结点在前中后的顺序分为了前序遍历，中序遍历和后序遍历

前序遍历:   根结点 --》左节点--》右节点

中序遍历:   左节点--》根结点--》右节点

后序遍历:   左节点--》右节点--》根节点

下面写了一个遍历的demo

public class BinaryTree {
    
        private Node root;
    
        public boolean insert(int data){
            Node newNode = new Node(data);
            if(root == null){
                root = newNode;
                return true;
            }
            Node current = root;
            Node parentNode = null;
            while (current != null){
                parentNode = current;
                if(current.data > data){
                    current = current.left;
                    if(current == null){
                        parentNode.left = newNode;
                        return true;
                    }
                }else {
                    current = current.right;
                    if(current == null){
                        parentNode.right = newNode;
                        return true;
                    }
                }
            }
            return false;
        }
    
        /**
         * 中序遍历
         * @param current
         */
        public void inOrder(Node current){
            if(current != null){
                inOrder(current.left);
                System.out.println(current.data);
                inOrder(current.right);
            }
        }
    
        /**
         * 前序遍历
         * @param current
         */
        public void preOrder(Node current){
            if(current != null){
                System.out.println(current.data);
                preOrder(current.left);
                preOrder(current.right);
            }
        }
    
        public static void main(String[] args) {
            BinaryTree binaryTree = new BinaryTree();
            binaryTree.insert(9);
            binaryTree.insert(12);
            binaryTree.insert(32);
            binaryTree.insert(13);
            binaryTree.insert(24);
            binaryTree.insert(3);
            binaryTree.insert(1);
            binaryTree.insert(2);
            binaryTree.insert(7);
            binaryTree.insert(312);
            System.out.println("前序遍历");
            binaryTree.preOrder(binaryTree.root);
            System.out.println("中序遍历");
            binaryTree.inOrder(binaryTree.root);
            System.out.println("后序遍历");
            binaryTree.postOrder(binaryTree.root);
        }
    
        /**
         * 后序遍历
         * @param current
         */
        public void postOrder(Node current){
            if(current != null){
                postOrder(current.left);
                postOrder(current.right);
                System.out.println(current.data);
            }
        }
    
        private class Node{
            private int data;
    
            private Node left;
    
            private Node right;
    
            public Node(int data, Node left, Node right) {
                this.data = data;
                this.left = left;
                this.right = right;
            }
    
            public Node(int data){
                this.data = data;
            }
    
            public int getValue() {
                return data;
            }
    
            public Node setValue(int data) {
                this.data = data;
                return this;
            }
    
            public Node getLeft() {
                return left;
            }
    
            public Node setLeft(Node left) {
                this.left = left;
                return this;
            }
    
            public Node getRight() {
                return right;
            }
    
            public Node setRight(Node right) {
                this.right = right;
                return this;
            }
        }
    }

可以看到排序二叉树的中序遍历就可以用来排序了