二叉树的各种遍历及根据遍历序列构建二叉树,Java实现
2023-12-15 11:31:15
本文主要讲解二叉树的各种遍历方式,基本概念参考二叉树的概念。二叉树的各种遍历及根据遍历序列构建二叉树,Java实现。我持续补充。
遍历二叉树
遍历或称周游,traversal。系统地访问数据结构中的节点,每个节点都正好被访问到一次。
深度优先遍历二叉树
三种深度优先遍历的递归定义:
- 前序法(tLR次序,preorder traversal):访问根结点,按前序遍历左子树;按前序遍历右子树。
- 中序法(LtR次序,inorder traversal):按中序遍历左子树;访问根结点;按中序遍历右子树。
- 后序法(LRt次序,postorder traversal):按后序遍历左子树;按后序遍历右子树;访问根结点。
递归的前序、中序、后序
public static List<Integer> preOrderTraverseByRecursion(BinaryTreeNode root, List<Integer> list) {
if (root != null) {
list.add(root.getKey());//前序法访问节点
preOrderTraverseByRecursion(root.getLeft(), list);
//list.add(root.getKey());//中序法访问节点
preOrderTraverseByRecursion(root.getRight(), list);
//list.add(root.getKey());//后序法访问节点
}
return list;
}
非递归遍历
递归算法非常简洁,推荐使用,当前的编译系统优化效率很不错了。特殊情况用栈模拟递归,深度优先遍历的回溯特点和栈的工作原理一致,有些应用环境资源限制不适合递归。
非递归的前序遍历
实现
/**
* 先序遍历(非递归)
* 通过栈来避免递归(有节点入栈)
*
* @param root
*/
public static List<Integer> preOrderTraverseByNonRecursion(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();// 用于存放遍历后的结果
Stack<BinaryTreeNode> stack = new Stack();// 用于存放右子树节点
BinaryTreeNode p = root;
//左子树和右子树都未遍历时,遍历
while (p != null || stack.size() > 0) {
if (p != null) { //左子树不为空时,遍历左子树
list.add(p.getKey());//当前节点输出
stack.push(p.getRight());//右子树入栈,待左子树遍历完后遍历右子树
p = p.getLeft();//遍历左子树
} else { //左子树遍历完后,遍历右子树
p = stack.pop();
}
}
return list;
}
非递归的中序遍历
实现
/**
* 中序遍历(非递归)
*
* @param root
*/
public static List<Integer> inOrderTraverseByNonRecursion(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<BinaryTreeNode> stack = new Stack<>();
BinaryTreeNode current = root;
//遍历节点的左子树并将根结点入栈,直到左子树为null时,然后出栈获取节点并遍历该节点的右子树的左子树直到为null
while(current != null || !stack.empty()){
if(current != null){
stack.push(current);
current = current.getLeft();
}else{
BinaryTreeNode top = stack.pop();
list.add(top.getKey());
current = top.getRight();
}
}
return list;
}
非递归的后序遍历
实现
/**
* 后续遍历(非递归)
*
* @param root
*/
public static List<Integer> postOrderTraverseByNonRecursion(BinaryTreeNode root) {
Stack<BinaryTreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
stack.push(root);
BinaryTreeNode current;
while (stack.isEmpty() == false) {
current = stack.pop();
if (current != null) {
list.add(current.getKey());
stack.push(current.getLeft());
stack.push(current.getRight());
}
}
Collections.reverse(list);
return list;
}
宽度优先遍历二叉树
从二叉树的第0层(根结点)开始,自上而下,追层遍历;在同一层中,按照从左到右的顺序对节点逐一访问。
特点是先遍历先访问,符合队列的特征,通过队列来实现。
实现如下:
/**
* 层序遍历(宽度优先遍历)
* 特点是先进先出,符合队列的特性
*
* @param root
* @return
*/
public static List<Integer> layerOrderTraverse(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<BinaryTreeNode> queue = new LinkedList<>();
BinaryTreeNode current;
queue.offer(root);
while (!queue.isEmpty()){
current = queue.poll();
list.add(current.getKey());
if(current.getLeft() != null){
queue.addLast(current.getLeft());
}
if(current.getRight() != null){
queue.addLast(current.getRight());
}
}
return list;
}
根据遍历序列构造二叉树
先来个结论及说明:
- 仅一个先(中、后)序序列不能构造唯一一颗二叉树(原因:无法确定左右子树或根结点)
- 仅先(后)序序列和中序序列可以构造唯一一颗二叉树(原因:先序序列和后序序列无法构造唯一一颗二叉树)
- 用扩充先(后)序序列可以构造唯一一颗二叉树
- 用扩充中序序列不能构造唯一一颗二叉树
先序序列和中序序列创建构造二叉树
实现:
/**
* 根据先序序列和中序序列构造二叉树(递归实现)
* <p>
* 先序序列第一个元素是树的根结点,从中序序列中找出与根结点所在位置k:
* 1.确定根结点的左子树和右子树的中序序列:该位置之前的元素就是根结点左子树的中序序列,该位置之后的元素就是根结点的右子树的中序序列
* 2.确定根结点的左子树和右子树的先序序列:先序序列第一个元素往后k元素就是根结点左子树的先序序列,k+1位置之后就是根结点右子树的先序序列
* <p>
* <p>
* perOrder[i]~perOrder[j] 是子树的先序序列
* inOrder[s]~inOrder[t] 是子树的中序序列
*
* @param perOrder
* @param inOrder
* @param i
* @param j
* @param s
* @param t
* @return
*/
public static BinaryTreeNode buildTreeByPerOrderAndInOrder(Integer[] perOrder, Integer[] inOrder, int i, int j, int s, int t) {
if (i > j) {
return null;
}
BinaryTreeNode root = new BinaryTreeNode(perOrder[i]);
int k;
k = s;
while (k <= t && inOrder[k] != perOrder[i]) {
k++;
}
if (k > t) {
return null;
}
root.setLeft(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + 1, j + k - s, s, k - 1));
root.setRight(buildTreeByPerOrderAndInOrder(perOrder, inOrder, i + k - s + 1, j, k + 1, t));
return root;
}
后序序列和中序序列创建构造二叉树
一个节点的左子树和右子树存在三种组合方式,左子树为null,右子树为null,左右子树都不为null。
运用递归思想时,按这三种情况分析左右子树的后序序列和中序序列。实现如下:
/**
* 根据后序序列和中序序列构造二叉树(递归实现)
*
* postOrder[i]~postOrder[j]是子树的后序序列
* inOrder[s]~inOrder[t]是子树的中序序列
*
* @param postOrder
* @param inOrder
* @param i
* @param j
* @param s
* @param t
* @return
*/
public static BinaryTreeNode buildTreeByPostOrderAndInOrder(Integer[] postOrder, Integer[] inOrder, int i, int j, int s, int t) {
if (i > j) {
return null;
}
BinaryTreeNode root = new BinaryTreeNode(postOrder[j]);
int k;
k = s;
while (k <= t && inOrder[k] != postOrder[j]) {
k++;
}
if (k > t) {
return null;
}
//左子树个数
int countLeft = k - s;
//右子树个数
int countRight = t - k;
if (countLeft == 0) {
//左子树为null
root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countRight, j - 1, t - countRight + 1, t));
} else if (countRight == 0) {
//右子树为null
root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - countLeft, j - 1, t - countLeft, t - countRight - 1));
} else {
//左、右子树不为null
root.setLeft(buildTreeByPostOrderAndInOrder(postOrder, inOrder, i, i + countLeft - 1, s, s + countLeft - 1));
root.setRight(buildTreeByPostOrderAndInOrder(postOrder, inOrder, j - 1 - countRight + 1, j - 1, t - countRight + 1, t));
}
return root;
}
是否可以通过非递归来实现呢?
可以考虑考虑
源码
参考
- https://www.icourse163.org/learn/PKU-1002534001?tid=1206727206#/learn/content?type=detail&id=1211568252&cid=1214289509
- https://www.icourse163.org/learn/PAEU-1001660013?tid=1460890448#/learn/content?type=detail&id=1237237109&cid=1257067240
- 二叉树的构建 https://www.icourse163.org/learn/PAEU-1001660013?tid=1460890448#/learn/content
创作地址
https://github.com/jast90/jast90.github.io/issues/32
文章来源:https://blog.csdn.net/jastzhang/article/details/108662929
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!