이 진 트 리 의 생 성, 옮 겨 다 니 기 (선 순, 중 순, 후 순, 차원) (재 귀 와 비 재 귀) - 자바 실현

나무 란 무엇 인가?이 진 트 리 는 무엇 입 니까?트 리: 뿌리 노드 를 제외 한 모든 노드 가 있 고 부모 노드 만 있 으 며 뿌리 노드 는 부모 노드 가 없습니다.잎 결점 을 제외 한 모든 노드 는 하나 이상 의 키 노드 가 있 고 잎 결점 에는 하위 노드 가 없다.이 진 트 리: 나무의 특수 한 구조 로 이 진 트 리 에서 각 노드 는 최대 두 개의 노드 만 있 을 수 있 습 니 다.이 진 트 리 의 옮 겨 다 니 는 방식: 1. 먼저 옮 겨 다 니 기 (재 귀, 비 재 귀);2. 중간 순서 로 옮 겨 다 니 기 (재 귀, 비 재 귀);3. 뒷 순 서 를 옮 겨 다 니 기 (재 귀, 비 재 귀);4. 층 차 를 옮 겨 다 닌 다.
트 리 만 들 기, 코드 옮 겨 다 니 기:

public class BinaryTree {

    private static class Node{
        public E value; //   
        public Node left; //   
        public Node right;//   

        public Node(E value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public static List> nodeList = null;//          
    /**
     *     
     * @param length
     * @return
     */
    public int[] createArray(int length){
        int[] array = new int[length];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int)(Math.random() * 100);
        }
        return array;
    }

    /**
     *      
     */
    public void createBinaryTree(int nodeNum){
        nodeList = new ArrayList>();
        int[] array = createArray(nodeNum);
        for(int i : array){
            System.out.print(i + " ");
        }
        System.out.println();
        for (int i = 0; i < array.length; i++) {
             Node temp = new Node(array[i]);
             nodeList.add(temp);
        }
        for (int parentIndex = 0; parentIndex < array.length/2 - 1; parentIndex++) {
            //   
            Node parentNode = nodeList.get(parentIndex);
            //   
            parentNode.left = nodeList.get(parentIndex * 2 + 1);
            //   
            parentNode.right = nodeList.get(parentIndex * 2 + 2);

            int lastParentIndex = array.length/2 - 1;
            Node lastParentNode = nodeList.get(lastParentIndex);
            lastParentNode.left = nodeList.get(lastParentIndex * 2 + 1);
            //       ，            
            if (array.length % 2 == 1) {
                lastParentNode.right = nodeList.get(lastParentIndex * 2 + 2);
            }
        }

    }

    /**
     *        （  ）
     * @param parentNode
     */
    public void BinaryTreePreOrder(Node parentNode){
        if (parentNode == null) {
            return;
        }
        System.out.print(parentNode.value + " ");
        BinaryTreePreOrder(parentNode.left);
        BinaryTreePreOrder(parentNode.right);
    }
    /**
     *        （  ）
     * @param rootNode
     */
    public void BinaryTreePreOrder_loop(Node rootNode){
        Stack> stack = new Stack>();
        Node cur = rootNode;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                System.out.print(cur.value + " ");
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
    }

    /**
     *        （  ）
     * @param parentNode
     */
    public void BinaryTreeMidOrder(Node parentNode){
        if (parentNode == null) {
            return;
        }
        BinaryTreeMidOrder(parentNode.left);
        System.out.print(parentNode.value + " ");
        BinaryTreeMidOrder(parentNode.right);
    }

    /**
     *        （  ）
     * @param rootNode
     */
    public void BinaryTreeMidOrder_loop(Node rootNode){
        Stack> stack = new Stack>();
        Node cur = rootNode;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
    }
    /**
     *        （  ）
     * @param parentNode
     */
    public void BinaryTreePostOrder(Node parentNode){
        if (parentNode == null) {
            return;
        }
        BinaryTreePostOrder(parentNode.left);
        BinaryTreePostOrder(parentNode.right);
        System.out.print(parentNode.value + " ");
    }

    /**
     *        （   ）
     *        ，    
     * @param rootNode
     */
    public void BinaryTreePostOrder_loop(Node rootNode){
        Stack> stack = new Stack>();
        //  map           
        Map, Boolean> nodeMap = new HashMap, Boolean>();
        stack.push(rootNode);
        while(!stack.isEmpty()){
            Node temp = stack.peek();
            //         
            if (temp.left != null && !nodeMap.containsKey(temp.left)) {
                temp = temp.left;
                while(temp != null){
                    stack.push(temp);
                    temp = temp.left;
                }
                continue;
            }
            //     
            if (temp.right != null && !nodeMap.containsKey(temp.right)) {
                stack.push(temp.right);
                continue;
            }
            Node cur = stack.pop();
            System.out.print(cur.value + " ");
            nodeMap.put(cur, true);
        }
    }

    /**
     *        
     * @param rootNode
     */
    public void BinaryTreeLevelOrder(Node rootNode){
        //         
        Queue> queue = new LinkedList>();
        queue.add(rootNode);
        while(!queue.isEmpty()){
            Node parentNode = queue.poll();
            System.out.print(parentNode.value + " ");
            if (parentNode.left != null) {
                queue.add(parentNode.left);
            }
            if (parentNode.right != null) {
                queue.add(parentNode.right);
            }
        }
    }
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        System.out.println("     ：");
        tree.createBinaryTree(11);
        Node rootNode = nodeList.get(0);
        System.out.println("    （  ）：");
        tree.BinaryTreePreOrder(rootNode);
        System.out.println();
        System.out.println("    （   ）：");
        tree.BinaryTreePreOrder_loop(rootNode);
        System.out.println();
        System.out.println("    （  ）：");
        tree.BinaryTreeMidOrder(rootNode);
        System.out.println();
        System.out.println("    （   ）：");
        tree.BinaryTreeMidOrder_loop(rootNode);
        System.out.println();
        System.out.println("    （  ）：");
        tree.BinaryTreePostOrder(rootNode);
        System.out.println();
        System.out.println("    （   ）：");
        tree.BinaryTreePostOrder_loop(rootNode);
        System.out.println();
        System.out.println("    ：");
        tree.BinaryTreeLevelOrder(rootNode);
    }
}

테스트 결과:

     ：
39 21 69 6 78 21 83 53 69 52 85 
    （  ）：
39 21 6 53 69 78 52 85 69 21 83 
    （   ）：
39 21 6 53 69 78 52 85 69 21 83 
    （  ）：
53 6 69 21 52 78 85 39 21 69 83 
    （   ）：
53 6 69 21 52 78 85 39 21 69 83 
    （  ）：
53 69 6 52 85 78 21 21 83 69 39 
    （   ）：
53 69 6 52 85 78 21 21 83 69 39 
    ：
39 21 69 6 78 21 83 53 69 52 85