hello-algo/codes/java/chapter_tree/array_binary_tree.java
Yudong Jin a005c6ebd3
Some improvements (#1073)
* Update avatar's link in the landing page

* Bug fixes

* Move assets folder from overrides to docs

* Reduce figures' corner radius

* Update copyright

* Update header image

* Krahets -> krahets

* Update the landing page
2024-02-07 22:21:18 +08:00

136 lines
3.9 KiB
Java
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: array_binary_tree.java
* Created Time: 2023-07-19
* Author: krahets (krahets@163.com)
*/
package chapter_tree;
import utils.*;
import java.util.*;
/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
private List<Integer> tree;
/* 构造方法 */
public ArrayBinaryTree(List<Integer> arr) {
tree = new ArrayList<>(arr);
}
/* 列表容量 */
public int size() {
return tree.size();
}
/* 获取索引为 i 节点的值 */
public Integer val(int i) {
// 若索引越界,则返回 null ,代表空位
if (i < 0 || i >= size())
return null;
return tree.get(i);
}
/* 获取索引为 i 节点的左子节点的索引 */
public Integer left(int i) {
return 2 * i + 1;
}
/* 获取索引为 i 节点的右子节点的索引 */
public Integer right(int i) {
return 2 * i + 2;
}
/* 获取索引为 i 节点的父节点的索引 */
public Integer parent(int i) {
return (i - 1) / 2;
}
/* 层序遍历 */
public List<Integer> levelOrder() {
List<Integer> res = new ArrayList<>();
// 直接遍历数组
for (int i = 0; i < size(); i++) {
if (val(i) != null)
res.add(val(i));
}
return res;
}
/* 深度优先遍历 */
private void dfs(Integer i, String order, List<Integer> res) {
// 若为空位,则返回
if (val(i) == null)
return;
// 前序遍历
if ("pre".equals(order))
res.add(val(i));
dfs(left(i), order, res);
// 中序遍历
if ("in".equals(order))
res.add(val(i));
dfs(right(i), order, res);
// 后序遍历
if ("post".equals(order))
res.add(val(i));
}
/* 前序遍历 */
public List<Integer> preOrder() {
List<Integer> res = new ArrayList<>();
dfs(0, "pre", res);
return res;
}
/* 中序遍历 */
public List<Integer> inOrder() {
List<Integer> res = new ArrayList<>();
dfs(0, "in", res);
return res;
}
/* 后序遍历 */
public List<Integer> postOrder() {
List<Integer> res = new ArrayList<>();
dfs(0, "post", res);
return res;
}
}
public class array_binary_tree {
public static void main(String[] args) {
// 初始化二叉树
// 这里借助了一个从数组直接生成二叉树的函数
List<Integer> arr = Arrays.asList(1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15);
TreeNode root = TreeNode.listToTree(arr);
System.out.println("\n初始化二叉树\n");
System.out.println("二叉树的数组表示:");
System.out.println(arr);
System.out.println("二叉树的链表表示:");
PrintUtil.printTree(root);
// 数组表示下的二叉树类
ArrayBinaryTree abt = new ArrayBinaryTree(arr);
// 访问节点
int i = 1;
Integer l = abt.left(i);
Integer r = abt.right(i);
Integer p = abt.parent(i);
System.out.println("\n当前节点的索引为 " + i + " ,值为 " + abt.val(i));
System.out.println("其左子节点的索引为 " + l + " ,值为 " + (l == null ? "null" : abt.val(l)));
System.out.println("其右子节点的索引为 " + r + " ,值为 " + (r == null ? "null" : abt.val(r)));
System.out.println("其父节点的索引为 " + p + " ,值为 " + (p == null ? "null" : abt.val(p)));
// 遍历树
List<Integer> res = abt.levelOrder();
System.out.println("\n层序遍历为" + res);
res = abt.preOrder();
System.out.println("前序遍历为:" + res);
res = abt.inOrder();
System.out.println("中序遍历为:" + res);
res = abt.postOrder();
System.out.println("后序遍历为:" + res);
}
}