续接上一话
目录
一、二叉树（续）
1、二叉树的基本操作
1.1前置说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习。等 二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
public class BinaryTree{
public static class BTNode{
BTNode left;
BTNode right;
int value;
BTNode(int value){
this.value = value;
}
}
private BTNode root;
public void createBinaryTree(){
BTNode node1 = new BTNode(1);
BTNode node2 = new BTNode(2);
BTNode node3 = new BTNode(3);
BTNode node4 = new BTNode(4);
BTNode node5 = new BTNode(5);
BTNode node6 = new BTNode(6);
root = node1;
node1.left = node2;
node2.left = node3;
node1.right = node4;
node4.left = node5;
node5.right = node6;
}
}注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
在看二叉树基本操作前，我们回顾下二叉树的概念，二叉树是：
（1）空树
（2）非空：根节点，根节点的左子树、根节点的右子树组成的。
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
1.2二叉树的遍历
1.2.1前中后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按 照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的 左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：
（1）NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。（从根节点开始，先左后右，遇到一个结点就出一个数据）
// 前序遍历
public void preOrder(TreeNode root) {
if(root == null) return;
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}（2）LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。（从根节点开始，先左后右，某一个节点的左子树都走完时出该节点数据）
// 中序遍历
public void inOrder(TreeNode root) {
if(root == null) return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}（3）LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。（从根节点开始，先左后右，某一个节点的右子树都走完时出该节点数据）
// 后序遍历
public void postOrder(TreeNode root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}下面主要分析前序递归遍历，中序与后序图解类似
前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 1 5 6 4 1
总结：
先序遍历：遇到一个出一个
特点：第一个打印根节点
中序遍历：左侧孩子结点返回时打印（左侧都走完）
特点：根节点左侧为左子树，右侧为右子树
后序遍历：右侧孩子结点返回时打印（右侧都走完）
特点：最后一个打印根节点
1.2.2层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
1.2.3练习
（1）自己去多找几个二叉树的图片，分别写出对应的前中后序遍历
（2）选择
答案：
1.3二叉树的基本操作
// 获取树中节点的个数
public void size(TreeNode root) {
if(root == null) {
return ;
}
nodeSize++;
size(root.left);
size(root.right);
}
// 获取叶子节点的个数
public void getLeafNodeCount(TreeNode root) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
}
// 获取第K层节点的个数
public int getKLevelNodeCount(TreeNode root,int k) {
if(root == null) {
return 0;
}
if(k == 1) {
return 1;
}
return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
}
// 获取二叉树的高度
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight >rightHeight
? leftHeight+1 : rightHeight+1;
}
// 检测值为value的元素是否存在
public TreeNode findVal(TreeNode root,char val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
}
TreeNode leftT = findVal(root.left,val);
if(leftT != null) {
return leftT;
}
TreeNode rightT = findVal(root.right,val);
if(rightT != null) {
return rightT;
}
return null;
}
//判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean foundNull = false; // 标记是否已经遇到null节点
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (current == null) {
foundNull = true; // 遇到null节点，标记为true
} else {
// 如果已经遇到过null节点，但当前节点不为null，则不是完全二叉树
if (foundNull) {
return false;
}
// 将左右子节点加入队列（即使为null也要加入）
queue.offer(current.left);
queue.offer(current.right);
}
}
return true;
}由于内容较多，会分为多篇讲解，预知后续内容，请看后续博客！！！