数据结构之二叉树家族1
树的产生
任何事物的诞生都是有原因的，不同的数据结构，是为了针对不同场景提供更优化的时间复杂度和空间复杂度。
几种常见的树：
树：
数据结构里的树跟真实的🌲很像，它的基本组成单位是节点，节点包含的链接可以为空或指向其他节点。简图如下：
Tree.png
对照例图介绍几个概念：
根节点：没有父节点的节点。
叶子节点：没有子节点的节点。
A是B的父节点；B是A的子节点；BC互为兄弟节点。
树对应的高度、深度、层也能从例图看明白。
一般的树，不再赘述，接下来讲几个特殊的树结构：
二叉树家族：
二叉树家族包含几种特殊的二叉树，最基本的二叉树从字面意思就能了解，除叶子节点外其他节点最多有两个子节点，再官方一点，就是每个节点都包含一个值和两个链接，链接可以为空，可以指向其他节点。在此基础上，延伸出了结构上特殊的树：满二叉树、完全二叉树；具有功能性的树：二叉查找树、平衡二叉树。
结构特殊的两种树：
满二叉树&完全二叉树.png
满二叉树：除叶子节点外，其他节点都有两个子节点。
完全二叉树：叶子节点必须在最后两层，最后一层的叶子节点从左到右结构上是连续的，除最后一层，其它层的节点个数达到最大。
说了很多毕竟还是要落实到代码上，下面我们一起来看一下如何用Java实现二叉树的遍历。
二叉树的遍历：
说起二叉树的遍历，那不得不提二叉树的前中后序遍历，还有二叉树的广度遍历和深度遍历，那我们一起来看看吧。
前中后序遍历（针对根节点的相对位置表述的,每种遍历都用递归和非递归方式实现）：
前序遍历：根左右
#######递归：
public static void preOrderRec(TreeNode root){
if(root!=null){
System.out.print(root.data+" ");
preOrderRec(root.left);
preOrderRec(root.right);
}
}
#######非递归：
前序遍历非递归的核心思路：
根节点入栈；栈不为空，让刚刚入栈的根节点出栈；若该根节点有右子节点，入栈；若该根节点有左子节点，入栈；一直遍历直到右左子节点都入栈。
public static void preOrder1(TreeNode root) {
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
if (root != null) {
stack.push(root);
}
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.data);
//右结点先入栈，左结点后入栈
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
中序遍历：左根右
#######递归：
public static void midOrderRec(TreeNode root){
if(root!=null){
midOrderRec(root.left);
System.out.print(root.data+" ");
midOrderRec(root.right);
}
}
#######非递归：
中序遍历非递归的核心思路：
根节点入栈；顺着根节点，将其左子节点全部入栈；左子节点出栈输出及值，再遍历右子节点。
public static void midOrder(TreeNode root){
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
while(root!=null||!stack.isEmpty()){
if(root!=null){
stack.push(root);
root= root.left;
}else {
root= stack.pop();
System.out.print(root.data+" ");
root=root.right;
}
}
}
后序遍历：左右根
#######递归：
public static void aftOrderRec(TreeNode root){
if(root!=null){
aftOrderRec(root.left);
aftOrderRec(root.right);
System.out.print(root.data+" ");
}
}
#######非递归：
后序遍历的非递归方式很难理解，因为它的遍历顺序是左右根，左子节点出栈后需要右子节点出栈，所以得借助两个stack来完成，为了帮助理解代码，绘制简要过程图：
aftOrder.png
public static void aftOrder1(TreeNode root){
java.util.ArrayDeque<TreeNode> inStack = new java.util.ArrayDeque<>();
java.util.ArrayDeque<TreeNode> outStack = new java.util.ArrayDeque<>();
inStack.push(root);
while(!inStack.isEmpty()){
outStack.push(root = inStack.pop());
if(root.left != null){
inStack.push(root.left);
}
if(root.right != null){
inStack.push(root.right);
}
}
while(!outStack.isEmpty()){
System.out.print(outStack.pop().data + " ");
}
System.out.println();
}
深度遍历和广度遍历：
深度遍历：
深度遍历的感觉就像沿着一条道走到黑，走不通了再出来，所以需要借助栈实现：
public void DFSTree(){
if(root == null){
return;
}
ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
stack.push(root);
while(stack.isEmpty()== false){
TreeNode node = stack.pop();
System.out.print(node.data+" ");
if(node.rightChild!=null){
stack.push(node.rightChild);
}
if(node.leftChild!=null){
stack.push(node.leftChild);
}
}
System.out.println("\n");
}
广度遍历：
广度遍历的感觉类似走完每一层树的节点，才更上一层楼，所以需要借助队列实现：
public void BFSTree(){
if(root ==null){
return;
}
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while(queue.isEmpty()==false){
TreeNode node = queue.remove();
System.out.print(node.data+" ");
if(node.leftChild!=null){
queue.add(node.leftChild);
}
if(node.rightChild!=null){
queue.add(node.rightChild);
}
}
}
