二叉树的前中后序遍历、层序遍历、前中序构建二叉树、中后序构建二叉树(Java)
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
准备
这里先定义一下二叉树节点
java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
1、前中序构建二叉树
java
/**
* 根据前序中序构建二叉树
*
* @param inorder 中序遍历
* @param inStart 中序开始的下标
* @param inEnd 中序结束的下标
* @param preorder 前序遍历
* @param preStart 前序开始的下标
* @param preEnd 前序结束的下标
* @return
*/
private static TreeNode buildTreeByPreAndInHelper(int[] inorder, int inStart, int inEnd, int[] preorder,
int preStart, int preEnd) {
System.out.println(preStart);
if (preStart >= preEnd || inStart >= inEnd) {
return null;
}
// 每次取前序遍历的第一个元素作为根节点
TreeNode root = new TreeNode(preorder[preStart]);
System.out.println(root.val + " " + preStart);
// 从中序遍历中找到当前根节点的下标
int index;
for (index = inStart; index < inEnd; index++) {
if (inorder[index] == root.val) {
break;
}
}
int leftSize = index - inStart;
root.left = buildTreeByPreAndInHelper(inorder, inStart, index, preorder, preStart + 1, preStart + leftSize+1);
root.right = buildTreeByPreAndInHelper(inorder, index + 1, inEnd, preorder, preStart + 1 + leftSize, preEnd);
return root;
}
2、中后序构建二叉树
java
/**
* 根据中序后序构建二叉树
*
* @param inorder 中序遍历
* @param inStart 中序开始的下标
* @param inEnd 中序结束的下标
* @param postorder 后序遍历
* @param postStart 后序开始的下标
* @param postEnd 后序结束的下标
* @return
*/
private static TreeNode buildTreeByInAndPostHelper(int[] inorder, int inStart, int inEnd, int[] postorder,
int postStart, int postEnd) {
// 下标越界,则说明没有可处理的节点
if (inStart >= inEnd || postStart >= postEnd) {
return null;
}
// 每次取后序遍历中的最后一个节点作为根节点
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置,
int index;
for (index = inStart; index < inEnd; index++) {
if (inorder[index] == rootVal) {
break;
}
}
// 以中序遍历中的根节点位置为分界线,
// 左边为左子树,右边为右子树
// 当前根节点的左子树中节点个数
int leftSize = index - inStart;
// 递归构建左子树
root.left = buildTreeByInAndPostHelper(inorder, inStart, index, postorder, postStart, postStart + leftSize);
// 递归构建右子树
root.right = buildTreeByInAndPostHelper(inorder, index + 1, inEnd, postorder, postStart + leftSize,
postEnd - 1);
return root;
}
3、前序遍历
java
/**
* 打印前序遍历 (根左右)
*
* @param root
*/
private static void preOrderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
}
if (root.left != null) {
preOrderTraversal(root.left);
}
if (root.right != null) {
preOrderTraversal(root.right);
}
}
4、中序遍历
java
/**
* 打印中序遍历 (左根右)
*
* @param root
*/
private static void inOrderTraversal(TreeNode root) {
if (root.left != null) {
inOrderTraversal(root.left);
}
if (root != null) {
System.out.print(root.val + " ");
}
if (root.right != null) {
inOrderTraversal(root.right);
}
}
5、后序遍历
java
/**
* 打印后序遍历 (左右根)
*
* @param root
*/
private static void postOrderTraversal(TreeNode root) {
if (root.left != null) {
inOrderTraversal(root.left);
}
if (root.right != null) {
inOrderTraversal(root.right);
}
if (root != null) {
System.out.print(root.val + " ");
}
}
6、层序遍历
java
/**
* 打印层序遍历
*
* @param root
*/
private static void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
// 利用队列先进先出的特点,先对当前根节点打印,然后接着存放其左右节点
// 之后每次进来都重新判断其左右节点非空,并对其进行处理
// 与层序遍历的逻辑相符
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// System.out.println("size的大小为:"+size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
完整代码
java
import java.util.*;
// L2-006 树的遍历
public class L2_6 {
public static void main(String[] args) {
// 7
// 2 3 1 5 7 6 4 后
// 1 2 3 4 5 6 7 中
// 4 1 3 2 6 5 7 前
// 4 1 6 3 5 7 2 层
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// int[] postorder = new int[n];
// for (int i = 0; i < n; i++) {
// postorder[i] = sc.nextInt();
// }
int[] inorder = new int[n];
for (int i = 0; i < n; i++) {
inorder[i] = sc.nextInt();
}
int[] preorder = new int[n];
for (int i = 0; i < n; i++) {
preorder[i] = sc.nextInt();
}
TreeNode root = buildTreeByPreAndIn(inorder, preorder);
preOrderTraversal(root);
System.out.print("\n");
inOrderTraversal(root);
System.out.print("\n");
postOrderTraversal(root);
System.out.print("\n");
levelOrderTraversal(root);
}
/**
* 打印前序遍历 (根左右)
*
* @param root
*/
private static void preOrderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
}
if (root.left != null) {
preOrderTraversal(root.left);
}
if (root.right != null) {
preOrderTraversal(root.right);
}
}
/**
* 打印中序遍历 (左根右)
*
* @param root
*/
private static void inOrderTraversal(TreeNode root) {
if (root.left != null) {
inOrderTraversal(root.left);
}
if (root != null) {
System.out.print(root.val + " ");
}
if (root.right != null) {
inOrderTraversal(root.right);
}
}
/**
* 打印后序遍历 (左右根)
*
* @param root
*/
private static void postOrderTraversal(TreeNode root) {
if (root.left != null) {
inOrderTraversal(root.left);
}
if (root.right != null) {
inOrderTraversal(root.right);
}
if (root != null) {
System.out.print(root.val + " ");
}
}
/**
* 打印层序遍历
*
* @param root
*/
private static void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
// 利用队列先进先出的特点,先对当前根节点打印,然后接着存放其左右节点
// 之后每次进来都重新判断其左右节点非空,并对其进行处理
// 与层序遍历的逻辑相符
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// System.out.println("size的大小为:"+size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
/**
* 根据前序中序构建二叉树
*
* @param inorder 中序遍历
* @param preorder 前序遍历
* @return 二叉树
*/
private static TreeNode buildTreeByPreAndIn(int[] inorder, int[] preorder) {
if (preorder.length == 0) {
return null;
}
return buildTreeByPreAndInHelper(inorder, 0, inorder.length, preorder, 0, preorder.length);
}
/**
* 根据前序中序构建二叉树
*
* @param inorder 中序遍历
* @param inStart 中序开始的下标
* @param inEnd 中序结束的下标
* @param preorder 前序遍历
* @param preStart 前序开始的下标
* @param preEnd 前序结束的下标
* @return
*/
private static TreeNode buildTreeByPreAndInHelper(int[] inorder, int inStart, int inEnd, int[] preorder,
int preStart, int preEnd) {
System.out.println(preStart);
if (preStart >= preEnd || inStart >= inEnd) {
return null;
}
// 每次取前序遍历的第一个元素作为根节点
TreeNode root = new TreeNode(preorder[preStart]);
System.out.println(root.val + " " + preStart);
// 从中序遍历中找到当前根节点的下标
int index;
for (index = inStart; index < inEnd; index++) {
if (inorder[index] == root.val) {
break;
}
}
// 当前根节点左子树的个数
int leftSize = index - inStart;
root.left = buildTreeByPreAndInHelper(inorder, inStart, index, preorder, preStart + 1, preStart + leftSize + 1);
root.right = buildTreeByPreAndInHelper(inorder, index + 1, inEnd, preorder, preStart + 1 + leftSize, preEnd);
return root;
}
/**
* 根据中序后序构建二叉树
*
* @param inorder 中序遍历
* @param postorder 后序遍历
* @return 二叉树
*/
private static TreeNode buildTreeByInAndPost(int[] inorder, int[] postorder) {
if (inorder.length == 0) {
return null;
}
return buildTreeByInAndPostHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
/**
* 根据中序后序构建二叉树
*
* @param inorder 中序遍历
* @param inStart 中序开始的下标
* @param inEnd 中序结束的下标
* @param postorder 后序遍历
* @param postStart 后序开始的下标
* @param postEnd 后序结束的下标
* @return
*/
private static TreeNode buildTreeByInAndPostHelper(int[] inorder, int inStart, int inEnd, int[] postorder,
int postStart, int postEnd) {
// 下标越界,则说明没有可处理的节点
if (inStart >= inEnd || postStart >= postEnd) {
return null;
}
// 每次取后序遍历中的最后一个节点作为根节点
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置,
int index;
for (index = inStart; index < inEnd; index++) {
if (inorder[index] == rootVal) {
break;
}
}
// 以中序遍历中的根节点位置为分界线,
// 左边为左子树,右边为右子树
// 当前根节点的左子树中节点个数
int leftSize = index - inStart;
// 递归构建左子树
root.left = buildTreeByInAndPostHelper(inorder, inStart, index, postorder, postStart, postStart + leftSize);
// 递归构建右子树
root.right = buildTreeByInAndPostHelper(inorder, index + 1, inEnd, postorder, postStart + leftSize,
postEnd - 1);
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
评论
0 条—
还没有评论,来说第一句