二叉树分类
满二叉树： 除最后一层无任何子外，每一层上的所有结点都有两个子结点二叉树。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
平衡二叉树：称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
对于完全二叉树，若某个节点数为i，左子节点位2i+1，右子节点为2i+2。
二叉树实现
通过以下代码实现一个二叉树的基本结构
public class BinaryNode {
public BinaryNode(Object data) {
//节点数据
this.data = data;
//左孩子
this.left = null;
//右孩子
this.right = null;
}
}
构造完全二叉树
完全二叉树.png
public void creatNode() {
BinaryNode a1 = new BinaryNode("1");
BinaryNode a2 = new BinaryNode("2");
BinaryNode a3 = new BinaryNode("3");
BinaryNode a4 = new BinaryNode("4");
BinaryNode a5 = new BinaryNode("5");
BinaryNode a6 = new BinaryNode("6");
this.left = a1;
this.right = a2;
a1.left = a3;
a1.right = a4;
a2.left = a5;
a2.right = a6;
}
二叉树遍历
节点遍历
- 前序遍历 访问根节点，前序遍历左子书，前序遍历又子树
public static void preOrder(BinaryNode root) {
if (root == null)
return;
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
0,1,3,4,2,5,6
- 中序遍历 中序遍历左子树，访问根节点，中序遍历右子书
public static void midOrder(BinaryNode root) {
if (root == null) {
return;
}
midOrder(root.left);
System.out.println(root.data);
midOrder(root.right);
}
3,1,4,0,5,2,6
- 后序遍历 后续遍历左子树，后续遍历又子树，访问根节点
public static void postOrder(BinaryNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.println(root.data);
}
3,4,1,5,6,2,0
- 前序遍历（压栈法）
/**
* 前序遍历
*/
public static void preorderTraversal(BinaryNode root) {
//节点为空直接返回
if (root == null) {
return;
}
//创建栈
Stack<BinaryNode> stack = new Stack<BinaryNode>();
//将根节点放入栈中
stack.push(root);
//当栈不为空时循环
while (!stack.isEmpty()) {
//出栈
BinaryNode binaryNode = stack.pop();
//打印出栈的data
System.out.println(binaryNode.data);
//先压入右节点，先进后出
if (binaryNode.right != null) {
stack.push(binaryNode.right);
}
//再压入左节点
if (binaryNode.left != null) {
stack.push(binaryNode.left);
}
}
}
层次遍历
二叉树的层次遍历可以分为深度优先遍历跟广度优先遍历
- 深度优先遍历：实际上就是上面的前序、中序和后序遍历，也就是尽可能去遍历二叉树的深度。
- 广度优先遍历：实际上就是一层一层的遍历，按照层次输出二叉树的各个节点。
广度优先遍历
所谓广度优先遍历就是一层一层的遍历，所以只需要按照每层的左右顺序拿到二叉树的节点，再依次输出就OK了
public static void levelOrder(BinaryNode root) {
if (root == null) {
return;
}
LinkedList<BinaryNode> queue = new LinkedList<>();
//把根节点放进linked中
queue.push(root);
while (!queue.isEmpty()) {
// 打印linkedList的第一次元素，并移除
BinaryNode binaryNode = queue.removeFirst();
System.out.print(binaryNode.data + " ");
// 依次添加每个节点的左节点
if (binaryNode.left != null) {
queue.add(binaryNode.left);
}
// 依次添加每个节点的右节点
if (binaryNode.right != null) {
queue.add(binaryNode.right);
}
}
}
