二叉树的前中后序遍历、层序遍历、前中序构建二叉树、中后序构建二叉树(Java)

2024-03-25数据结构与算法4 分钟131 次阅读
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 条
登录 之后才能评论
—
还没有评论,来说第一句