二叉树（一）

树是在实际编程中经常遇到的数据结构，它的逻辑很简单：除了根节点以外，每个节点只有一个父节点，根节点没有父节点;除了叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。

树的前、中、后序遍历是比较基础，同时也是必须要掌握的几个点，它们分别有递归、和非递归的解法。递归相对简单一点，非递归相对复杂一些。

下面用Java语言分别实现树的前、中、后序递归遍历，另外这边拓展（递归创建二叉树、求树的深度）两个解法。

package BiTree;

import java.util.Scanner;

/**
 * @author zyh
 * @create 19-3-9 下午12:06
 */
public class BiTree {

    private Object data;
    private BiTree lChild;
    private BiTree rChild;

    public BiTree(Object data,BiTree lChild,BiTree rChild){
        this.data = data;
        this.lChild = lChild;
        this.rChild = rChild;
    }

    /**
     * 中序遍历二叉数 左根右
     * @param tree
     */
    public static void inOrderTraverse(BiTree tree){
        if(tree != null) {
            inOrderTraverse(tree.lChild);
            System.out.print(tree.data);
            inOrderTraverse(tree.rChild);
        }
    }

    /**
     * 后续遍历二叉数 左右根
     * @param tree
     */
    public static void afterOrderTraverse(BiTree tree){
        if(tree != null){
            afterOrderTraverse(tree.lChild);
            afterOrderTraverse(tree.rChild);
            System.out.print(tree.data);
        }
    }

    /**
     * 先须遍历二叉数 根左右
     * @param tree
     */
    public static void preOrderTraverse(BiTree tree){
        if(tree != null){
            System.out.print(tree.data);
            preOrderTraverse(tree.lChild);
            preOrderTraverse(tree.rChild);
        }
    }

    /**
     * 递归创建二叉数
     * @param scanner
     * @return
     * @throws Exception
     */
    public static BiTree createBiTree(Scanner scanner) throws Exception{
        int data = scanner.nextInt();
        if(data == 0){
            return null;
        }else{
            return new BiTree(data,createBiTree(scanner),createBiTree(scanner));
        }
    }

    /**
     * 求二叉数的深度
     * @param tree
     * @return
     */
    public static Integer depth(BiTree tree){
        if(tree == null){
            return 0;
        }else{
            Integer m = depth(tree.lChild);
            Integer n = depth(tree.rChild);
            if(m > n){
                return m+1;
            }else{
                return n+1;
            }
        }

    }

    public static void main(String []args)  throws Exception{
        BiTree tree = createBiTree(new Scanner(System.in));
        System.out.println();
        System.out.println("--------------递归：中序遍历二叉数------------------");
        inOrderTraverse(tree);
        System.out.println();
        System.out.println("--------------递归：先序遍历二叉数------------------");
        preOrderTraverse(tree);
        System.out.println();
        System.out.println("--------------递归：后序遍历二叉数------------------");
        afterOrderTraverse(tree);

        System.out.println();
        System.out.println("--------------递归：求二叉树的深度------------------");
        System.out.println(depth(tree));
    }

}

参考:参考: Data Structure (2nd Edition) 第五章http://book.knowsky.com/book_1030305.htm