- 树结构：树结构是一种描述非线性层次关系的数据结构。
树是n个数据结点的集合，在该集合中包含一个根结点，根结点之下分布着一些互不交叉的子集合，这些子集合是根结点的子树。
树结构的基本特征：
（1）在一个树结构中，有且只有一个结点没有直接前驱，这个结点就是树的根结点；
（2）除根结点之外，其余每个节点有且仅有一个直接前驱；
（3）每个结点可以有任意多个直接后继。
- 树的概念
父结点和子结点:每个结点子树的根称为该结点的子结点，相应的，该结点称为其子结点的父结点；兄弟结点:具有同一父结点的结点称为兄弟结点；结点的度:一个结点所包含子树的数量；树的度:是指该树所有结点中最大的度；叶结点:树中度为零的结点称为叶结点或终端结点；分支结点:树中度不为零的结点称为分支结点或非终端结点；结点的层数:结点的层数从树根开始计算，根结点为第1层、依次向下为第2、3、…n层(树是一种层次结构，每个结点都处在一 定的层次上)；树的深度:树中结点的最大层数称为树的深度；有序树:若树中各结点的子树(兄弟结点)是按一 定次序从左向右排列的，称为有序树；无序树:若树中各结点的子树(兄弟结点)未按一 定次序排列，称为无序树；森林(forest): n (n>0)棵互不相交的树的集合。
- 二叉树
二叉树是树结构的一种特殊形式，是n个结点的集合，每个结点最多可以有两个结点。
二叉树的子树依然是二叉树。
二叉树的一个结点上对应的两个子树分别称为左子树和右子树。由于二叉树子树有左右之分，故而二叉树是有序树。
普通树结构中，结点的最大度数没有限制，而二叉树结点的最大度数为2。
一个二叉树结构也可以是空，此时空二叉树中没有数据结点，是一个空集合。
二叉树有两种特殊类型：
（1） 满二叉树：在二叉树中除了最下一层的叶结点外，每层的结点都有两个子结点
（2） 完全二叉树：
二叉树中除最后一层外，其它各层的结点都达到最大个数，且最后一层叶结点按照左往右的顺序连续存在，只缺最后一层右侧若干结点。
完全二叉树的性质
二叉树中树结构研究的重点是完全二叉树。对于完全二叉树，若树中包含n个结点，假设这些结点按照顺序方式存储。那么，对于任意一个结点m来说，具有如下性质:
如果m!=1，则结点m的父结点的编号为m/2;如果2m≤n，则结点m的左子树根结点的编号为2m; 若2*m>n, 则无左子树，也没有右子树如果2m+1≤n, 则结点m的右子树根结点编号为2m+1;若2*m+1>n,
则无右子树。另外，对于该完全二叉树来说，其深度为[log2n]+1。
这些基本性质展示了完全二叉树结构的特点，在完全二叉树的存储方式及运算处理上都有重要意义。
- 遍历二叉树
遍历二叉树即逐个查找二叉树中的所有结点，这是二叉树的基本操作，因为很多操作都需要首先遍历整个二叉树。由于二叉树结构的特殊性，往往可以采用多种方法进行遍历。
由于二叉树代表的是一种层次结构，因此，首先按层来遍历整个二叉树。对于二叉树的按层遍历，一般不能使用递归算法来编写代码，而是使用一个循环队列来进行处理。
当然也可以使用递归算法来简化遍历算法。一般可以采用以下几种方法来遍历整个二叉树：
先序遍历：即先访问根结点，再按先序遍历左子树，最后先序遍历右子树。
1、首先先定义一个树节点类信息，如下：
package com.dz.demo.algorithm;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
2、递归调用比较简单，具体如下：
private static void preOrderRecursive(TreeNode root) {
if (root == null) return;
System.out.println(root.val);
preOrderRecursive(root.left);
preOrderRecursive(root.right);
}
3、非递归的方法主要是借助栈结构来完成：
private static void preOrderUnRecursive(TreeNode root) {
Stack stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode temp = stack.pop();
if (temp == null) continue;
System.out.println(temp.val);
// 明确栈的进出顺序，先进后出，所以先序遍历，先push右子树
stack.push(temp.right);
stack.push(temp.left);
}
中序遍历：即先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。
import java.util.Stack;
public class Test
{
public static void main(String[] args)
{
TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
}
midOrderRe(node[0]);
System.out.println();
midOrder(node[0]);
}
public static void midOrderRe(TreeNode biTree)
{//中序遍历递归实现
if(biTree == null)
return;
else
{
midOrderRe(biTree.left);
System.out.println(biTree.value);
midOrderRe(biTree.right);
}
}
public static void midOrder(TreeNode biTree)
{//中序遍历费递归实现
Stack stack = new Stack();
while(biTree != null || !stack.isEmpty())
{
while(biTree != null)
{
stack.push(biTree);
biTree = biTree.left;
}
if(!stack.isEmpty())
{
biTree = stack.pop();
System.out.println(biTree.value);
biTree = biTree.right;
}
}
}
}
class TreeNode//节点结构
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
后序遍历：先按后序遍历左子树，再按后序遍历右子树，最后遍历根结点。
算法核心思想：
首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。
import java.util.Stack;
public class Test
{
public static void main(String[] args)
{
TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
}
postOrderRe(node[0]);
System.out.println("***");
postOrder(node[0]);
}
public static void postOrderRe(TreeNode biTree)
{//后序遍历递归实现
if(biTree == null)
return;
else
{
postOrderRe(biTree.left);
postOrderRe(biTree.right);
System.out.println(biTree.value);
}
}
public static void postOrder(TreeNode biTree)
{//后序遍历非递归实现
int left = 1;//在辅助栈里表示左节点
int right = 2;//在辅助栈里表示右节点
Stack stack = new Stack();
Stack stack2 = new Stack();//辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
while(biTree != null || !stack.empty())
{
while(biTree != null)
{//将节点压入栈1，并在栈2将节点标记为左节点
stack.push(biTree);
stack2.push(left);
biTree = biTree.left;
}
while(!stack.empty() && stack2.peek() == right)
{//如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
stack2.pop();
System.out.println(stack.pop().value);
}
if(!stack.empty() && stack2.peek() == left)
{//如果是从左子节点返回父节点，则将标记改为右子节点
stack2.pop();
stack2.push(right);
biTree = stack.peek().right;
}
}
}
}
class TreeNode//节点结构
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
