二叉树遍历

一、原文链接

http://blog.csdn.net/gfj0814/article/details/51637696
原文写的挺好的，简洁易懂。于是借鉴过来放在自己的博客下方便自己整理与记录。如有侵权，必将第一时间删除。

二、二叉树特点

1、第i层至多有2^(i-1)个节点(i >= 1)
2、深度为k的二叉树至多有2^(k-1)个节点(k>=1)
3、父节点记为parent，则子节点位置 左节点 = parent * 2 + 1 右节点 = parent * 2 + 2
4、子节点记为child，则父节点位置 = (child - 1) / 2
5、对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1
6、具有n个节点的完全二叉树的深度为n/2

三、二叉树遍历

1、初始化操作

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Aria on 2017/8/31.
 */
public class Tree {

    Node root;
    List<Node> list = new ArrayList<>();

    public void init(){
        Node x=new Node("X",null,null);
        Node y=new Node("Y",null,null);
        Node d=new Node("d",x,y);
        Node e=new Node("e",null,null);
        Node f=new Node("f",null,null);
        Node c=new Node("c",e,f);
        Node b=new Node("b",d,null);
        Node a=new Node("a",b,c);
        root =a;
    }

    public Tree(){
        init();
    }

    static class Node{
        Node left;
        Node right;
        String val;

        public Node(String val,Node left,Node right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

2、前序遍历

    public void preOrder(Node node){
        list.add(node);

        if (node.left != null)
            preOrder(node.left);
        if (node.right != null)
            preOrder(node.right);
    }

3、中序遍历

    public void inOrder(Node node){
        if (node.left != null)
            inOrder(node.left);
        list.add(node);
        if (node.right != null)
            inOrder(node.right);
    }

4、后序遍历

    public void postOrder(Node node){
        if (node.left != null)
            postOrder(node.left);
        if (node.right != null)
            postOrder(node.right);
        list.add(node);
    }

5、获取树的深度

    public int getTreeDepth(Node node){
        if (node.left == null && node.right == null)
            return 1;
        int left = 0,right = 0;
        if (node.left != null)
            left = getTreeDepth(node.left);

        if (node.right != null)
            right = getTreeDepth(node.right);
        return left > right ? left + 1: right +1;
    }