二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子
重要的二叉树结构
-
完全二叉树(complete binary tree)是一种二叉树结构,除最后一层以外,每一层都必须填满,填充时要遵从先左后右
-
平衡二叉树(balance binary tree)是一种二叉树结构,其中每个节点的左右子树高度相差不超过 1
1、存储
存储方式分为两种
-
定义树节点与左、右孩子引用(TreeNode)
-
使用数组,前面讲堆时用过,若以 0 作为树的根,索引可以通过如下方式计算
-
父 = floor((子 - 1) / 2)
-
左孩子 = 父 * 2 + 1
-
右孩子 = 父 * 2 + 2
-
二叉树的节点结构
/**
* 二叉树节点
*
* @author zjj_admin
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(TreeNode left, int val, TreeNode right) {
this.left = left;
this.val = val;
this.right = right;
}
}
2、遍历
遍历也分为两种
-
广度优先遍历(Breadth-first order):尽可能先访问距离根最近的节点,也称为层序遍历
-
深度优先遍历(Depth-first order):对于二叉树,可以进一步分成三种(要深入到叶子节点)
-
pre-order 前序遍历,对于每一棵子树,先访问该节点,然后是左子树,最后是右子树
-
in-order 中序遍历,对于每一棵子树,先访问左子树,然后是该节点,最后是右子树
-
post-order 后序遍历,对于每一棵子树,先访问左子树,然后是右子树,最后是该节点
-
2.1、广度优先
本轮开始时队列 | 本轮访问节点 |
---|---|
[1] | 1 |
[2, 3] | 2 |
[3, 4] | 3 |
[4, 5, 6] | 4 |
[5, 6] | 5 |
[6, 7, 8] | 6 |
[7, 8] | 7 |
[8] | 8 |
[] |
-
初始化,将根节点加入队列
-
循环处理队列中每个节点,直至队列为空
-
每次循环内处理节点后,将它的孩子节点(即下一层的节点)加入队列
注意
以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树
对于数组表现的二叉树,则直接遍历数组即可,自然为层序遍历的顺序
2.2、深度优先遍历
深度优先遍历有前序遍历、中序遍历和后续遍历三种
-
前序遍历: 先输出父节点,再遍历左子树和右子树
-
中序遍历: 先遍历左子树,再输出父节点,再遍历右子树
-
后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点
-
小结: 看输出父节点的顺序,就确定是前序,中序还是后序
前,中,后序遍历详解
-
创建一颗二叉树
-
前序遍历 2.1 先输出当前节点(初始的时候是root节点) 2.2 如果左子节点不为空,则递归继续前序遍历 2.3 如果右子节点不为空,则递归继续前序遍历
-
中序遍历 3.1 如果当前节点的左子节点不为空,则递归中序遍历 3.2 输出当前节点 3.3 如果当前节点的右子节点不为空,则递归中序遍历文章来源:https://www.toymoban.com/news/detail-604971.html
-
后序遍历 4.1 如果当前节点的左子节点不为空,则递归后序遍历 4.2 如果当前节点的右子节点不为空,则递归后序遍历 4.3 输出当前节点文章来源地址https://www.toymoban.com/news/detail-604971.html
2.3、递归实现深度优先遍历
/**
* 前序遍历,继续递归实现
*
* @param root
*/
static void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + "\t");
preOrder(root.left);
preOrder(root.right);
}
/**
* 中序遍历
*
* @param root
*/
static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + "\t");
inOrder(root.right);
}
/**
* 后续遍历
*
* @param root
*/
static void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + "\t");
}
2.4、非递归实现深度优先遍历
/**
* 前序遍历
* 使用非递归的方式
*
* @param root
*/
static String preOrder(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
StringBuilder res = new StringBuilder();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
res.append(curr.val).append(" ");
stack.push(curr);
curr = curr.left;
} else {
//弹栈
TreeNode pop = stack.pop();
curr = pop.right;
}
}
return res.toString();
}
/**
* 中序遍历
* 使用非递归的方式
*
* @param root
*/
static String inOrder(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
StringBuilder res = new StringBuilder();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
//弹栈
TreeNode pop = stack.pop();
res.append(pop.val).append(" ");
curr = pop.right;
}
}
return res.toString();
}
/**
* 后续遍历
* 使用非递归的方式
*
* @param root
*/
static String postOrder(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
StringBuilder res = new StringBuilder();
TreeNode curr = root;
TreeNode pop = null;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == pop) {
//弹栈
pop = stack.pop();
res.append(pop.val).append(" ");
} else {
curr = peek.right;
}
}
}
return res.toString();
}
2.5、在一个方法中实现二叉树的三种深度优先遍历(前序、中序和后续)
/**
* 使用非递归的方式求解,在一个方法中实现
* 实现前序遍历,中序遍历和后续遍历
*
* @param root
*/
static List<String> order(TreeNode root) {
TreeNode curr = root;
StringBuilder pre = new StringBuilder("preOrder:");
StringBuilder in = new StringBuilder("inOrder:");
StringBuilder post = new StringBuilder("postOrder:");
//定义一个栈,用于存储当前节点的父节点
LinkedList<TreeNode> s = new LinkedList();
TreeNode pop = null;
while (curr != null || !s.isEmpty()) {
if (curr != null) {
s.push(curr);
pre.append(curr.val + " ");
//依次向左边遍历
curr = curr.left;
} else {
TreeNode peek = s.peek();
if (peek.right == null) {
in.append(peek.val + " ");
//当没有右节点时
pop = s.pop();
//这一行打印的是中序遍历的结果
post.append(pop.val + " ");
} else if (peek.right == pop) {
//当右节点已经遍历结束时
pop = s.pop();
//这一行打印的是中序遍历的结果
post.append(pop.val + " ");
} else {
//右节点不为空并且没有遍历
in.append(peek.val + " ");
curr = peek.right;
}
}
}
return List.of(pre.toString(), in.toString(), post.toString());
}
到了这里,关于【数据结构和算法15】二叉树的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!