树(Tree)是n(n≧0)个结点的有限集。在任意一颗非空树中：有且仅有一个特定的称为根的结点。n=0时称为空树。
n=0时称为空树。
n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，T3，……，Tm，其中每个集合本身又是一棵树，并且称为根的子树。
节点：树中的每一个元素都是一个节点，如上图中1，2，3，4，5，6等都是树的节点，节点可以为NULL，上图中并未直接画出。
根节点：一棵树中有且仅有一个根节点，上图中1为根节点。
父节点：上图中1是2、3、4的父节点，2是4和5的父节点…。
子节点：上图中2、3和4分别是1的子节点…。
兄弟节点：父节点的子节点被称为兄弟节点，如4和5之间为兄弟节点。
节点的度（degree）：子树的个数，如节点1的度为3，节点2的度为2。
树的度（degree）：所有节点度中最大的值。
叶子节点（leaf）：度为 0 的节点。
非叶子节点：度不为0的节点。
层数：根节点在第一层，根节点的子节点在第二层，以此类推。
节点的深度（depth）：从根节点到当前节点的唯一路径的节点总数，如节点4的深度为3。
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数，如节点4的高度为2。
树的深度：所有节点深度中的最大值。
树的高度：所有节点高度中的最大值。
树的深度等于树的高度。
树中任意节点的子节点之间有顺序关系
无序树树中任意节点的子节点之间没有顺序关系
也称为”自由树”
森林由m (m≥0)棵互不相交的树组成的集合
每个节点的度最大为2 （最多拥有2棵子树）。
左子树和右子树是有顺序的。
即使某节点只有一棵子树，也要区分左右子树。
二叉树是有序树还是无序树？有序树
假设度为1的节点的个数为n1，则有no + n1 + n2 = n，n为节点的个数。当节点个数为n时，则二叉树中边的个数为n-1。当度为2的节点个数为n2，则存在的边数为2 * n2，当度为1的节点个数为n1，则存在的边数为n1，当度为0的节点个数为n0，则存在的边数为0，可得2 * n2 + n1 = n - 1。
在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多。
满二叉树一定是真二叉树，真二叉树不一定是满二叉树。
假设满二叉树的高度为h （h≥1），那么
第i层的节点数量:2^(i-1)。
叶子节点数量: 2^(h-1)。
总节点的数量n，n = 2 ^ h- 1 = 2 ^ 0 + 2 ^ 1 + ...... + 2 ^ (h-1)，则h = log(n + 1)。
度为1的节点只有左子树。
度为1的节点要么是1个，要么是0个。
同样节点数量的二叉树，完全二叉树的高度最小。
假设完全二叉树的高度为h(h≥1)，那么
至少有2^(h-1)个节点( 2^0 + 2^1 +2^2 + ... + 2^(h-2) +1)
最多有2^h - 1个节点(2^0 + 2^1 + 2^2 + ... + 2^(h-1)， 满二叉树)
总节点数量为n
2^(h-1) <= n < 2^hh - 1 <= log(n) < hh = floor(log(n)) + 1一棵有n个节点的完全二叉树(n>0)，从上到下、从左到右对节点从0开始进行编号,对任意第i个节点。
如果i = 0,它是根节点。如果i > 0，它的父节点编号为floor(i-1)/2)。如果2i + 1 ≤ n -1,它的左子节点编号为2i + 1。如果2i + 1 > n-1，它无左子节点。如果2i + 2 ≤ n-1，它的右子节点编号为2i+ 2。如果2i + 2 > n-1，它无右子节点。如果一棵完全二叉树有768个节点，求叶子节点的个数？
假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2。
总结点个数n = n0 + n1 + n2，而且n0 = n2 + 1，所以有n = 2 * n0 + n1 - 1。
完全二叉树的n1要么为0，要么为1
n1为1时，n = 2 * n0，n必然是偶数：
叶子节点个数n0 = n / 2，非叶子节点个数n1 + n2= n/2。
n1为0时，n = 2 * n0 - 1，n必然是奇数： 叶子节点个数n0 = (n + 1)/ 2，非叶子节点个数n1 + n2 = (n- 1)/2。
倘若，我们想要构建下图所示的一棵二叉树，应该如何构建呢？
采用递归的方式，首先可以构建根节点，然后构建根节点的左子树，接着构建根节点右子树。 既然采用递归，那么一定得有递归的终止条件，那么何时终止呢？答案便是节点为NULL的时候，这里我们以#字符代替空节点。
接下来，便进入代码的研究。
首先，我们可以看一下，二叉树节点的定义。
/** * @author wangzhao * @date 2020/7/1 2:11 */ public class TreeNode<E> { public E value; public TreeNode<E> left; public TreeNode<E> right; public TreeNode<E> parent; public TreeNode(E value, TreeNode<E> parent) { this.value = value; this.parent = parent; } }相比于前面介绍的二叉树，多了一个parent指针，不过这并不影响我们对二叉树的使用，这样定义是为了后面其他树的学习。
二叉树的构建代码可以看createTree()方法。
import java.util.Scanner; import java.util.Scanner;/** * @author wangzhao * @date 2020/7/1 2:10 */ public class BinaryTree { private TreeNode root; public TreeNode createTree(){ root = createTree(null); return root; } private TreeNode createTree(TreeNode parentNode){ Scanner input = new Scanner(System.in); char ch = input.next().charAt(0); // 递归的终止条件 if (ch == '#'){ return null; } // 首先构建根节点 TreeNode node = new TreeNode(ch, parentNode); // 接着构建根节点的左子树 node.left = createTree(node); // 最后构建根节点的右子树 node.right = createTree(node); return node; } }如果，我们要构建上图所示的二叉树，输入的内容应该如下所示：
根节点、左子树、右子树
前序遍历二叉树的顺序如下图所示：
public void preOrderTraversal(){ preOrderTraversal(root); } private void preOrderTraversal(TreeNode node){ if (node == null) return; // 首先打印当前根节点的值 System.out.println(node.value); // 接着遍历当前根节点的左子树 preOrderTraversal(node.left); // 最后遍历当前根节点的右子树 preOrderTraversal(node.right); }左子树、根节点、右子树
中序遍历二叉树的顺序如下图所示：
public void inOrderTraversal(){ inOrderTraversal(root); } private void inOrderTraversal(TreeNode node){ if (node == null) return; // 首先当前根节点的左子树 inOrderTraversal(node.left); // 接着打印当前根节点的值 System.out.println(node.value); // 最后遍历当前根节点的右子树 inOrderTraversal(node.right); }左子树、右子树、根节点
public void postOrderTraversal(){ postOrderTraversal(root); } private void postOrderTraversal(TreeNode node){ if (node == null) return; // 首先当前根节点的左子树 postOrderTraversal(node.left); // 接着遍历当前根节点的右子树 postOrderTraversal(node.right); // 最后打印当前根节点的值 System.out.println(node.value); }从上到下，从左到右依次访问每一个节点。
实现思路 将根节点入队循环执行以下操作，直到队列为空 将队头节点root出队，进行访问将root的左子节点入队将root的右子节点入队 public void sequenceTraversal(){ if (root == null){ return; } Queue<TreeNode> queue = new LinkedList<TreeNode> (); queue.offer(root); while (!queue.isEmpty()){ // 根节点出队 TreeNode node = queue.poll(); // 根节点的左子树入队 if (node.left != null){ queue.offer(node.left); } // 根节点的右子树入队 if (node.right != null){ queue.offer(node.right); } System.out.println(node.value); } }树状结构展示(注意左右子树的顺序)。
中序遍历二叉搜索树的中序遍历按升序或者降序处理节点。
后序遍历适用于一些先子后父的操作。
层序遍历计算二叉树的高度。
判断一棵树是否为完全二叉树。
方式一：二叉树的高度等于左子树和右子树高度的最大值+1。
public int height() { return height(root); } private int height(Node<E> root) { if(rootNode == null) return 0; return 1 + Math.max(height(root.left), height(root.right)); }方式二：层序遍历中，当每遍历完该层的最后一个节点，则高度+1。
如何判断当前节点是否是该层的最后一个节点，如果当前遍历的节点是该层的最后一个节点，那么下一层节点的个数就等于队列中元素的个数。
public int height() { if (rootNode == null) return 0; // 存储着每一层元素的数量 int height = 0; int levelSize = 1; Queue<Node> queue = new LinkedList<Node> (); queue.offer(rootNode); while (!(queue.isEmpty())){ Node node = queue.poll(); levelSize--; if (node.left != null){ queue.offer(node.left); } if (node.right != null){ queue.offer(node.right); } if (levelSize == 0){ // 访问完当前层的最后一个元素 levelSize = queue.size(); height++; } } return height; }完全二叉树的定义如下：叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐。
如果树为空，返回false。
如果树不为空，开始层序遍历二叉树（队列）
如果node.left != null，将node.left入队。
如果node.left == null && node.right != null，返回false。
如果node.right !=null，将node.right入队。
如果node.right == null
那么后面遍历的节点应该都为叶子节点，才是完全二叉树否则返回false遍历结束，返回true。
例如，节点B的right为null时，那么其后面的节点C和D只有是叶子节点时才能是完全二叉树。
public boolean isComplete(){ if (root == null) return false; boolean leaf = false; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode node = queue.poll(); if (leaf && (node.right != null || node.left != null)){ return false; } if (node.left != null){ queue.offer(node); }else if (node.right != null){ // node.left == null && node.right != null return false; } if (node.right != null){ queue.offer(node); }else{ // 此时，后续节点需要都是叶子节点 leaf = true; } } return true; }翻转二叉树
前序、中序、后序、层序都可以做，只要可以遍历到每一个节点。
// 采用前序遍历的方式 public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } TreeNode tempNode = root.left; root.left = root.right; root.right = tempNode; invertTree(root.left); invertTree(root.right); return root; } // 采用中序遍历的方式 public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } invertTree(root.left); TreeNode tempNode = root.left; root.left = root.right; root.right = tempNode; // 注意，这里因为已经将左右节点进行交换了，所以需要对 left 进行交换，即交换前的right 节点 invertTree(root.left); return root; } // 采用后序遍历的方式 public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } invertTree(root.left); invertTree(root.right); TreeNode tempNode = root.left; root.left = root.right; root.right = tempNode; return root; } // 采用层序遍历的方式 public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode node = queue.poll(); TreeNode tempNode = node.left; node.left = node.right; node.right = tempNode; if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } } return root; }重建二叉树
通过以下结果可以保证重建出一棵唯一的二叉树。
前序遍历 + 中序遍历后序遍历 + 中序遍历这里，我们以前序+中序的方式为例。首先，在前序遍历中，可以确定根节点。然后再中序遍历确定根节点的位置。根节点的左边则为左子树，右边则为右子树。接着回到前序遍历的左右子树，分别确定其根节点，接着再回到中序遍历中对应左右子树中寻找根节点，一直递归。
索引关系如图示：
public TreeNode buildTree(int[] preorder, int[] inorder) { TreeNode root = null; root = buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length - 1); return root; } private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) { if (preLeft > preRight || inLeft > inRight){ return null; } TreeNode root = new TreeNode(preorder[preLeft]); int i = 0; // 中序遍历中寻找根节点的位置 for (i = inLeft; i <= inRight; i++){ if (preorder[preLeft] == inorder[i]){ break; } } // 构建左子树 root.left = buildTree(preorder, preLeft + 1, preLeft + i - inLeft, inorder, inLeft, i - 1); // 构建右子树 root.right = buildTree(preorder, preLeft + i - inLeft + 1, preRight, inorder, i + 1, inRight); return root; }前驱节点:中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点node.left != null
processorNode = node.left.right.right ... ，终止条件right == null例如4的前驱节点为3，13的前驱节点为12。node.left == null && node.parent != null
processorNode = node.parent.parent...，终止条件node = parent.right例如3的前驱节点是2，9的前驱节点是8。node.left == null && node.parent == null
无前驱节点 public TreeNode predecessorNode(TreeNode node){ if (node == null){ return null; } // 前驱节点在左子树中 TreeNode processorNode = node.left; if (processorNode != null){ while (processorNode.right != null){ processorNode = processorNode.right; } return processorNode; } // 从祖先节点中寻找 while (node.parent != null && node == node.parent.left){ node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; }后继节点：中序遍历时的后一个节点
如果是二叉搜索树，后继节点就是后一个比它大的节点node.right != null
successor = node.right.left.left.left...，终止条件: left == nullnode.right == null && node .parent != null
successor = node.parent.parent.parent...，终止条件：node == node.parent.leftnode.right == null && node.parent == null
那就没有前驱节点 public TreeNode successorNode(TreeNode node){ if (node == null){ return null; } // 后继节点在右子树中 TreeNode successorNode= node.right; if (successorNode!= null){ while (successorNode.left!= null){ successorNode= successorNode.left; } return successorNode; } // 从祖先节点中寻找 while (node.parent != null && node == node.parent.right){ node = node.parent; } return node.parent; }