二叉树的基本知识
树的定义：
树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。
当n=0时，称为空树
树的概述图
树具有的特点有：
1、每个结点有零个或多个子结点
2、每一个非根结点有且只有一个父节点
3、除了根结点外，每个子结点可以分为多个不相交的子树。
4、一颗n个结点的树有n-1条边（从下往上看，根节点不提供边）
树的一些基本术语：
1、结点的度：结点拥有的子树的数目
2、树的度：树中结点的最大的度
3、叶结点：度为0的结点
4、父结点：有子树的结点是其子树根节点的父节点
5、子节点，F是C的父结点，C是F的子结点
6、兄弟结点，具有同一父结点的各结点彼此是兄弟结点
7、祖先结点，沿树到某一结点路径上所有结点都是这个结点的祖先结点
8、子孙结点
9、结点的层次：根结点的层次为1，其余结点的层次等于其父结点的层次加1
10、树的深度：树中结点的最大层次
二叉树的定义：
二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根和空的左子右子树；根和左子树或右子树；根和左、右子树。
满二叉树和完全二叉树：
1、满二叉树（完美二叉树）
2、完全二叉树
定义：对n个结点的树，从上到下、从左到右顺序进行编号，任一结点编号与二叉树中相同编号结点位置相同。
一棵满二叉树是一棵完全二叉树，但完全二叉树未必是满二叉树。
二叉树的性质：
性质1：二叉树第i层上的最大结点数为（i>=1）
性质2：深度为k的二叉树有最大结点总数（k>=1）
性质3：在任意一棵二叉树中，若叶结点的个数为n0，度为2的结点数为n2，则n0=n2+1
创建一颗如下图的树，并进行递归、非递归（前序、中序、后序）以及层序遍历
代码实现如下：
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;
public class MyTree {
public TreeNode root; //根结点
public List<TreeNode> datas; //结点集合
public MyTree() {
this.root = new TreeNode(); //初始化
}
//创建树
public void CreatTree(Object[] data) {
datas = new ArrayList<TreeNode>();
//将数组中的待添加的元素全部构建成树结点，放入datas集合中
for (Object o : data) {
datas.add(new TreeNode(o));
}
root = datas.get(0); //根结点更新为集合第一个元素
for (int i = 0; i <= data.length / 2 - 1; i++) { //i限制不超过这个值，也就是叶结点没有子树
if (datas.get(i) != null) { //为null时，也就是空节点了，没有子树
datas.get(i).setLeft(datas.get(2 * i + 1));
datas.get(i).setRight(datas.get(2 * i + 2));
}
}
}
//递归前序遍历
public void PreOrderTraversal(TreeNode root) {
if (root != null) {
System.out.println(root.getData());
PreOrderTraversal(root.getLeft());
PreOrderTraversal(root.getRight());
}
}
//递归中序遍历
public void InOrderTraversal(TreeNode root) {
if (root != null) {
InOrderTraversal(root.getLeft());
System.out.println(root.getData());
InOrderTraversal(root.getRight());
}
}
//递归后序遍历
public void PostOrderTraversal(TreeNode root) {
if (root != null) {
PostOrderTraversal(root.getLeft());
PostOrderTraversal(root.getRight());
System.out.println(root.getData());
}
}
//非递归中序遍历
public void SinOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>(); //递归是靠堆栈实现的，非递归直接用堆栈
while (null != root || !stack.isEmpty()) { //遍历
//左子树入栈
while (root != null) {
stack.push(root);
root = root.getLeft();
}
//左子树入栈完毕
if (!stack.isEmpty()) {
TreeNode pop = stack.pop();
System.out.println(pop.getData()); //按照走的路径，第2次碰见出栈就打印，叶结点第1次、第2次、第3次是同时碰见的
root = pop.getRight();
}
}
}
//非递归前序遍历
public void SpreOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while (null != root || !stack.isEmpty()) { //遍历
//左子树入栈
while (root != null) {
stack.push(root);
System.out.println(root.getData()); //按照走的路径，第1次碰见入栈就打印
root = root.getLeft();
}
//左子树入栈完毕
if (!stack.isEmpty()) {
TreeNode pop = stack.pop();
root = pop.getRight();
}
}
}
//非递归后序遍历
public void SpostOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while (null != root || !stack.isEmpty()) { //遍历
//左子树入栈
while (root != null) {
stack.push(root);
root = root.getLeft();
}
//左子树入栈完毕
boolean flag = false; //状态记录，来记录是否遍历了右子树(如果有），false为没有遍历，true为遍历了
TreeNode pre = null; //记录上一个输出结点
while (!stack.isEmpty() && flag == false) {
if (stack.peek().getRight() == pre) { //如果栈的顶层结点没有（null）右子树或者是右子树上一次（pre）输出了
TreeNode pop = stack.pop(); //出栈
System.out.println(pop.getData());
pre = pop; //更新输出记录
} else {
//如果有右子树并且没有输出，准备遍历右子树，并更新flag状态，跳出循环
root = stack.peek().getRight();
flag = true;
}
}
}
}
//层序遍历
/*
根结点入队
循环：结点出队，该结点左右左右儿子入队
*/
public void LevelOrderTraversal(TreeNode root) {
Queue<TreeNode> queue = new LinkedBlockingQueue<>();
queue.add(root);
while (root != null) {
TreeNode node = queue.remove();
System.out.println(node.getData());
if (node.getLeft() != null) {
queue.add(node.getLeft());
}
if (node.getRight() != null) {
queue.add(node.getRight());
}
root = queue.peek();
}
}
}
//main测试
public static void main(String[] args) {
MyTree tree = new MyTree();
Object[] arr = {"A", "B", "C", "D", "F", "G", "I", null, null, "E", null, null, "H"};
tree.CreatTree(arr);
System.out.println("--递归前序--");
tree.PreOrderTraversal(tree.root); //A\B\D\null\null\F\E\null\C\G\null\H\I
System.out.println("--递归中序--");
tree.InOrderTraversal(tree.root); //null\D\null\B\E\F\null\A\null\G\H\C\I
System.out.println("--递归后序--");
tree.PostOrderTraversal(tree.root); //null\null\D\E\null\F\B\null\H\G\I\C\A
System.out.println("--非递归前序--");
tree.SpreOrderTraversal(tree.root); //A\B\D\null\null\F\E\null\C\G\null\H\I
System.out.println("--非递归中序--");
tree.SinOrderTraversal(tree.root); //null\D\null\B\E\F\null\A\null\G\H\C\I
System.out.println("--非递归后续--");
tree.SpostOrderTraversal(tree.root); //null\null\D\E\null\F\B\null\H\G\I\C\A
System.out.println("--层序遍历--");
tree.LevelOrderTraversal(tree.root); //A\B\C\D\F\G\I\null\null\E\null\null\H
}
