【数据结构与算法】Java描述：第四节：二叉树
一、树的相关概念
编程中的树是模仿大自然中的树设计的，呈现倒立的结构，我们着重掌握 二叉树 。
1.1 基本概念：
结点的度：一个结点有几个子结点，度就是几； 如上图：A的度为3
树的度：一棵树中，所有结点 度 的 最大值 称为 树的度； 如上图：树的度为3
叶子结点或终端结点：度为0的结点称为叶子结点； 如上图：J F K L H I...等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的 根结点 称为该结点的 子结点； 如上图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
1.2 树的表现形式：
树有多种表现方式，如双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法，下图为孩子兄弟表示法
我们在操作一棵树时，主要操作的结点，对每一个树的结点进行操作，所以我的 Tree 类中会定义结点类 Tree Node
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
二、二叉树
2.1 二叉树的概念
二叉树是树的一种，它的特点是每个结点的度最大为2，并且两边分别称为 左子树 ，右子树
2.2 两种特殊的二叉树
满二叉树：所有结点都是满的，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
完全二叉树：从左往右,从上往下，完全二叉树是一棵深度最小的二叉树，其除了最后一层可能不是满的，其他每一层都必须是满的，并且节点从左到右依次排列。
2.3 相关性质：
1. 根结点的层数为1，则一棵 非空二叉树 的第 i 层上最多有 (i>0)个结点。
2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
4.具有n个结点的完全二叉树的深度k为上取整
5. 完全二叉树通常使用数组来表示，因为它的特性能够通过数组的索引来 快速定位 每个节点的位置。在数组中，根节点位于索引0，如果一个节点的索引为i，那么它的左子节点索引为2i+1，右子节点索引为2i+2。
6.给定结点数，求叶子结点数：
2.4 二叉树的基本操作：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public abstract class BinaryTree {
public class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 获取树中节点的个数
public int size(TreeNode root){
if(root==null){
return 0;
}
return size(root.left)+ size(root.right) + 1;
}
// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
return getLeafNodeCount(root.left)
+getLeafNodeCount(root.right);
}
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
public int getKLevelNodeCount(TreeNode root,int k){
if(root==null){
return 0;
}
if(root!=null && 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 Math.max(leftHeight,rightHeight)+1;
}
// 检测值为value的元素是否存在
public TreeNode find(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
} else {
if (root.left != null) {
find(root.left, val);
return root.left;
}
if (root.right != null) {
find(root.right, val);
return root.right;
}
return null;
}
}
//层序遍历
public void levelOrder(TreeNode root){
if(root==null){
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.isEmpty()){
TreeNode cur = queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}
public List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root==null){ //记得判空
return ret;
}
Queue <TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){//用方法不是null
int size = queue.size();//size不是length
List<Integer> retsamll = new ArrayList<>();
while(size!=0){
TreeNode cur = queue.poll();//在循环内，每次cur都是队列出去的元素
retsamll.add(cur.val);//在循环内，把一行的元素都添加完
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
size--;//记得把size最终变成小于零的，这样就进行下一列了
}
ret.add(retsamll);
}
return ret;
}
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root){
return false;
}
}
方法未完待续........
二叉树的层序遍历
判断是否是完全二叉树