树是一种非线性结构。树上的任意节点，就只有一个父节点，可以有多个子节点。

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶子节点或终端节点：度为0的节点称为叶子节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
根结点：一棵树中，没有双亲结点的结点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层数；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
堂兄弟节点：双亲在同一层的节点互为堂兄弟：
节点的祖先：从根到该节点所经分支上的所有节点（不是一个节点，而是一组节点）；
子孙：以某节点为根的子树中的任一节点都称为该节点的子孙；
森林：由 M ( M >= 0 ) 棵互不相交的树的集合称为森林；

文件系统管理（目录和文件的管理）

树的度为 2 ，就叫做二叉树。
1、每个节点最多有两棵子树，即 二叉树不存在度大于 2 的节点；
2、二叉树的子树有左右之分，其子树的次序不能颠倒（ 颠倒之后就是不同的树了 ），因此二叉树是有序树。

1、满二叉树：即每一层的节点都达到了最大值，每一个节点的度要么是 2 要么是 0 。
2、完全二叉树：由满二叉树引出来的，对于深度为 K，有 n 个节点的二叉树，当且仅当其中每一个节点都与深度为 k 的满二叉树中编号从 1 到 n 的节点一一对应的时称为完全二叉树，满二叉树是一种特殊的完全二叉树。

1、若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2 i − 1 2^{i-1} 2i−1(i>0)个结点；
2、若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2 k − 1 2^k-1 2k−1(k>=0)；
3、 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有 n0＝n2＋1；
4、具有n个结点的完全二叉树的深度k为 l o g 2 ( n + 1 ) log_2(n+1) log2​(n+1)上取整；
5、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
  假设父节点的编号是 i，则左孩子节点的编号的是 (2i + 1)；右孩子节点的编号就是 (2i + 2)。

// 孩子表示法
class Node {
    String val;
    Node left;
    Node right;

    public Node(String val) {
        this.val = val;
    }
}
// 孩子双亲表示法
class Node2{
    String val;
    Node left;
    Node right;
    Node parent;

    public Node2(String val) {
        this.val = val;
    }
}

先创建一个如下图的二叉树

public static Node build() {
    Node a = new Node("A");
    Node b = new Node("B");
    Node c = new Node("C");
    Node d = new Node("D");
    Node e = new Node("E");
    Node f = new Node("F");
    Node g  = new Node("G");
    a.left = b;
    a.right = c;
    b.left = d;
    b.right = e;
    e.left = g;
    c.right = f;

    return a;
}

四种遍历方式：
1.先序遍历 ( 根左右 ) ：先访问 ( visit ) 根节点，然后遍历左子树，然后遍历右子树；

public void preOrder(Node root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

2.中序遍历 ( 左根右 ) ：先递归遍历左子树，然后访问根节点，然后递归遍历右子树；

public static void inOrder(Node root) {
    if (root == null) {
        return ;
    }
    inOrder(root.left);
    System.out.print(root.val);
    inOrder(root.right);
}

3.后序遍历 ( 左右根 ) ：先递归遍历左子树，然后递归遍历右子树，然后访问根节点；

public static void postOrder(Node root) {
    if (root == null) {
        return ;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val);
}

4.层序遍历 ：按照从上到下，从左到右的顺序遍历。

方法一：

// 这个方法使用 count 来记录节点的个数
// 但是，注意当有多个树时，它求出的是累加的节点数，这时就会出现问题
public static int count = 0;
public static void length(Node root) {
    if (root == null) {
        return;
    }
    count ++;
    length(root.left);
    length(root.right);
}

方法二：

// 这个方法可以避免上个方法会出现的问题
public static int length2(Node root) {
    if (root == null) {
        return 0;
    }
    return 1 + length2(root.left) + length2(root.right);
}

public int getKLevelSize(Node root,int k) {
    if (root == null || k < 1) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return getKLevelSize(root.left,k - 1) + getKLevelSize(root.right,k - 1);
}

k 层节点数 = 左子树 k - 1 层节点个数 + 右子树 k - 1 层节点个数，具体根据我们创建的这棵树来解释就是如下：

A 的第三层的节点数 = B 的第二层节点个数 + C 的第二层节点个数 = D 的第一层节点个数 + E 的第一层节点个数 + F 的第一层节点个数。（第一层就是当前层）

A 的高度 = 1 + ( B的高度和C的高度的较大值 )

public static int getHeight(Node root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
   return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

遍历二叉树，查找与要找元素相同的元素

public static Node find(Node root,String toFind) {
    if (root == null) {
        return null;
    }
    if (root.val.equals(toFind)) {
        return root;
    }
    Node ret = find(root.left,toFind);
    if (ret != null) {
        return ret;
    }
    return find(root.right,toFind);
}