一、二叉树
1、为什么需要树
1）数组存储方式的分析
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值（按一定顺序）会整体移动，效率较低
2）链式存储方式的分析
优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链按到链表中即可，删除效率也很好）。
缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从头节点开始遍历）
3）树存储方式的分析
可以提高数据存储，读取的效率
比如利用二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
2、树的常用术语
- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点：没有子节点的节点
- 节点的权：节点值
- 路径：从root 节点找到该节点的路线
- 层
- 子树
- 树的高度（最大层数）
- 森林 ：多颗子树构成森林
3、二叉树概述
- 二叉树：每个节点最多只能有两个子节点（左节点和右节点）
- 满二叉树：二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1（n 为层数）
- 完全二叉树：二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续
4、二叉树遍历概述
- 前序遍历：先输出父节点，再遍历左子树和右子树
- 中序遍历：先遍历左子树，再输出父节点，再遍历右子树
- 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
小结：看输出父节点的顺序，就确定是前序，中序还是后序
5、二叉树代码实现
package work.rexhao.tree;
/**
* 二叉树的遍历和查找
*
* @author 王铭颢
* @Date 2022/7/5 10:23
*/
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
System.out.print("先序遍历: ");
BinaryTree.preOrder(bt.head);//先序遍历：12453
System.out.println();
System.out.print("中序遍历: ");
BinaryTree.infixOrder(bt.head);//中序遍历：42513
System.out.println();
System.out.print("后序遍历: ");
BinaryTree.postOrder(bt.head);//后续遍历：45231
System.out.println();
System.out.println("------------");
System.out.println("先序查找3: " + BinaryTree.preOrderSearch(bt.head, 3));
System.out.println("先序查找6: " + BinaryTree.preOrderSearch(bt.head, 6));
System.out.println("中序查找3: " + BinaryTree.infixOrderSearch(bt.head, 3));
System.out.println("中序查找6: " + BinaryTree.infixOrderSearch(bt.head, 6));
System.out.println("后序查找3: " + BinaryTree.postOrderSearch(bt.head, 3));
System.out.println("后序查找6: " + BinaryTree.postOrderSearch(bt.head, 6));
System.out.println("------------");
BinaryTree.delTree(bt.head, 2);
BinaryTree.infixOrder(bt.head);//中序遍历：13
System.out.println();
BinaryTree.delTree(bt.head, 6);
BinaryTree.infixOrder(bt.head);//中序遍历：13
System.out.println();
System.out.println("------------");
bt = new BinaryTree();
BinaryTree.delNode(bt.head, 2);
BinaryTree.infixOrder(bt.head);//中序遍历：453
System.out.println();
}
}
/**
* 二叉树
*/
class BinaryTree {
TreeNode head;
public BinaryTree() {
head = new TreeNode(1);
head.leftNode = new TreeNode(2);
head.rightNode = new TreeNode(3);
head.leftNode.leftNode = new TreeNode(4);
head.leftNode.rightNode = new TreeNode(5);
/*
初始化树结构示意图
1
/ \
2 3
/ \
4 5
先序遍历：12453
中序遍历：42513
后续遍历：45231
*/
}
/**
* 先序遍历
*/
public static void preOrder(TreeNode tn) {
if (tn != null) {
System.out.print(tn.getData());
preOrder(tn.leftNode);
preOrder(tn.rightNode);
}
}
/**
* 中序遍历
*/
public static void infixOrder(TreeNode tn) {
if (tn != null) {
infixOrder(tn.leftNode);
System.out.print(tn.getData());
infixOrder(tn.rightNode);
}
}
/**
* 后序遍历
*/
public static void postOrder(TreeNode tn) {
if (tn != null) {
postOrder(tn.leftNode);
postOrder(tn.rightNode);
System.out.print(tn.getData());
}
}
/**
* 先序查找
*/
public static boolean preOrderSearch(TreeNode tn, int target) {
if (tn == null) return false;
if (target == tn.getData()) {
return true;
} else if (preOrderSearch(tn.leftNode, target)) {
return preOrderSearch(tn.leftNode, target);
} else {
return preOrderSearch(tn.rightNode, target);
}
}
/**
* 中序查找
*/
public static boolean infixOrderSearch(TreeNode tn, int target) {
if (tn == null) return false;
if (infixOrderSearch(tn.leftNode, target)) {
return infixOrderSearch(tn.leftNode, target);
} else if (target == tn.getData()) {
return true;
} else {
return infixOrderSearch(tn.rightNode, target);
}
}
/**
* 后序查找
*/
public static boolean postOrderSearch(TreeNode tn, int target) {
if (tn == null) return false;
if (postOrderSearch(tn.leftNode, target)) {
return postOrderSearch(tn.leftNode, target);
} else if (postOrderSearch(tn.rightNode, target)) {
return postOrderSearch(tn.rightNode, target);
} else {
return target == tn.getData();
}
}
/**
* 删除子树
* 叶子结点：删除节点
* 非叶子节点：删除子树
* 注：不删除根节点
*/
public static void delTree(TreeNode tn, int target) {
if (tn == null) {
return;
}
if (tn.leftNode != null) {
if (tn.leftNode.getData() == target) {
tn.leftNode = null;
return;
} else {
delTree(tn.leftNode, target);
}
}
if (tn.rightNode != null) {
if (tn.rightNode.getData() == target) {
tn.rightNode = null;
return;
} else {
delTree(tn.rightNode, target);
}
}
}
/**
* 删除节点
* 叶子节点：删除
* 非叶子节点（一个子节点）：替代原节点
* 非叶子节点（两个子节点）：左节点代替原节点
*/
public static void delNode(TreeNode tn, int target) {
if (tn == null) return;
if (tn.leftNode != null) {
if (tn.leftNode.getData() == target) {
if (tn.leftNode.rightNode == null && tn.leftNode.leftNode == null) {
// 叶子节点
tn.leftNode = null;
} else if (tn.leftNode.rightNode != null && tn.leftNode.leftNode != null) {
// 两个节点
tn.leftNode = tn.leftNode.leftNode;
} else {
// 一个节点
if (tn.leftNode.leftNode != null) {
// 左节点
tn.leftNode = tn.leftNode.leftNode;
} else {
// 右节点
tn.leftNode = tn.leftNode.rightNode;
}
}
return;
} else {
delNode(tn.leftNode, target);
}
}
if (tn.rightNode != null) {
if (tn.rightNode.getData() == target) {
if (tn.rightNode.rightNode == null && tn.rightNode.leftNode == null) {
// 叶子节点
tn.rightNode = null;
} else if (tn.rightNode.rightNode != null && tn.rightNode.leftNode != null) {
// 两个节点
tn.rightNode = tn.rightNode.leftNode;
} else {
// 一个节点
if (tn.rightNode.leftNode != null) {
// 左节点
tn.rightNode = tn.rightNode.leftNode;
} else {
// 右节点
tn.rightNode = tn.rightNode.rightNode;
}
}
return;
} else {
delNode(tn.rightNode, target);
}
}
}
}
/**
* 二叉树的节点
*/
class TreeNode {
private int data;
TreeNode leftNode;
TreeNode rightNode;
TreeNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
二、顺序存储二叉树
1、顺序存储二叉树的说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
2、顺序存储二叉树的特点
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为
2*n+1 - 第n个元素的右子节点为
2*n+2 - 第n个元素的父节点为
(n-1)/2 - n：表示二叉树中的第几个元素（按0开始编号）
3、顺序存储二叉树代码实现
package work.rexhao.tree;
/**
* 顺序存储二叉树
*
* @author 王铭颢
* @Date 2022/7/5 14:56
*/
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
ArrBinaryTree abt = new ArrBinaryTree(7);
for (int i = 0; i < abt.data.length; i++) {
abt.data[i] = i + 1;
}
System.out.print("前序:");
ArrBinaryTree.preOrder(abt, 0);
System.out.println();
System.out.print("中序:");
ArrBinaryTree.infixOrder(abt, 0);
System.out.println();
System.out.print("后序:");
ArrBinaryTree.postOrder(abt, 0);
System.out.println();
}
}
class ArrBinaryTree {
int[] data;
ArrBinaryTree(int maxSize) {
data = new int[maxSize];
}
/**
* 先序遍历
*/
public static void preOrder(ArrBinaryTree abt, int index) {
// 数组越界
if (index >= abt.data.length) {
return;
}
System.out.print(abt.data[index]);
preOrder(abt, index * 2 + 1);
preOrder(abt, index * 2 + 2);
}
/**
* 中序遍历
*/
public static void infixOrder(ArrBinaryTree abt, int index) {
// 数组越界
if (index >= abt.data.length) {
return;
}
infixOrder(abt, index * 2 + 1);
System.out.print(abt.data[index]);
infixOrder(abt, index * 2 + 2);
}
/**
* 后序遍历
*/
public static void postOrder(ArrBinaryTree abt, int index) {
// 数组越界
if (index >= abt.data.length) {
return;
}
postOrder(abt, index * 2 + 1);
postOrder(abt, index * 2 + 2);
System.out.print(abt.data[index]);
}
}
3、后序线索二叉树
...
