图中的结构就像一棵倒过来的树，最顶部的节点就是“根节点 (root 节点)” 每棵树至多只有一个根节点 根节点生出多个孩子节点，每个孩子节点只有一个父节点，每个孩子节点又生出多个孩子 父亲节点 (parent) 和孩子节点 (child)是相对的 没有孩子节点的节点成为叶子节点 (leaf)
2. 树中的基本概念：
节点的度 一个节点直接含有的子树个数，叫做节点的度。比如上图中的 3 的度是 2，10 的度是 1。
树的度 一棵树中 最大节点的度，即哪个节点的子节点最多，它的度就是 树的度。上图中树的度为 2 。
节点的层次 从根节点开始算起，根节点算第一层，往后底层。比如上图中，3 的层次是 2，4 的层次是 4。
树的高度 树的高度是从叶子节点开始，自底向上增加。
树的深度 与高度相反，树的深度从根节点开始，自顶向下增加。 整个树的高度、深度是一样的，但是中间节点的高度 和 深度是不同的，比如上图中的6 ，高度是 2 ，深度是 3。
3.树的实现过程： 树是一个递归的概念，从根节点开始，每个节点至多只有一个父节点，有多个子节点，每个子节点又是一棵树，以此递归。
树有两种实现方式： 数组 链表
数组表示： 我们可以利用每个节点至多只有一个父节点这个特点，使用 父节点表示法 来实现一个节点：
package com.hfc; public class TreeNode { private Object mData; //存储的数据 private int mParent; //父亲节点的下标 public TreeNode(Object data, int parent) { mData = data; mParent = parent; } public Object getData() { return mData; } public void setData(Object data) { mData = data; } public int getParent() { return mParent; } public void setParent(int parent) { mParent = parent; } public static void main(String[] args) { TreeNode treeNode[]=new TreeNode[10]; //这是一个对象数组 } }用数组实现的树表示下面的树，（其中一种 ）结果就是这样的：
数组实现的树节点使用角标表示父亲的索引。
使用链表的方式来实现：
package com.hfc; import java.util.LinkedList; import java.util.List; public class LinkedTreeNode { private Object mData; //存储的数据 private LinkedTreeNode mParent; //父亲节点的下标 private List<LinkedTreeNode> mChildNodeList; //孩子节点的引用 public LinkedTreeNode(Object data, LinkedTreeNode parent) { mData = data; mParent = parent; } public Object getData() { return mData; } public void setData(Object data) { mData = data; } public Object getParent() { return mParent; } public void setParent(LinkedTreeNode parent) { mParent = parent; } public List<LinkedTreeNode> getChild() { return mChildNodeList; } public void setChild(List<LinkedTreeNode> childList) { mChildNodeList = childList; } public static void main(String[] args) { //使用list来实现 LinkedList<LinkedTreeNode> linkedList=new LinkedList<>(); } }使用引用，而不是索引表示父亲与孩子节点。树，最大的作用就是为了更好的查找性能而生。
树的表示方法： 双亲表示法，
孩子表示法，
双亲孩子表示法,
孩子兄弟表示法；
常见的树有以下几种分类： 二叉树：，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成. （他就是两个叉，就是有两个孩子， 就和传销） 从定义可以看出， 二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5中表现形式
二叉树的特点：
性质1：在二叉树的第i层上至多有2^(i-1)个节点(i >= 1) 性质2：深度为k的二叉树至多有2^k-1个节点(k >=1) 性质3：对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1。 性质4：具有n个节点的完全二叉树的深度 。 二叉树的遍历分为 五种：前序遍历 中序遍历 后序遍历 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树 后序列遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点 深度优先遍历 广度优先遍历 例子：Tree.java
满二叉树 一棵深度为k且有2k-1（2的k次幂减1）个结点的二叉树称为满二叉树。
完全二叉树 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
二叉排序树 二叉查找树定义：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；它的左、右子树也分别为二叉排序树。平衡二叉树 —平衡二叉树（Balanced Binary Tree）又被称为AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1;
B 树: 二叉搜索树： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
B-树 : 是一种多路搜索树（并不是二叉的）：就是我们的文件系统就是b*树
B+树：B+树是B-树的变体，也是一种多路搜索树： 哈夫曼树： 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
红黑树：
红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
