1. 二叉树分类
满二叉树：所有层的节点数均达到了最大值
完全二叉树：除了最后一层外，所有层的节点数都达到了最大值，最后一层若不满，则只缺少右边部分。
平衡二叉树：：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1。
2. 度为二的节点数和叶子节点数的关系
设二叉树的叶子节点个数为x,二度节点个数为y，1度节点个数为z，总结点个数为N，则有：
x+y+z= N;
又 N个节点一共有 N-1个树枝，二度节点有2个树枝，1度节点有1个，叶子没有，所以：
2y+z = N-1;
可得出 x = y+1.
3.遍历
只要给出中根遍历，先根遍历和后根遍历的一种，就能确定一棵二叉树。
只给出先跟顺序和后根顺序无法确定一棵二叉树。例如：
- 树1：根A和一个左子节点B
- 树2：根A和一个右子节点B
1.递归遍历
只给出先根遍历的递归代码：
Java
//先根遍历
public void preVisit(Node node){
if(node== null){
return;
}
System.out.println(node.val);
preVisit(node.left);
preVisit(node.right);
}
2.非递归遍历：
```Java```
//非递归先根遍历，
//1 对每个节点，先进行访问，然后右节点进栈，左节点进栈
//2 弹出栈顶，对栈顶进行1的操作
public void nonRecursivePre(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> nodeStack = new Stack<>();
nodeStack.push(node);
while (!nodeStack.empty()) {
TreeNode peek = nodeStack.pop();
System.out.print(peek.val);
if (peek.right != null) {
nodeStack.push(peek.right);
}
if (peek.left != null) {
nodeStack.push(peek.left);
}
}
}
//中根遍历
public void nonRecursiveMiddle(TreeNode node) {
if (node != null) {
Stack<TreeNode> nodeStack = new Stack<>();
while (node != null || !nodeStack.empty()) {
while (node != null) {
nodeStack.push(node);
node = node.left;
}
node = nodeStack.pop();
System.out.print(node.val);
node = node.right;
}
}
}
//后根遍历
public void nonRecursiveAfter(TreeNode node) {
if (node != null) {
Stack<TreeNode> nodeStack = new Stack<>();
TreeNode pre = null;
while (node != null || !nodeStack.empty()) {
while (node != null) {
nodeStack.push(node);
node = node.left;
}
node = nodeStack.peek();
if (node.right == null || node.right.equals(pre)) {
System.out.print(node.val);
pre = node;
nodeStack.pop();
node = null;
} else {
node = node.right;
}
}
}
}
