漫画算法）Note4）二叉树的实现与遍历

参考《漫画算法》P79，着重理解递归思想!

package com.hzc.tree;

import java.util.Arrays;
import java.util.linkedList;


public class Iterable {
    public static void main(String[] args) {
        
        linkedList inputList = new linkedList(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历:");
        preOrderTraveral(treeNode);
        System.out.println("中序遍历:");
        inOrderTraveral(treeNode);
        System.out.println("后续遍历:");
        postOrderTraveral(treeNode);
    }

    
    private static class TreeNode{//每个节点都有自己的值以及左叶子节点和右叶子节点
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data){
            this.data = data;
        }
    }

    
    public static TreeNode createBinaryTree(linkedList inputList){
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();//第一个数据作为根节点
        if (data != null){
            node = new TreeNode(data);//每次递归都会依次取出第一个根节点然后往下走,直到叶子节点,就这样一步一步构建二叉树
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    
    public static void preOrderTraveral(TreeNode node){
        if (node == null){
            return;//递归的结束标志
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

    
    public static void inOrderTraveral(TreeNode node){
        if (node == null){
            return;//递归的结束标志
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    
    public static void postOrderTraveral(TreeNode node){
        if (node == null){
            return;//递归的结束标志
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data
        );
    }
}