树以及常用的算法
树的概念
树(Tree)的基本概念
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
二叉树的概念
每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的性质
1.若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)
2.高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)(空树的高度为-1)
3.对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1
二叉树的分类
二叉树又分为：完美二叉树，完全二叉树，完满二叉树
其中完满二叉树：除了叶子节点每个节点都有俩个孩子
完全二叉树：除了最后一层外，除了叶子节点每个节点都有俩个孩子
完美二叉树：除了叶子节点外，每一层每个节点都有俩个孩子
完美二叉树
完全二叉树
完满二叉树
完满二叉树
二叉树常见的搜索算法，借助leetcode展示
前序遍历
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Given a binary tree, return the preorder traversal of its TreeNodes' values.
*/
public class Lc144 {
/*
* 前序遍历 ：根左右 思路；将当前节点压入栈中，一直遍历左子树知道当前节点为空，向上弹出遍历一下右子树。
*/
public static List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
list.add(curr.val);
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return list;
}
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, 2, null};
TreeNode root = CreateNode.createTree(arr).get(0);
List<Integer> list = preorderTraversal(root);
list.forEach(n -> System.out.println(n));
}
}
中顺遍历
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Given a binary tree, return the inorder traversal of its nodes' values.
*/
public class Lc94 {
/*
* 中序遍历：左根右
*/
public static List<Integer> orderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> preorder = new ArrayList<Integer>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
preorder.add(curr.val);
curr = curr.right;
}
return preorder;
}
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, null, 2, null, null, 3 };
TreeNode root = CreateNode.createTree(arr).get(0);
List<Integer> list = orderTraversal(root);
list.forEach(n -> System.out.println(n));
}
}
后序遍历
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Lc145 {
/*
* 后续序遍历：左右根
*/
public static List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
TreeNode curr = root;
stack.push(curr);
while (!stack.isEmpty()) {
curr = stack.pop();
list.add(0, curr.val);
if (curr.left != null) {
stack.push(curr.left);
}
if (curr.right != null) {
stack.push(curr.right);
}
}
return list;
}
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, null, 2 };
TreeNode root = CreateNode.createTree(arr).get(0);
List<Integer> list = postorderTraversal(root);
list.forEach(n -> System.out.println(n));
}
}
层序遍历
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Lc102 {
/**
* 层序遍历
*
* @param root
* @return
*/
public static List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> lists = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<>();
if (root == null) {
return lists;
}
TreeNode curr = root;
queue.offer(curr);
int size = queue.size();
while (!queue.isEmpty()) {
curr = queue.poll();
list.add(curr.val);
size--;
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
if (size == 0) {
lists.add(list);
list = new ArrayList<>();
size = queue.size();
}
}
return lists;
}
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, 2, 3, 4, 5, 6, 7 };
TreeNode root = CreateNode.createTree(arr).get(0);
List<List<Integer>> lists = levelOrder(root);
lists.forEach(n -> {
n.forEach(m -> {
System.out.print(m + ",");
});
System.out.println();
});
}
}
BFS
public class Lc100 {
//bfs 递归
public static boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) {
return p == q ? true : false;
} else {
if (p.val != q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
}
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, 2, 2, 3, null, null, 3 };
TreeNode root = CreateNode.createTree(arr).get(0);
System.out.println(isSameTree(root.left, root.right));
}
}
介绍一个二叉树数组转换节点的工具类
使用方法，每一个main函数中都是
import java.util.ArrayList;
import java.util.List;
public class CreateNode {
public static List<TreeNode> list = new ArrayList<TreeNode>(); // 用一个集合来存放每一个Node
public static List<TreeNode> createTree(Integer[] array) {
list.clear();
for (int i = 0; i < array.length; i++) {
TreeNode TreeNode = new TreeNode(array[i], null, null); // 创建结点，每一个结点的左结点和右结点为null
list.add(TreeNode); // list中存着每一个结点
}
// 构建二叉树
if (list.size() > 0) {
for (int i = 0; i < array.length / 2 - 1; i++) { // i表示的是根节点的索引，从0开始
if (list.get(2 * i + 1) != null) {
// 左结点
list.get(i).left = list.get(2 * i + 1);
}
if (list.get(2 * i + 2) != null) {
// 右结点
list.get(i).right = list.get(2 * i + 2);
}
}
// 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
int lastIndex = array.length / 2 - 1;
// 左结点
list.get(lastIndex).left = list.get(lastIndex * 2 + 1);
// 右结点，如果数组的长度为奇数才有右结点
if (array.length % 2 == 1) {
list.get(lastIndex).right = list.get(lastIndex * 2 + 2);
}
}
return list;
}
// 遍历，先序遍历
public static void print(TreeNode TreeNode) {
if (TreeNode != null) {
System.out.print(TreeNode.val + " ");
print(TreeNode.left);
print(TreeNode.right);
}
}
/**
* @param args
*/
public static void main(String[] args) {
Integer[] array = { 1, 2, 2, null, 3, null, 3 };
CreateNode.createTree(array);
print(list.get(0));
}
}
基础类-节点
public class TreeNode {
public Integer val; // 自己本身值
public TreeNode left; // 左结点
public TreeNode right; // 右结点
public TreeNode() {
}
public TreeNode(Integer val, TreeNode left, TreeNode right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
public int getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}