树形结构（3）（Java语言）——二叉树（2）
二叉树的基本操作
前提条件
节点
class TreeNode {
public char val;
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
public TreeNode(char val) {
this.val = val;
}
}
二叉树
public class BinaryTree {
public TreeNode root;//二叉树的根节点
public TreeNode createTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
E.right = H;
C.left = F;
C.right = G;
return root;
}
}
获取树中节点的个数
方法1
int count = 0;
int size(TreeNode root) {
if (root == null) {
return count;
}
count++;
size(root.left);
size(root.right);
return count;
}
我们利用遍历的思路完成size（）方法，比如我们用先序遍历整个链表，在遍历过程中，如果节点不为null，那么计数器count就加1，直到遍历完整个链表完成sizeof（）方法，但是需要注意的是，在计数器count不能放在方法的内部，否则每次递归都会将count置为0，从而重新计算count。
方法2
int size1(TreeNode root) {
if (root == null) {
return 0;
}
return size1(root.right) + size1(root.left) + 1;
}
虽然代码量少但是不容易想到，因为这是采用的子问题解决的，举个例子：
解决这个节点个数问题，我们可以看作求A节点左树和右树的个数（左树右树是否存在），A左树的个数（0或者1）+A右树的个数（0或者1）+A本身（1）。求A左树的个数又可以由B左树的个数+B右树的个数＋1求得，依次递归可以得到节点的个数。
获取叶子节点的个数
方法1
// 获取叶子节点的个数
int LeafCount = 0;
int getLeafNodeCount1(TreeNode root) {
if (root == null) {
return 0;
}
if (root.right == null && root.left == null) {
LeafCount++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
return LeafCount;
}
跟获取节点个数类似，用遍历的方法解决该问题，当节点为null是返回0；当节点的左右孩子都为null时，证明此时的节点为叶子节点，所以LeafCount++，以此递归完成方法，最后返回LeafCount的值。同样需要注意的是LeafCount需要放到方法的外面，当然LeafCount也可以用static修饰。
方法2
int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
if (root.right == null && root.left == null) {
return 1;
}
return getLeafNodeCount(root.right) + getLeafNodeCount(root.left);
}
同样可以采用子问题的思路解决这个问题，要求出整棵树的叶子节点，我们可以求左子树和右子树的叶子节点的总和，只要满足一个节点的没有左右孩子那么就加上1，最后返回根节点的getLeafNodeCount(root.right)和getLeafNodeCount(root.left)的总和。
获取第K层节点的个数
int getKLevelNodeCount(TreeNode root, int k) {
if (root == null || k <= 0) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}
举个例子：
假设我们要求第3层的节点个数，首先就是求A节点往下第三层的节点个数，因此我们可以求A节点左右子树B和C往下2层的节点个数，最后就是求D，E（B的左右子树）F，G（C的左右子树）的往下1层的节点个数（这里的往下1层表示不动的意思），因此递归条件就是当k为1时，返回1，或者root == null和k <= 0返回0。最后返回getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1)的值。
获取二叉树的高度
int getHeight1(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight1(root.left);
int rightHeight = getHeight1(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
举个例子：
我们仍用子问题的思路求解，在求这棵树的高度时，我们需要求A的左右子树（B和C）的高度，让B树和C树的最大值加上1就是A树的高度，通理，求B树的高度就是求D树和E树的最大值加上1就是B树的高度，以此递归。当root为null时返回0，用leftHeight和rightHeight分别计算出root左右子树的高度，最后以三目运算符计算出leftHeight和rightHeight的最大值，将最大值加上1，并返回。
检测值为value的元素是否存在
TreeNode find(TreeNode root, char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = find(root.left,val);
if (ret != null){
return ret;
}
ret = find(root.right,val);
if (ret != null){
return ret;
}
return null;
}
举个例子：
假设我们要在这个二叉树上找“E”，我们直到会有3种情况，第一，root为null，此时返回null，第二，root.val和val值相等，那么返回root，第三，没有找到val值，并且root也不为null，那么此时我们需要先向root的左子树寻找，如果左子树有相应的val值，那么返回root，否则往root的右子树寻找，如果有val值返回root，如果右子树也没有val值，那么最后返回null值。
判断一棵树是不是完全二叉树
boolean isCompleteTree(TreeNode root){
if (root == null){
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.peek() != null){
queue.offer(queue.peek().left);
queue.offer(queue.peek().right);
queue.poll();
}
while (queue.poll() == null){
if (queue.isEmpty()){
return true;
}
}
return false;
}
判断一棵树是否为完全二叉树需要我们用到队列来解决，举个例子：
我们知道这个这个树不是完全二叉树，那么思路是什么样的呢？
首先，我们将A节点放入队列中去。
然后将队头元素A弹出，放入A左右孩子节点（B和C）。
同样的，将队头元素B弹出，放入B左右孩子节点（D和E）。
同理，C节点也是如此。
将队头元素D弹出时，放入D的左右孩子节点（null和null）。
如此循环，当队头元素为null时跳出循环，此时情况如下：
此时队头为null，每次弹出一个队头元素，如果队头为null进入循环，判断此时的队列是否为空，如果为空，返回true，当弹出的队头元素不为null时，则不进入循环直接返回false。我们可以看到上述队列中当弹出队头三次时，遇到了H节点，并不为null，因此该树并不是完全二叉树。
注意： 这当中有一个非常容易错的点在于队列必须先放入左节点，在放入右节点，如果先放入右节点，然后在放入左节点很容易出现bug导致代码报错。
好了，关于二叉树的基本操作就是这么多，这些基本操作对于理解二叉树的性质和递归思想有着非常好的作用，如果有什么问题或者想法欢迎各位私信和评论，也希望这篇博客能够给各位带来帮助，谢谢大家！