【数据结构与算法】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()){//用方法不是nullint size = queue.size();//size不是lengthList<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;}
}

方法未完待续........

二叉树的层序遍历

判断是否是完全二叉树