个人学习笔记--数据结构与算法--二叉树（四）
以下是学习恋上数据结构与算法的学习笔记，本篇主要内容是二叉树基本概念
◼树（Tree）的基本概念
●节点、根节点、父节点、子节点、兄弟节点，一棵树可以没有任何节点，称为空树，一棵树可以只有1 个节点，也就是只有根节点
●子树：左子树、右子树
●节点的度（degree）：子树的个数
●树的度：所有节点度中的最大值
●叶子节点（leaf）：度为0 的节点
●非叶子节点：度不为0 的节点
●层数（level）：根节点在第1 层，根节点的子节点在第2 层，以此类推（有些教程也从第0 层开始计算）
●节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
●节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
●树的深度：所有节点深度中的最大值
●树的高度：所有节点高度中的最大值
●树的深度等于树的高度
●有序树：树中任意节点的子节点之间有顺序关系
●无序树：树中任意节点的子节点之间没有顺序关系也称为“*树”
●森林：由m（m ≥0）棵互不相交的树组成的集合
◼二叉树（Binary Tree）
◼二叉树的特点：
●每个节点的度最大为2（最多拥有2 棵子树）
●左子树和右子树是有顺序的
●即使某节点只有一棵子树，也要区分左右子树
●二叉树是有序树还是无序树？有序树
◼二叉树的性质
●非空二叉树的第i层，最多有2i−1个节点（i≥1）
●在高度为h的二叉树上最多有2h−1个结点（h≥1）
●对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2 的节点个数为n2，则有: n0 = n2 + 1
：假设度为1 的节点个数为n1，那么二叉树的节点总数n= n0 + n1 + n2
二叉树的边数T = n1 + 2 * n2 = n –1 = n0 + n1 + n2 –1
因此n0 = n2 + 1
◼真二叉树：
◼满二叉树（Full Binary Tree）
◼完全二叉树（Complete Binary Tree）
●叶子节点只会出现最后2 层，且最后1 层的叶子结点都靠左对齐
●完全二叉树从根结点至倒数第2 层是一棵满二叉树
●满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
●度为1 的节点只有左子树
●度为1 的节点要么是1 个，要么是0 个
●同样节点数量的二叉树，完全二叉树的高度最小
●假设完全二叉树的高度为h（h≥1），那么
●至少有2h−1个节点（20+21+22+⋯+2h−2+1）
●最多有2h−1个节点（20+21+22+⋯+2h−1，满二叉树）
●总节点数量为n
✓2h−1≤n<2h
✓h−1≤log2n<h
✓h=floor(log2n)+1
➢floor 是向下取整，另外，ceiling 是向上取整
◼判断一棵树是否为完全二叉树
●如果树为空，返回false
●如果树不为空，开始层序遍历二叉树（用队列）
●如果node.left!=null，将node.left 入队
●如果node.left==null && node.right!=null，返回false
●如果node.right!=null，将node.right 入队
●如果node.right=null
✓那么后面遍历的节点应该都为叶子节点，才是完全二叉树
✓否则返回false
●遍历结束，返回true
//是否为完全二叉树
public boolean isComplete() {
if(root==null) return false;//树为空，不是完全二叉树
//如果树不为空，开始层序遍历二叉树（用队列）
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);//根节点入队
boolean leaf = false;//叶子节点
//层序遍历二叉树
while(!queue.isEmpty()) {
Node<E> node=queue.poll();
if (leaf && !node.isLeaf()) return false;//叶子节点判断
if(node.hasTwoChildren()) {//度为2的节点
queue.offer(node.left);
queue.offer(node.right);
}else if(node.left==null && node.right!=null) {
return false;//左子树为空，而右子树不为空，不是完全二叉树
}else {后面遍历的节点应该都为叶子节点，才是完全二叉树
leaf = true;
}
}
return true;//遍历结束，返回true
}
◼二叉树的遍历
遍历是数据结构中的常见操作，就是把所有元素都访问一遍。
◼前序遍历（Preorder Traversal）
●访问顺序：根节点、前序遍历左子树、前序遍历右子树
●遍历顺序结果：7、4、2、1、3、5、9、8、11、10、12
前序遍历应用：树状结构展示（注意左右子树的顺序）
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
//递归
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
◼中序遍历（Inorder Traversal）
●访问顺序：中序遍历左子树、根节点、中序遍历右子树
●遍历顺序结果：1、2、3、4、5、7、8、9、10、11、12
中序遍历应用：二叉搜索树的中序遍历按升序或者降序处理节点
◼如果访问顺序是下面这样呢？
●中序遍历右子树、根节点、中序遍历左子树
●12、11、10、9、8、7、5、4、3、2、1
◼二叉搜索树的中序遍历结果是升序或者降序的
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.println(node.element);
inorderTraversal(node.right);
}
◼后序遍历（Postorder Traversal）
●访问顺序：后序遍历左子树、后序遍历右子树、根节点
●遍历顺序结果：1、3、2、5、4、8、10、12、11、9、7
◼后序遍历应用：适用于一些先子后父的操作
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.println(node.element);
}
◼层序遍历（Level Order Traversal）
●访问顺序：从上到下、从左到右依次访问每一个节点
●遍历顺序结果：7、4、9、2、5、8、11、1、3、10、12
◼层序遍历应用：计算二叉树的高度和判断一棵树是否为完全二叉树
◼实现思路：使用队列
1.将根节点入队
2.循环执行以下操作，直到队列为空
●将队头节点A 出队，进行访问
●将A 的左子节点入队
●将A 的右子节点入队
public void levelOrderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
◼根据遍历结果重构二叉树
以下结果可以保证重构出唯一的一棵二叉树
●前序遍历+ 中序遍历
红色方块为根节点，先利用前序遍历特性判断出根节点（第一个即为根节点），拿到根节点依据中序遍历锁定左右子树。再次循环判断左右子树的根节点，不断循环即可。
●后序遍历+ 中序遍历，同理
◼前序遍历+ 后序遍历
✓如果它是一棵真二叉树（度为2或者度为0），结果是唯一的
✓不然结果不唯一
◼前驱节点（predecessor）
●前驱节点：中序遍历时的前一个节点
●如果是二叉搜索树，前驱节点就是前一个比它小的节点
◼node.left!= null
举例：6、13、8
predecessor= node.left.right.right.right…
✓终止条件：right 为null
◼node.left== null && node.parent!= null
举例：7、11、9、1
predecessor= node.parent.parent.parent…
✓终止条件：node 在parent 的右子树中
◼node.left== null && node.parent== null
那就没有前驱节点
举例：没有左子树的根节点
private Node<E> predecessor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（left.right.right.right....）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null 和 node == node.parent.right
return node.parent;
}
◼后继节点（successor）
●后继节点：中序遍历时的后一个节点
●如果是二叉搜索树，后继节点就是后一个比它大的节点
◼node.right!= null
举例：1、8、4
successor= node.right.left.left.left…
✓终止条件：left 为null
◼node.right== null && node.parent!= null
举例：7、6、3、11
successor= node.parent.parent.parent…
✓终止条件：node 在parent 的左子树中
◼node.right== null && node.parent== null
那就没有前驱节点
举例：没有右子树的根节点
private Node<E> successor(Node<E> node) {
if (node == null) return null;
//后继节点在右子树当中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找后继节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
◼计算二叉树的高度
●递归
public int height() {
return height(root);
}
节点的高度时左右子树的高度+1
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
●迭代
利用层序遍历，每遍历一层，高度+1
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) { // 意味着即将要访问下一层
levelSize = queue.size();
height++;
}
}
return height;
}
上一篇： 时隔近一年半价格依然坚挺 黑莓KEY2到手价3249元
下一篇： 喝椰青的禁忌有哪些？